# Graph Theory

(This is a first post of a two part series giving an introduction into Graph Theory and its applications. This post will contain more of an theory on graphs and the next one would concentrate more on its applications)

The different types of graphs discussed here are - Directed Graphs, Undirected Graphs & Trees (which are similar to graphs as we shall see)

A**directed graph**or

**digraph**G is a pair (V,E) where V is a finite set of

**vertices**and E is a set of

**edges**which has a binary relation on V. Given below is an example of a digraph.

An **undirected graph **G = (V, E), the edge set E consists of
unordered pairs of vertices. The edge (u, v) is the same as (v, u). No
self-loops are allowed all though this is possible in a digraph. Given
below is an example of an undirected graph.

Terminologies used in graphs:

Related to edges of a graph

- If (u, v) is an edge in a directed graph G = (V, E), we say that it is
**incident from**u and**incident to**v. For example, in the above directed graph, the edge (1, 2) is incident from 1 and incident to 2

- if (u, v) is an edge in an undirected graph G = (V, E), we say that is
**incident on**vertices u and v. For example, in the above undirected graph, the edge (1, 2) is incident on vertices 1 and 2

Related to vertices of a graph

- If (u, v) is an edge in the graph G = (V, E), we say that vertex v is
**adjacent**to vertex u. This relation is symmetric if the graph is undirected. In the directed graph, w.r.t edge (2, 3) vertex 3 is adjacent to vertex 3 and in the first undirected graph, the edge (2, 4) vertex 2 is adjacent to vertex 4 and vertex 4 is also adjacent to vertex 2

- The
**degree**of a vertex in an undirected graph G = (V, E) is the number of edges incident to it. A vertex is said to be isolated if its degree is 0. In the first undirected graph, the degree of vertex 4 is four (In fact the graph is a complete graph with all vertices of degree four). And in the second undirected graph, vertex 2 is isolated and has a degree of zero

- The
**degree**of a vertex in a directed graph G = (V, E) is the sum of its**In-degree**(Number of edges incident from the vertex) and its**Out-degree**(Number of edges incident to the vertex). In the above directed graph, the in-degree of vertex 4 is three and the out-degree is two

- A
**path**from a vertex u to a vertex v in a graph G = (V, E) is a sequence <V0, V1, V2, V3, … , Vn> where V0 = u and Vn = v and v is reachable from u. A path is**simple**if all vertices in a path is unique. A example path in the directed graph is 1, 2, 3, 5

- A
**subpath**of a path P is the continuous subsequence of its vertices. An example subpath in the directed graph is 2, 3, 4 of the complete path 1, 2, 3, 4

- A path forms a
**cycle**if one or more of its vertices are repeated during the path. A path with no cycle is called a simple path. A graph with no cycle is called acyclic. A**dag**is a directed acyclic graph which has no cycles. An example of a cycle in the directed graph is 1, 2, 3, 4, 3, 5.

- A
**connected graph**is a graph G = (V, E), where all its vertices are reachable using a path. The first undirected graph in the above illustration is a connected graph where as the second undirected graph is not connected. In the directed graph too all vertices form a connected graph

- The
**strongly connected components**of a directed graph are the set of vertices for which each pair of vertices in the set are reachable from each other. In the first undirected graph, all the vertices form a strongly connected component

**tree**is a connected, acyclic, undirected graph. Many algorithms that work on graphs also work on trees. Below are some illustration of trees.

Terminologies used in trees:

- A
**root**is a node which is the base of the graph. No edges come into it. Edges only go out of it. In the illustrations above, 15 and 1 are some examples of trees

- If x is a node in the tree with root r, and any node y on the path from r to x is called an
**ancestor**of x and x is an**descendant**of y. In the first example, 12 is an descendant of 15 and and 22 is an ancestor of 3

- If there is an edge (x,y), then x is called the
**parent**of y and y is called the**child**of x. In the second example, 2 is the parent of 5 and 5 is a child of 2

- The length of the path from the root r to a node x is the
**depth**of x in the tree. The depth of the first illustration is 4 and of the second is 2 (Note: the depth starts from 0)

- The
**height**of the tree is the depth of the lowest node from the root of the tree. The height of the first tree is 4 and of the second one is 2

- A
**binary tree**is one which has zero, one, two or three disjoint sets of nodes. The first example is not a binary tree where as the second one is

- A node to the left of the root is called the
**left child**of the root and a node to the right of the root is called the**right child**of the root

- A
**full binary tree**is a tree where each node is a leaf or has two children. The second illustration is a full binary tree

- A
**complete binary tree**is a tree where all the leaves are in the same level and each non leaf node has two children. The second illustration is again a complete binary tree

Some properties of graphs and trees:

- In a complete graph, the sum of degree of all vertices is equal to the 2 times number of edges in the graph i.e. for v ∈ V ∑degree (v) = 2 | E |
- Any connected, undirected graph G = (V, E), | E | ≧ | V | -1
- Any two vertices in a tree are connected by a unique simple path
- In a connected tree, | E | = | V | - 1
- A complete binary tree has (2 ^ h) - 1 nodes where h is the height of the tree
- A non empty binary tree with n nodes has a height at least floor(lg n)

If you have read this far, you should follow me on twitter.

Also feel free to follow my projects on github.