Introduction to Graphs

Data Structures using C PlusPlus

Chapter 7: Graphs

 

Introduction to Graphs

A graph is a collection of two sets V and E where V is a finite non‒empty set of vertices and E is a finite non‒empty set of edges.

• Vertices are nothing but the nodes in the graph.

• Two adjacent vertices are joined by edges.

• Any graph is denoted as G = (V, E}.

• For example :

G = {{V₁, V₂, V₃ ,V₄, V₅, V₆},

{E₁, E₂, E₃, E₄, E₅, E₆, E₇ }}

1. Comparison between Graph and Trees

Graph

1. Graph is a non‒linear data structure.

2. It is a collection of vertices/nodes and edges.

3. Each node can have any number of edges.

4. There is no unique node called root in graph.

5. A cycle can be formed.

6. Applications : For finding shortest path in networking graph is used

Tree

1. Tree is a non‒linear data structure.

2. It is a collection of nodes and edges.

3. General trees consist of the nodes having any number of child nodes. But in case of binary trees every node can have at the most two child nodes.

4. There is a unique node called root in trees.

 5. There will not be any cycle.

6. Applications : For game trees, decision trees, the tree is used.

 

2. Types of Graphs

• Basically graphs are of two types –

1. Directed graphs

2. Undirected graphs.

• In the directed graph the directions are shown on the  edges. As shown in the Fig. 7.1.2, the edges between the vertices are ordered. In this type of graph, the edge E₁ is in between the vertices V₁ and V₂. The V₁ is called head and the V₂ is called the tail. Similarly for V₁ head the tail is V₃ and so on.

• We can say E₁ is the set of (V₁, V₂) and not of (V₂, V₁). ́ ́

• Similarly, in an undirected graph, the edges are not ordered. Refer the Fig. 7.1.3 for clear understanding of undirected graph. In this type of graph the edge E₁ is set of (V₁, V₂) or (V₂, V₁).

• Similarly the object shown in the Fig. 7.1.4 is a multi‒graph.

 

3. Properties of Graph

1) Complete graph :

If an undirected graph of n vertices consists of   n(n‒1)/2  number of edges then that graph is called a complete graph.

For example : The graph shown in Fig 7.1.5 is a complete graph.

Here n = 4

 e = n(n‒1) / 2 =  4(3) / 2 = 6

Theorem : A complete graph with n vertices has n(n‒1) / 2 number of edges.

Proof : This can be proved by principle of mathematical induction.

Basis of induction : This theorem is true for n = 1 i.e. a graph with single node because when n = 1, total number of edges = 1(1‒1)/2 = 0.

For instance :

• Induction hypothesis : We assume that for k vertices it is true that total number of edges = k(k‒1) / 2

• Inductive step : We have to show that the theorem is also true for (n + 1) vertices.

• Let, G(n) be the graph with n vertices. If we add one more vertex to G(n) then to make this graph complete, we need to add edges to this newly added vertex from all the previous n vertices then total number of edges in G (n + 1) will be

Edges = Edges in G(n) + n = [ n(n‒1) / 2 ] + n = [ n(n‒1)+2n ] / 2

= (n²‒n+2n) / 2 =  (n²+n) / 2

Total edges in G(n + 1) = n(n+1) / 2

If we put n + 1= k then n = k ‒ 1. Hence we can rewrite equation (7.1.1) as

 (k‒1)k / 2   i.e.     k(k−1) / 2

 This is true by induction hypothesis. Hence total number of edges in G (n+1) graph is

[n(n‒1) / 2 ]+ n = [n(n+1)] / 2 is true.

• Thus it is proved by principle of mathematical induction that total number of edges in complete graph is n(n‒1) / 2

2) Subgraph :

A subgraph G' of graph G is a graph such that the set of vertices and set of edges of G' are proper subset of the set of edges of G.

3) Connected graph :

An undirected graph is said to be connected if for every pair of distinct vertices V_i and V_j in V(G) there is an edge V_i to to V_j in G.

Note that there is path from any two vertices.

For example:

• V₁ ‒ V₂

• V₂ ‒ V₁

• V₃ – V₁

• V₄ ‒ V₃ ‒ V₁

• V₁ ‒ V₃

• V₂ ‒ V₁ ‒ V₃

• V₃ ‒ V₁ ‒ V₂

• V₄ – V₂

• V₁ ‒ V₄

• V₂ ‒ V₄

• V₃ ‒ V₄

• V₄ ‒ V₃

Weighted graph

A weighted graph is a graph which consists of weights along its edges.

For example :

Path:

A path is denoted using sequence of vertices and there exists an edge from one vertex to the next vertex.

Cycle :

A closed walk through the graph with repeated vertices, mostly having the same starting and ending vertex is called a cycle.

Component :

The maximal connected subgraph of a graph is called component of a graph.

For example : Following are 3 components of a graph.

In‒degree and out‒degree

• The degree of vertex is the number of edges associated with the vertex.

• In‒degree of a vertex is the number of edges that incident to that vertex. Out‒degree of the vertex is total number of edges that are going away from the vertex.

Self loop :

Self loop is an edge that connects the same vertex, to itself.