Analysis of Algorithms : An Active Learning Approach

6.1 GRAPH BACKGROUND AND TERMINOLOGY 145

After this section, we will specify graphs by drawing them instead of giving

these sets. In our drawings, we will use circles to represent the nodes of the

graph and lines connecting the circles to represent the edges. We will put the

node labels inside the circles. If we want to represent a directed graph, we will

use arrows to show the direction the edge can be traveled. Figure 6.1 shows the

drawing of a graph (Fig. 6.1(a)) and directed graph (Fig. 6.1(b)) with their for-

mal set definitions.

■ 6.1.1 Terminology

A complete graph is a graph with an edge between every pair of nodes. If there

are N nodes, there will be (N^2 
N) / 2 edges in a complete graph without

loop edges. A complete digraph is a digraph with an edge allowing traversal

between every pair of nodes. Because the edges of a graph allow travel in two

directions, whereas a digraph’s edges allow travel in only one, a digraph with N

nodes will have twice as many edges, specifically N^2 
N.

A subgraph (Vs,Es) of a graph or digraph (V,E) is one that has a subset of

the vertices (Vs⊆V) and edges (Es⊆E) of the full graph.

A path between two nodes of a graph or digraph is a sequence of edges that

can be traveled consecutively. In other words, a path between node A and node

B would begin at node A and traverse a set of edges until node B was reached.

Formally, we say that a path from node vi to vj is the sequence of edges vivi+1,

vi+1vi+2,... , vj
 1 vj that are in the graph. We require that all of the nodes along

this path be unique. A path is said to have a length that represents the number

of edges that make up the path. The path AB, BC, CD, DE has length 4.

1 2

5

3

4

1 2

3

4

5

■FIGURE 6.1A
The graph G = ({1, 2, 3, 4, 5}, {{1, 2},
{1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}})

■FIGURE 6.1B

The directed graph G = ({1, 2, 3, 4, 5}, {(1, 2),

(1, 3), (2, 1), (3, 2), (4, 3), (4, 5),

(5, 2), (5,4)})