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

Salta a la navegació Salta a la cerca
m
cap resum d'edició
m (Suprimida Categoria:Teoria de grafs; Afegida Categoria:Famílies de grafs usant HotCat)
m
{{Polisèmia|Arbre (desambiguació)}}
En [[teoria de grafs]], un ''' arbre ''' és un graf en el qual dos [[Vèrtex (Teoriateoria 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í; 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 ==
 
* '' G '' és [[graf connex|connex]] i no té [[cicle (teoria de grafs)|cicles]] simples.
* '' G '' no té cicles simples i, si s'afegeix alguna [[aresta (teoria de grafs)|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 <math> K_3 </math> no és un [[menor (teoria de grafs)|menor]] de '' G ''.
4.463

modificacions

Menú de navegació