Arbre (teoria de grafs)

Per a altres significats, vegeu «Arbre (desambiguació)».

En teoria de grafs, un arbre és un graf en el qual dos vèrtexs estan connectats per exactament un camí. Un bosc és un graf en el qual dos vèrtexs qualsevol estan connectats per com a màxim un camí; una definició equivalent és que un bosc és una unió disjunta d'arbres (d'aquí el nom). Un arbre de vegades rep el nom d'arbre lliure .

Definicions

Un arbre és un graf simple unidireccional G que satisfà alguna de les següents condicions equivalents:

• G és connex i no té cicles simples.
• G no té cicles simples i, si s'afegeix alguna aresta es forma un cicle simple.
• G és connex i si se li treu alguna aresta deixa de ser connex.
• G és connex i el graf complet de 3 vèrtexs $K_{3}$ no és un menor de G .
• Dos vèrtexs qualsevol G estan connectats per un únic camí simple.

Si G té molts vèrtexs, n , llavors les definicions anteriors són també equivalents a qualsevol de les següents condicions:

• G és connex i té n - 1 arestes.
• G no té arestes simples i té n - 1 arestes.
• La quantitat de fulles d'un arbre sempre és major o igual a la meitat de la totalitat dels nodes

En gràfic unidireccional simple G rep el nom de bosc si no té cicles simples.

Un arbre dirigit és un graf dirigit que seria un arbre si no es consideraran les adreces de les arestes. Alguns autors restringeixen la frase al cas en què totes les arestes es dirigeixen a un vèrtex particular, o totes les seves adreces parteixen d'un vèrtex particular.

Un arbre rep el nom d'arbre amb arrel si hi ha un vèrtex que ha estat designat com a arrel . En aquest cas les arestes tenen una orientació natural cap o des de l'arrel. Els arbres amb arrel, sovint amb estructures addicionals com l'ordre dels veïns de cada vèrtex, són estructures de dades clau en informàtica; vegeu arbre (programació).

Un arbre etiquetat és un arbre en el qual cada vèrtex té una única etiqueta. Els vèrtexs d'un arbre etiquetat de n vèrtexs reben normalment les etiquetes {1,2, ..., n}.

Un arbre regular ( homogeni ) és un arbre en el qual cada vèrtex té el mateix grau. Vegeu graf regular.

Un arbre etiquetat amb 6 vèrtexs i 5 arestes

Exemple

En arbre d'exemple mostrat a la dreta té 6 vèrtexs i 6 - 1 = 5 arestes. L'únic camí simple que connecta els vèrtexs 2 i 6 és 2-4-5-6.

Propietats

Tot arbre és, alhora, un graf bipartit. Tot arbre amb només un conjunt comptable de vèrtexs és a més un graf planar.

Tot graf connex G admet un arbre de cobertura, que és un arbre que conté cada vèrtex de G i les arestes són arestes de G .

Donats n vèrtexs etiquetats, hi ha n^{n -2} maneres diferents de connectar-los per a construir un graf; aquest resultat s'anomena fórmula de Cayley. Per a demostrar-la es prova primer que el nombre d'arbres amb n vèrtexs etiquetats i de graus respectivament d₁, d₂,...,d_n és:

${N-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1},$

que és un coeficient multinomial.

No es coneix cap fórmula per al número t ( n ) d'arbres amb n vèrtexs d'un isomorfisme de grafs. Tanmateix, el comportament asimptòtic de t ( n ) es coneix; hi ha números α ≈ 3 i β ≈ 0,5 tals que

$\lim _{n\to \infty }{\frac {t(n)}{\beta \alpha ^{n}n^{-5/2}}}=1.$

Vegeu també

• Arbre (programació)

Viccionari