Page 285 - Advanced engineering mathematics
P. 285
8.6 The Matrix Tree Theorem 265
3. Find the number of spanning trees in the graph of 5. Find the number of spanning trees in the graph of
Figure 8.7. Figure 8.9.
1
2 2
1
6 3
3
5 4
4 6 5
FIGURE 8.7 Graph FIGURE 8.9 Graph
of Problem 3, of Problem 5,
Section 8.6. Section 8.6.
4. Find the number of spanning trees in the graph of 6. A complete graph on n points consists of n points, with
Figure 8.8. a line between each pair of points. This graph is often
denoted K n . With the points labeled 1,2,··· ,n,show
1 2 that the number of spanning trees in K n is n n−2 for
6 n = 3,4,···.
3
5
4
FIGURE 8.8 Graph
of Problem 4,
Section 8.6.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
October 14, 2010 14:26 THM/NEIL Page-265 27410_08_ch08_p247-266
