Arbre d'expansió
From Wikipedia, the free encyclopedia
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èrtexs del graf. En general, un graf pot tenir més d'un arbre d'expansió, però un graf que no sigui connex no pot contenir cap arbre d'expansió. Si totes les arestes de G són també arestes d'un arbre d'expansió T de G, llavors G és un arbre i és idèntic a T (és a dir, un arbre té un únic arbre d'expansió i és el mateix graf).
«Spanning tree» redirigeix aquí. Vegeu-ne altres significats a «Spanning tree (desambiguació)». |
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èrtexs.