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
mCap resum de modificació
Línia 1:
{{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 ==
Línia 7:
 
* '' 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 ''.
Obtingut de «https://ca.wikipedia.org/wiki/Arbre_(teoria_de_grafs)»