Page 39 - MATINF Nr. 13-14

Num˘ararea arborilor part , iali ai grafului evantai 39

a
Observat ,ia 1. Dac˘ graful G este neorientat, atunci

M = D − A,

a
unde A este matricea de adiacent , ˘ s , i D este matricea gradelor (d ii = d G (v i ), ∀ i ∈ {1, . . . , n} s , i
d ij = 0, ∀ i, j ∈ {1, . . . , n}, i 6= j).

Exemplul 2. Matricea de admitant , ˘ a grafului evantai F 3 , reprezentat ˆın Figura 1, este
a
Ü ê
3 −1 −1 −1
−1 2 −1 0
M = ,
−1 −1 3 −1
−1 0 −1 2

a
iar matricea de admitant , ˘ a grafului evantai F 4 , reprezentat ˆın Figura 2, este
à í
4 −1 −1 −1 −1
−1 2 −1 0 0
M = −1 −1 3 −1 0 .
−1 0 −1 3 −1
−1 0 0 −1 2

Observat ,ia 2. Matricea de admitant , ˘a este o matrice simetric˘a (s , i pentru grafuri orientate!) s , i
are toate sumele pe linii s , i pe coloane egale cu zero.
Observat ,ia 3. Definit , ia 2 se poate extinde s , i pentru grafuri cu bucle, considerˆand drept matrice
de admitant , ˘a a unui astfel de graf matricea de admitant , ˘a a grafului obt , inut prin eliminarea
tuturor buclelor.

Teorema 1 (Kirchoff-Trent, de num˘arare a arborilor part , iali, Matrix Tree Theorem).
a
a
Fie G = (V, E) un graf f˘ar˘ bucle avˆand matricea de admitant ,˘ M = (m ij ) , n ≥ 2. Atunci
i,j=1,n
a
num˘arul t(G) de arbori part ,iali ai grafului G verific˘ egalitatea
t(G) = (−1) i+j det[M] ij , ∀ i, j ∈ {1, . . . , n},

a
a
unde [M] ij reprezint˘ matricea obt ,inut˘ din M prin eliminarea liniei i s , i coloanei j.

O demonstrat , ie a acestei teoreme poate fi g˘asit˘a, de exemplu, ˆın [1].

a
a
Observat ,ia 4. Teorema anterioar˘ este valabil˘ s , i pentru grafuri cu bucle, folosind Observat , ia 3.
a
Exemplul 3. Aplicˆand teorema anterioar˘ rezult˘ c˘ num˘arul arborilor part , iali ai grafului evantai
a
a
F 3 este

2 −1 0

t(F 3 ) = det[M] 11 = −1 3 −1 = 12 + 0 + 0 − 0 − 2 − 2 = 8.

0 −1 2
Cei 8 arbori part , iali sunt: