Page 38 - MATINF Nr. 13-14

˘
MATEMATICA PENTRU PROGRAMATORI SI
,
PROGRAMARE PENTRU MATEMATICIENI

Num˘ararea arborilor partiali ai grafului evantai
,

1
Costel B˘alc˘au s , i Doru Constantin 2

ˆ
In acest articol vom aplica Teorema Kirchhoff-Trent pentru a determina num˘arul de arbori
part , iali ai grafului evantai. Folosind propriet˘at , ile determinant , ilor vom obt , ine o relat , ie de
recurent , ˘a, prin rezolvarea c˘areia vom g˘asi formula explicit˘a s , i vom demonstra leg˘atura cu
numerele lui Fibonacci.

Preliminarii

Definit , ia 1. Graful neorientat F n = (V, E) definit prin

V = {1, 2, . . . , n + 1}, E = {[1, i]|i ∈ {2, . . . , n + 1}} ∪ {[i, i + 1]|i ∈ {2, . . . , n}}

∗
se numes , te graful evantai cu n + 1 noduri, unde n ∈ N .
Exemplul 1. Graful evantai F 3 este reprezentat ˆın Figura 1, iar graful evantai F 4 este reprezentat
ˆın Figura 2.

3 4 3 4

2 2 5

1 1

Figura 1 Figura 2

Definit , ia 2. Fie G = (V, E) un graf f˘ar˘a bucle, unde V = {v 1 , . . . , v n }. Matricea de
a
a
admitant , ˘a (matricea Laplacian˘) asociat˘ grafului G este matricea M = (m ij ) i,j=1,n definit˘
a
prin:
m ii = d G (v i ), ∀ i ∈ {1, . . . , n},
m ij = − num˘arul de muchii sau arce dintre nodurile v i s , i v j , ∀ i, j ∈ {1, . . . , n}, i 6= j.
1 Conf. univ. dr., Universitatea Nat , ional˘a de S , tiint , ˘a s , i Tehnologie POLITEHNICA Bucures , ti, Centrul
Universitar Pites , ti, costel.balcau@upb.ro
2
Conf. univ. dr., Universitatea Nat , ional˘a de S , tiint , ˘a s , i Tehnologie POLITEHNICA Bucures , ti, Centrul
Universitar Pites , ti, doru.constantin0804@upb.ro

38