Page 41 - MATINF Nr. 13-14

Num˘ararea arborilor part , iali ai grafului evantai 41

a
Fie n ≥ 3. Matricea de admitant , ˘ a grafului F n este

 
n −1 −1 −1 . . . −1 −1 −1
 −1 2 −1 0 . . . 0 0 0 
 
−1 −1 3 −1 . . . 0 0 0
 
 
−1 0 −1 3 . . . 0 0 0
 
M =  
. . . . . .
 
 
 −1 0 0 0 . . . 3 −1 0 
 
 −1 0 0 0 . . . −1 3 −1 
−1 0 0 0 . . . 0 −1 2
a
(matrice (n + 1) × (n + 1) avˆand diagonala principal˘ n, 2, 3, . . . , 3, 2), deci conform Teoremei 1
| {z }
n−2
avem
2 −1 0 0 . . . 0 0 0

−1 3 −1 0 . . . 0 0 0

0 −1 3 −1 . . . 0 0 0

t n = det[M] 11 = . . . . . .

0 0 0 0 . . . 3 −1 0

0 0 0 0 . . . −1 3 −1

0 0 0 0 . . . 0 −1 2

(determinant de ordin n avˆand diagonala principal˘a 2, 3, . . . , 3, 2).
| {z }
n−2
Dezvoltˆand determinantul dup˘a linia 1, obt , inem

3 −1 0 . . . 0 0 0 −1 −1 0 . . . 0 0 0

−1 3 −1 . . . 0 0 0 0 3 −1 . . . 0 0 0

. . . . . . . . . . . .

t n = 2 · +
0 0 0 . . . 3 −1 0 0 0 0 . . . 3 −1 0

0 0 0 . . . −1 3 −1 0 0 0 . . . −1 3 −1

0 0 0 . . . 0 −1 2 0 0 0 . . . 0 −1 2

(determinant , i de ordin n − 1), deci dezvoltˆand ultimul determinant dup˘ coloana 1, obt , inem c˘
a
a
t n = 2x n−1 − x n−2 , (2)
unde, pemtru orice n ≥ 1,

3 −1 0 0 . . . 0 0 0

−1 3 −1 0 . . . 0 0 0

0 −1 3 −1 . . . 0 0 0

x n = . . . . . .

0 0 0 0 . . . 3 −1 0

0 0 0 0 . . . −1 3 −1

0 0 0 0 . . . 0 −1 2
(determinant de ordin n avˆand diagonala principal˘ 3, . . . , 3, 2).
a
| {z }
n−1