Page 189 - DCAP407_DATA_STRUCTURE

Data Structure

Figure 10.5 shows a graph with arcs.

Figure 10.5: A Graph

An arc is an ordered pair of vertices. In figure 8.5, the arcs are (a,b) and (b,c). In the arc (a, b), a is called
the tail of the arc and b is called the head of the arc. Similarly, in the arc (b,c), b is called the tail of the
arc and c is called the head of the arc. If (a,b) is a directional arc, then (a,b) is not equal to (b,a).
In figure 10.5, Vertices (V) = {a, b, c} and Arcs (E) = {(a,b), (b,c)}
The vertices of the graph are used to represent objects and the arcs are used to represent the relationship
between the objects.
10.1.2 Types of Graphs

A graph consists of a set of vertices and edges/arcs.
Graph (G) = (V, E); where V represents vertices and E represents edges/arcs.
Vertices are also known as nodes.
The three types of graphs are:
1. Directed graphs

2. Undirected graphs
3. Mixed graphs
Directed Graphs
A graph in which each edge is assigned a direction is called a directed graph.
The figure 10.6 shows a directed graph. Directed arcs connect the nodes.

Figure 10.6: A Directed Graph

A directed graph (G) consists of vertices (V) and a set of arcs (E). Directed graphs are also known as
digraphs. In a tree, the nodes are considered as vertices and the directed lines are considered as arcs.

182 LOVELY PROFESSIONAL UNIVERSITY