Top

# Graph Theory

Graph theory, as the name suggests, is the study of graphs. A graph is defined to be a mathematical structure which connects a set of points representing a particular function, virtue or rule.
A simple graph may look like the image shown below:

The points may be referred as vertices and the line segments connecting them may be called as edges or sides. Graph theory studies about how network is encoded.

The study of graph theory enables us to know how to construct graphs as well as how to solve problems using graphs. Graph theory is applicable not just in mathematics, but in almost every field, such as: physics, chemistry, economics, finance, geography, weather forecast, computer science, sociology, psychology, biology and many more.

 Related Calculators Calculator for Graphing circle graph calculator Ellipse Graphing Calculator Equation Graphing Calculator

## History

The credit of beginning of graph theory goes to famous Swiss mathematician named Leonhard Euler. In 1735, Euler tried to solve the problem of Konigsberg bridge. This problems was actually a puzzle which was concerning for the possibility of finding the path using each one of the seven bridges that were made over a river flowing through an island. The condition was that a bridge could not be passed by twice.

The problems can be shown in the following figure:

Euler proved that no such path exists. In his proof, he introduced graph theory.

Also, scientist William R. Hamilton studied the polyhedral cycles which led to the origin of concept of Hamiltonian graph.
After the discovery of a subject which may be based on graphs, It took 200 years for the first book on graph theory to be written.

## Degree

Before get into the graph theory, we should know about the vertex, degree and edge of the graph:
Vertex or Node: Each point in the graph is known as a node or a vertex.
Edge or Link: The line segment that joins two nodes is known as an edge or a link.
Degree:
Degree is measured for each vertex separately. Degree of a vertex is the total number of edges that are connected with that particular vertex. If a vertex is named as v, then the degree of v is denoted by :
deg (v)
Let us consider following graph:

Total number of vertices are 6. The degree of each vertex is 2, since total number of edges that are joined with each vertex is 2.
If in case, there is any loop in the graph, then it is counted twice while assessing the degree of vertex that connects any loop.

## Algebraic Graph Theory

Algebraic graph theory is said to be a fascinating branch of mathematics which applies algebraic methods to the problems of graphs. It is a subject that is eventually a combination of algebra and graph theory. In algebraic graph theory, students study how algebraic methods and tools are utilized in order to provide surprising results and proofs in graph theory.
Algebraic graph theory can be divided into three main branches:
1) Use of Linear Algebra: This branch algebraic graph theory uses linear algebra and matrices for solving various problems of graph theory.
2) Use of Group Theory: Another branch of algebraic graph theory involves concepts of group theory with graph theory.
3) Graph invariants: This branch of graph theory deals with study of invariants (abstract structure) of graphs.

## Cycle

In graph, a cycle is defined as a closed path. It contains a set of vertices or nodes in which starting point and ending point are the same. A cycle may be referred as a closed circuit. A cycle in which no vertex is repeated is known as simple cycle. In a simple cycle, every vertex has degree exactly equal to two.
Cycles can be classified into two on the basis of number of sides or edges:
1) Even Cycle:
A cycle having even number of links or edges is known as an even cycle.
2) Odd Cycle:
Odd cycle is referred to a cycle which has total number of odd edges or links.
A cyclic graph is denoted by the symbol $C_{n}$, where n is the total number of edges in it.

## Trees

In graph theory, trees were introduced by famous British mathematician Arthur Cayley in 1857. A tree is defined to be the connection of undirected networks in which there is only one path between any two vertices. More specifically, a tree does not have cycles or loops. There are only straight lines that proceed in any direction in the form of a branch of an edge.
Following diagram demonstrates a tree studied in graph theory :

A tree has few properties which are as follows:
1) It has no simple cycles.
2) It does not contain any loops.
3) If a tree has total "v" number of vertices, then it would have "v - 1" edges.
4) If any single edge is removed from the tree, then would not be connected.
The union of more than one trees is termed as a forest.

## Properties

Few basic structural properties of graphs that are studied under graph theory are:
1) Assortativite graph : The graph in which similar nodes are connected to one another, is known as an assortative graph, otherwise a disassortative graph.

2) Symmetry : When every pair of vertices is connected in one direction as well as in reverse direction, is known as a symmetric network, otherwise asymmetric. In other words, in symmetric graph, it is possible to move in both the directions on a line.

3) Root : Usually a root is the the starting point of a network system.

4) Cycle Graph : A graph having one single cycle is known as cycle graph.

5) Complete Graph : A graph in which there is exactly one edge connecting each pair of nodes.

6) Path Graph : Path graph is one which has a single path.

## Algorithms

Algorithm is a step-by-step procedure for the computation or calculation of a function. Graph theory also contains various algorithms. The algorithms of graph theory are well defined set of instructions that involve predetermined steps in order to solve different types of problems in graph theory as well as in other fields.
Few important algorithms that are used in graph theory are listed below:
1) Girvan-Newman algorithm
2) Prim's algorithm
3) Karger algorithm
4) Ford-Fulkerson algorithm
5) Edmond algorithm
6) Bellman-Ford algorithm
7) Push-relabel algorithm
 More topics in Graph Theory Connectivity
 NCERT Solutions NCERT Solutions NCERT Solutions CLASS 6 NCERT Solutions CLASS 7 NCERT Solutions CLASS 8 NCERT Solutions CLASS 9 NCERT Solutions CLASS 10 NCERT Solutions CLASS 11 NCERT Solutions CLASS 12
 Related Topics Math Help Online Online Math Tutor
*AP and SAT are registered trademarks of the College Board.