Introduction to Graph Theory
335
regular graph is n-regular if each vertex has degree n. Graphs that are 3-regular are often
called cubic graphs.
Some examples of complete graphs and regular graphs are shown in Figure 6.5.
K,
K 2
K 3
K 4
K 5
2-regular
3-regular
4-regular
Figure 6.5 Complete and regular graphs.
Another family of graphs that are used in matching problems, resource allocation problems, and computer architecture modeling is the family of bipartite graphs.
Definition 3. Let G = (V, E) be a graph. G is a bipartite graph if its vertex set V
can be partitioned into two nonempty disjoint subsets V 1 and V 2 , called a bipartition, so
that each edge has one end in V 1 and one end in V 2 . A complete bipartite graph is a
bipartite graph with bipartition V1 and V 2 in which each vertex of V 1 is joined by an edge
to each vertex of V 2 . A complete bipartite graph with I V1i = m and I V 2 I = n is denoted
as Km,n.
Examples of bipartite graphs and the bipartitions they determine are shown in
Figure 6.6.
V,
V2
1
4
4
1•
2
56
2•
x2 *
4
3
6
3
7
K 2 , 2
K 3 ,3
K 3 ,4
V 1 and V 2
V = 1 {1,2}
V 1 = {1, 2,3}
V 1 = {1, 2,31
forma
V 2 = {3,4)
V 2 = {4,5,6}
V 2 = {4, 5, 6, 71
bipartition
Figure 6.6 Bipartition and complete bipartite graphs.