484
Graphs and Trees
We can prove some (fairly trivial) statements about graphs that follow directly
from the definitions.
example 9
In the directed graph of Figure 6.13, there are many paths from node 1 to node 3:
1, a 4 , 3 and 1, a 1 , 2, a 2 , 2, a 2 , 2, a 3 , 3 are two possibilities. Node 3 is certainly
reachable from 1. Node 1, however, is not reachable from any other node. The
cycles in this graph are the loop a 2 and the path 3, a 5 , 4, a 6 , 3.
1
3
4
a 7
2
a 2
a 3
a 1
a 4 a 5
a 6
Figure 6.13
example 10
Prove that an acyclic graph is simple.
We’ll use a proof by contraposition. If a graph is not simple, it has either
parallel arcs or a loop. The parallel arcs and their endpoints, or the loop and its
endpoints, then constitute a cycle, and the graph is not acyclic.
Note that the converse to the statement in Example 10 is not true: Figure 6.10a
is a simple graph, but it contains a cycle.
praCTiCe 6
a. Prove that every complete graph is connected.
b. Find a connected graph that is not complete.
■
isomorphic Graphs
Two graphs may appear quite different in their visual representation but still be the
same graph according to our formal definition. We want to distinguish between
two graphs that have cosmetic visual differences and those that have fundamentally different structures. The graphs in Figures 6.14 and 6.15 are the same—they
have the same nodes, the same arcs, and the same arc-to-endpoint function. (In
a representation of a graph, arcs can intersect at points that are not nodes of the
graph.) The graph in Figure 6.16 is essentially the same graph as well. If we relabeled the nodes and arcs of the graph of Figure 6.14 by the following mappings,
the graphs would be the same:
f 1 :1 S a
f 2 : a 1 S e 2
2 S c
a 2 S e 1
3 S b
4 S d
Graphs and Trees
We can prove some (fairly trivial) statements about graphs that follow directly
from the definitions.
example 9
In the directed graph of Figure 6.13, there are many paths from node 1 to node 3:
1, a 4 , 3 and 1, a 1 , 2, a 2 , 2, a 2 , 2, a 3 , 3 are two possibilities. Node 3 is certainly
reachable from 1. Node 1, however, is not reachable from any other node. The
cycles in this graph are the loop a 2 and the path 3, a 5 , 4, a 6 , 3.
1
3
4
a 7
2
a 2
a 3
a 1
a 4 a 5
a 6
Figure 6.13
example 10
Prove that an acyclic graph is simple.
We’ll use a proof by contraposition. If a graph is not simple, it has either
parallel arcs or a loop. The parallel arcs and their endpoints, or the loop and its
endpoints, then constitute a cycle, and the graph is not acyclic.
Note that the converse to the statement in Example 10 is not true: Figure 6.10a
is a simple graph, but it contains a cycle.
praCTiCe 6
a. Prove that every complete graph is connected.
b. Find a connected graph that is not complete.
■
isomorphic Graphs
Two graphs may appear quite different in their visual representation but still be the
same graph according to our formal definition. We want to distinguish between
two graphs that have cosmetic visual differences and those that have fundamentally different structures. The graphs in Figures 6.14 and 6.15 are the same—they
have the same nodes, the same arcs, and the same arc-to-endpoint function. (In
a representation of a graph, arcs can intersect at points that are not nodes of the
graph.) The graph in Figure 6.16 is essentially the same graph as well. If we relabeled the nodes and arcs of the graph of Figure 6.14 by the following mappings,
the graphs would be the same:
f 1 :1 S a
f 2 : a 1 S e 2
2 S c
a 2 S e 1
3 S b
4 S d