Page 270 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 13: Graphs

13.1 Defi ning Graph Notes

A Graph G consists of a set V of vertice (nodes) and a set E of edges (arcs). We write G=(V,E). V

is a finite and non empty set of vertices. E is a set of pairs of vertices; these pairs are called edges.
Therefore
V(G), read as V of G, is set of vertices,
and E(G), read as E of G, is set of edges.
An edge e = (v,w), is a pair of vertices v and w, and is said to be incident with v and w.
A graph may be pictorically represented as given in Figure 13.1.

Figure 13.1: A Graph

1

2 5

3 4

We have numbered the nodes as 1,2,3,4 and 5. Therefore
V(G) = (1, 2, 3, 4, 5)

and E(G) = {(1, 2), (2, 3), (3, 4), (4, 5), (1, 5), (1, 3), (3, 5)}
You may notice that the edge incident with node 1 and node 5 is written as (1,5); we could also
have written (5,1) instead of (1,5). The same applies to all the other edges. Therefore, we may say

that ordering of vertices is not significant here. This is true for an undirected graph.
In an undirected graph, pair of vertices representing any edge is unordered. Thus (v,w) and (w,v)
represent the same edge. In a directed graph each edge is an ordered pair of vertices, i.e. each
edge is represented by a directed pair. If e = (v,w), then v is tail or initial vertex and w is head or

final vertex. Subsequently (v,w) and (w,v) represent two different edges.
A directed graph may be pictorically represented as given in Figure 13.2.

LOVELY PROFESSIONAL UNIVERSITY 265