Arbre d'expansió

De Viquipèdia
Dreceres ràpides: navegació, cerca
«Spanning tree» redirigeix aquí. Vegeu-ne altres significats a «Spanning tree (desambiguació)».

Al camp matemàtic de la teoria de grafs, un arbre d'expansió (spanning tree, en anglès) d'un graf connex és un subconjunt de les arestes del graf que és acíclic i connecta tots els vèrtex del graf.

Un arbre d'expansió d'un graf d'ordre n té exactament n-1 arestes.

Un arbre d'expansió d'un graf connex G pot també ésser definit com el conjunt màxim d'arestes de G que no contenen cicles, o com el conjunt mínim d'arestes que connecten tots els vèrtex.