Page 284 - Advanced engineering mathematics

264 CHAPTER 8 Determinants

G v v
v 7 1 2 v
v 6 3
v 5 v 4

FIGURE 8.4 Graph of
Example 8.8.

EXAMPLE 8.8
For the labeled graph of Figure 8.4, T is the 7 × 7matrix

⎛ ⎞
3 −1 0 0 0 −1 −1
−1 3 −1 −1 0 0 0
⎜ ⎟
⎜ ⎟
0 −1 3 −1 0 −1 0
⎜ ⎟
⎜ ⎟
T = ⎜ 0 −1 −1 4 −1 0 −1 .
⎟
⎜ ⎟
0 0 0 −1 3 −1 −1
⎜ ⎟
⎜ ⎟
⎝ −1 0 −1 0 −1 4 −1 ⎠
−1 0 0 −1 −1 −1 4
Evaluate any cofactor of T. For example, deleting row 1 and column 1, evaluate the cofactor

3 −1 −1 0 0 0

−1 3 −1 0 −1 0

−1 −1 4 −1 0 −1
1+1

(−1) M 11 = = 386.
0 0 −1 3 −1 −1

0 −1 0 −1 4 −1

0 0 −1 −1 −1 4
Even with this small graph in Example 8.8, it would clearly be impractical to enumerate the
spanning trees by listing them all.
SECTION 8.6 PROBLEMS

1. Find the number of spanning trees in the graph of 2. Find the number of spanning trees in the graph of
Figure 8.5. Figure 8.6.
1
1 6
2 5 2

3 4 3 4 5

FIGURE 8.5 Graph FIGURE 8.6 Graph
of Problem 1, of Problem 2,
Section 8.6. 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-264 27410_08_ch08_p247-266