Page 272 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 13: Graphs

Find out the vertices adjacent to remaining nodes of the graph. Notes

Path: A path from vertex v to vertex w is a sequence of vertices, each adjacent to the next.
Consider the above example again. 1,3,4 is a path
1,3,6 is a path
1,2,7 is a path,
Is 1,4,7 a path?
How many paths are there from vertex 1 to vertex 7?
You may notice that there is a path existing in the above example which starts at vertex 1 and

finishes at vertex 1, i.e. path 1,3,4,7,2,1. Such a path is called a cycle.

A cycle is a path in which first and last vertices are the same.
DO we have a path from any vertex to any other vertex in the above example? If you see it
carefully, you may find the answer to the above question as YES. Such a graph is said to be

connected graph. A graph is called connected if there exists a path from any vertex to any other
vertex. There are graphs which are unconnected. Consider the graph in Figure 13.4.
Figure 13.4: An Unconnected Graph

1 6

2 3 7 8

4

5

It is an unconnected graph. You may say that these are two graphs and not one. Look at the fi gure

in its totality and apply the definition of graph. Does it satisfy the definition of a graph? It does.

Therefore, it is one graph having two unconnected components. Since there are unconnected
components, it is an unconnected graph.
So far we have talked of paths, cycles and connectivity of undirected graph. In a Digraph the path
is called a directed path and a cycle as directed cycle.
Figure 13.5: A Digraph

1 4 6

2 3 5 7

LOVELY PROFESSIONAL UNIVERSITY 267