Arbre (teoria de grafs): diferència entre les revisions
| Línia 35: | Línia 35: | ||
== Propietats == |
== 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 |
Tot arbre és, alhora, un [[graf bipartit]]. Tot arbre amb només un [[conjunt comptable]] de vèrtexs és a més un [[graf pla]]. |
||
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 ''. |
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 ''. |
||
Revisió del 07:04, 31 març 2010
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 de 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 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 es recible 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è tots 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 cada vèrtex ha estat designat arrel , i en aquest cas les arestes tenen una orientació natural cap o Des de l'arrel. Els arbres amb arrel, sovint amb estructures addicionals com a ordre dels veïns de cada vèrtex, són una estructura clau en informàtica; vegeu arbre (programació).
Un arbre etiquetatge és un arbre en el qual cada vèrtex té una única etiqueta. Els vèrtexs d'un arbre etiquetatge 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.
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 pla.
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 .
Atès n vèrtexs etiquetats, hi ha n n -2 maneres diferents de connectar per construir un graf. El resultat s'anomena fórmula de Cayley.
El nombre d'arbres amb n vèrtexs de grau d 1 , d 2 ,..., d n és:
que és un coeficient multinomial.
No es coneix fórmula per al número t ( n ) d'arbres amb n vèrtexs d'un isomorfisme de grafs.
Tanmateix, el comportament asimptòtic d ' t ( n ) es coneix; hi ha números α ≈ 3 i
β ≈ 0,5 tals que
