Viquipèdia

Arbre (teoria de grafs): diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
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ó.
Línia 1:
{{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 ==
Línia 21:
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]].
Línia 39:
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>
Linha 47 ⟶ 45:
 
 
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
Obtingut de «https://ca.wikipedia.org/wiki/Arbre_(teoria_de_grafs)»