Diferència entre revisions de la pàgina «Arbre (teoria de grafs)»

m
Corregit un error matemàtic i alguns errors de llenguatge deguts a la traducció.
m (Robot esborra: zh:树 (图 论) (missing), ru:Дерево (strongly connected to ca:Arbre), sv:Trad (graf) (missing), it:Albero (graf) (missing), th:ต้นไม้ (ทฤษฎี กราฟ) (missing))
m (Corregit un error matemàtic i alguns errors de llenguatge deguts a la traducció.)
{{Polisèmia|Arbre (desambiguació)}}
En [[teoria de grafs]], un ''' arbre ''' és un graf en el qual dos [[Vèrtex (Teoria de grafs)|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í.; Unauna 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 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 dde ''' arbre amb arrel '' si cadahi ha un vèrtex que ha estat designat com a '' arrel '', i. enEn aquest cas les arestes tenen una orientació natural '' cap '' o '' Desdes de '' l'arrel. Els arbres amb arrel, sovint amb estructures addicionals com a l'ordre dels veïns de cada vèrtex, són unaestructures de estructuradades clau en informàtica; vegeu [[arbre (programació)]].
 
Un '' arbre etiquetatgeetiquetat '' és un arbre en el qual cada vèrtex té una única etiqueta. Els vèrtexs d'un arbre etiquetatgeetiquetat 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 (teoria de grafs)|grau]]. Vegeu [[graf regular]].
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èsDonats '' n '' vèrtexs etiquetats, hi ha '' n '' <sup> '' n '' -2 </sup> maneres diferents de connectar-los per a construir un graf.; Elaquest 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''<sub>1</sub>, ''d''<sub>2</sub>,...,''d''<sub>n</sub> és:
 
El nombre d'arbres amb '' n '' vèrtexs de grau '' d '' <sub> 1 </sub>, '' d '' <sub> 2 </sub >,..., '' d '' <sub> n </sub> és:
 
: <math>{N-2 \choose d_1-1, d_2-1, \ldots, d_n-1}, </math>
 
 
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]] d ''' t '' ('' n '') es coneix; hi ha números α ≈ 3 i
β ≈ 0,5 tals que
5

modificacions