Page 271 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Figure 13.2: A Directed Graph

1

2 5

3 4

The direction is indicated by an arrow. The set of vertices for this graph remains the same as that
of the graph in the earlier example, i.e.
V(G) = (1,2,3,4,5}
However the set of edges would be

E(G) = {(1,2), (2,3), (3,4), (5,4), (5,1), (1,3), (5,3)}
Do you notice the difference?

Note Arrow is always from tail vertex to head vertex. In our further discussion on
graphs, we would refer to directed graph as digraph and undirected graph as graph.

13.2 Basic Graph Terminology

A good deal of nomenclature is associated with graphs. Most of the terms have straight foward

definitions, and it is convenient to put them in one place even though we would not be using
some of them until later.
Adjacent Vertices

Vertex v is said to be adjacent to a vertex v if there is an edge
1 2
(v , v ) or (v , v )
1 2 2 1
Figure 13.3

1

3 2

5 6 4 7

Vertices adjacent to node 3 are 1,5,6 and 4 and that to node 2 are 1 and 7.

266 LOVELY PROFESSIONAL UNIVERSITY