Section 6.1 Graphs and Their Representations
483
Now consider the simple graph in Figure 6.12. It is not a complete graph
because it is not true that every node is adjacent to every other node. However,
the nodes can be divided into two disjoint sets, 51, 26 and 53, 4, 56, such that
any two nodes chosen from the same set are not adjacent but any two nodes
chosen one from each set are adjacent. Such a graph is a bipartite complete
graph.
3
4
1
2
5
Figure 6.12
ExamplE 8
Figure 6.11 illustrates the simple, complete graphs with 1, 2, 3, and 4 vertices. The
simple, complete graph with n vertices is denoted by K n .
K 1
K 2
K 3
K 4
Figure 6.11
Practice 4 Draw K 5 .
■
Practice 5 Draw K 3,3 .
■
The concept of a path extends to a directed graph, as we might expect: A path
from node n 0 to node n k in a directed graph is a sequence
n 0 , a 0 , n 1 , a 1 , … , n k−1 , a k−1 , n k
where for each i, n i is the initial point and n i+1 is the terminal point of a i . If a path
exists from node n 0 to node n k , then n k is reachable from n 0 . The definition of a
cycle also carries over to directed graphs.
DEfinition Bipartite Complete Graph
A graph is a bipartite complete graph if its nodes can be partitioned into two disjoint nonempty sets N 1 and N 2 such that two nodes x and y are adjacent if and only
if x [ N 1 and y [ N 2 . If 0 N 1 0 = m and 0 N 2 0 = n, such a graph is denoted by K m,n .
Figure 6.12 therefore illustrates K 2,3 .