482
Graphs and Trees
graphs have no parallel arcs. A complete graph is one in which any two distinct
nodes are adjacent. In this case, g is almost an onto function—every pair x–y of
distinct nodes is the image under g of an arc—but there does not have to be a loop at
every node. Consequently, pairs of the form x–x need not have a preimage.
A subgraph of a graph consists of a set of nodes and a set of arcs that are subsets of the original node set and arc set, respectively, in which the endpoints of an
arc must be the same nodes as in the original graph. In other words, it is a graph
obtained by erasing part of the original graph and leaving the rest unchanged.
Figure 6.10 shows two subgraphs of the graph in Figure 6.3. Note that the graph in
Figure 6.10a is simple and also complete.
1
3
a 1
2
a 2
a 3
a 5
1
3
a 1
a 4
2
a 5
(a)
(b)
Figure 6.10
A path from node n 0 to node n k is a sequence
n 0 , a 0 , n 1 , a 1 , … , n k−1 , a k−1 , n k
of nodes and arcs where for each i, the endpoints of arc a i are n i –n i+1 . In the
graph of Figure 6.3, one path from node 2 to node 4 consists of the sequence
2, a l , 1, a 2 , 2, a 4 , 3, a 6 , 4. The length of a path is the number of arcs it contains; if
an arc is used more than once, it is counted each time it is used. The length of the
path just described from node 2 to node 4 is 4.
A graph is connected if there is a path from any node to any other node. The
graphs in Figure 6.10 are each connected, but the graph of Figure 6.3 is not connected. A cycle in a graph is a path from some node n 0 back to n 0 where no arc
appears more than once in the path sequence, n 0 is the only node appearing more
than once, and n 0 occurs only at the ends. (Nodes and arcs may be repeated in a
path but not, except for node n 0 , in a cycle.) In the graph of Figure 6.3,
1, a 1 , 2, a 4 , 3, a 5 , 1
is a cycle. A graph with no cycles is acyclic.
praCTiCe 3 Refer to the graph created in Practice 1.
a. Find two nodes that are not adjacent.
b. Find a node adjacent to itself.
c. Find a loop.
d. Find two parallel arcs.
e. Find the degree of node 3.
f. Find a path of length 5.
g. Find a cycle.
h. Is this graph complete?
i. Is this graph connected?
■
Graphs and Trees
graphs have no parallel arcs. A complete graph is one in which any two distinct
nodes are adjacent. In this case, g is almost an onto function—every pair x–y of
distinct nodes is the image under g of an arc—but there does not have to be a loop at
every node. Consequently, pairs of the form x–x need not have a preimage.
A subgraph of a graph consists of a set of nodes and a set of arcs that are subsets of the original node set and arc set, respectively, in which the endpoints of an
arc must be the same nodes as in the original graph. In other words, it is a graph
obtained by erasing part of the original graph and leaving the rest unchanged.
Figure 6.10 shows two subgraphs of the graph in Figure 6.3. Note that the graph in
Figure 6.10a is simple and also complete.
1
3
a 1
2
a 2
a 3
a 5
1
3
a 1
a 4
2
a 5
(a)
(b)
Figure 6.10
A path from node n 0 to node n k is a sequence
n 0 , a 0 , n 1 , a 1 , … , n k−1 , a k−1 , n k
of nodes and arcs where for each i, the endpoints of arc a i are n i –n i+1 . In the
graph of Figure 6.3, one path from node 2 to node 4 consists of the sequence
2, a l , 1, a 2 , 2, a 4 , 3, a 6 , 4. The length of a path is the number of arcs it contains; if
an arc is used more than once, it is counted each time it is used. The length of the
path just described from node 2 to node 4 is 4.
A graph is connected if there is a path from any node to any other node. The
graphs in Figure 6.10 are each connected, but the graph of Figure 6.3 is not connected. A cycle in a graph is a path from some node n 0 back to n 0 where no arc
appears more than once in the path sequence, n 0 is the only node appearing more
than once, and n 0 occurs only at the ends. (Nodes and arcs may be repeated in a
path but not, except for node n 0 , in a cycle.) In the graph of Figure 6.3,
1, a 1 , 2, a 4 , 3, a 5 , 1
is a cycle. A graph with no cycles is acyclic.
praCTiCe 3 Refer to the graph created in Practice 1.
a. Find two nodes that are not adjacent.
b. Find a node adjacent to itself.
c. Find a loop.
d. Find two parallel arcs.
e. Find the degree of node 3.
f. Find a path of length 5.
g. Find a cycle.
h. Is this graph complete?
i. Is this graph connected?
■