Section 6.1 Graphs and Their Representations
487
3. One graph has parallel arcs and the other does not.
4. One graph has a loop and the other does not.
5. One graph has a node of degree k and the other does not.
6. One graph is connected and the other is not.
7. One graph has a cycle and the other does not.
praCTiCe 9 Prove that the two graphs in Figure 6.19 are not isomorphic.
Figure 6.19
■
Again, graphs that are isomorphic are considered to be “the same” regardless of
cosmetic differences in how they are drawn or labeled, whereas nonisomorphic
graphs have fundamental structural differences.
planar Graphs
A planar graph is one that can be represented (on a sheet of paper, that is, in
the plane) so that its arcs intersect only at nodes. Designers of integrated circuits
want all components in one layer of a chip to form a planar graph so that no connections cross. The graph of Figure 6.14 is clearly planar. However, we know that
it is isomorphic to the graph of Figure 6.15, so the graph of Figure 6.15 is also
planar. The key word in the definition of a planar graph is that it can be drawn in
a certain way.
example 12
The two graphs of Figure 6.20 are not isomorphic. Note that each graph has six
nodes and seven arcs. Neither has parallel arcs or loops. Both are connected. Both
have three cycles, four nodes of degree 2, and two nodes of degree 3. Therefore
none of the obvious nonisomorphism tests apply. However, the graph in Figure
6.20b has a node of degree 2 that is adjacent to two nodes of degree 3; this is not
the case in Figure 6.20a, so the graphs are not isomorphic.
(a)
(b)
Figure 6.20
praCTiCe 10 Prove that K 4 is a planar graph.
■
487
3. One graph has parallel arcs and the other does not.
4. One graph has a loop and the other does not.
5. One graph has a node of degree k and the other does not.
6. One graph is connected and the other is not.
7. One graph has a cycle and the other does not.
praCTiCe 9 Prove that the two graphs in Figure 6.19 are not isomorphic.
Figure 6.19
■
Again, graphs that are isomorphic are considered to be “the same” regardless of
cosmetic differences in how they are drawn or labeled, whereas nonisomorphic
graphs have fundamental structural differences.
planar Graphs
A planar graph is one that can be represented (on a sheet of paper, that is, in
the plane) so that its arcs intersect only at nodes. Designers of integrated circuits
want all components in one layer of a chip to form a planar graph so that no connections cross. The graph of Figure 6.14 is clearly planar. However, we know that
it is isomorphic to the graph of Figure 6.15, so the graph of Figure 6.15 is also
planar. The key word in the definition of a planar graph is that it can be drawn in
a certain way.
example 12
The two graphs of Figure 6.20 are not isomorphic. Note that each graph has six
nodes and seven arcs. Neither has parallel arcs or loops. Both are connected. Both
have three cycles, four nodes of degree 2, and two nodes of degree 3. Therefore
none of the obvious nonisomorphism tests apply. However, the graph in Figure
6.20b has a node of degree 2 that is adjacent to two nodes of degree 3; this is not
the case in Figure 6.20a, so the graphs are not isomorphic.
(a)
(b)
Figure 6.20
praCTiCe 10 Prove that K 4 is a planar graph.
■