Arbre d'expansió
De Viquipèdia
(S'ha redirigit des de: Spanning tree)
 |
«Spanning tree» redirigeix aquí. Vegeu 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.
  |
Aquest article és un esborrany sobre matemàtiques. Podeu ajudar la Viquipèdia ampliant-lo. |
