miniatura|Un arbre d'expansió (amb les arestes en ) d'un graf 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).
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.
Aplicacions Diversos algorismes de cerca de ruta, inclosos l'algorisme de Dijkstra i l'algorisme de cerca A*, construeixen internament un arbre d'expansió com a pas intermedi a l'hora de trobar la solució del problema.
Per tal de minimitzar el cost de les xarxes d'electricitat, connexions de cable, reconeixement automàtic de veu, etc. hom utilitza algorismes que construeixen un arbre d'expansió de forma gradual (o diversos arbres d'expansió) com a passos intermedis en el procés de trobar l'arbre generador mínim.R. L. Graham and Pavol Hell. "On the History of the Minimum Spanning Tree Problem". 1985.
Internet i moltes altres xarxes de telecomunicacions tenen enllaços de transmissió que connecten nodes en una topologia de xarxa en malla que inclouen alguns cicles. Per tal d'evitar aquests cicles, molts protocols d'encaminament dissenyats per a aquestes xarxes (com per exemple lSpanning Tree Protocol, lOSPF, o el protocol d'estat d'enllaç) requereixen que cada encaminador recordi un arbre d'expansió.
Definicions Un arbre és un graf no dirigit connex sense cicles. Hom diu que és un arbre d'expansió d'un graf G si genera G (és a dir, si conté tots els vèrtexs de G) i és un subgraf de G (és a dir, tota aresta de l'arbre és una aresta de G). També es pot definir un arbre d'expansió d'un graf connex G com el conjunt maximal d'arestes de G que no conté cap cicle, o com el conjunt mínim d'arestes que connecten tots els vèrtexs.
Cicles fonamentals Si s'afegeix una aresta a un arbre d'expansió, s'obté un cicle; hom diu que aquest cicle és un cicle fonamental. Hi ha un cicle fonamental per a cada aresta; així, hi ha una relació unívoca entre els cicles fonamentals i les arestes que no pertanyen a l'arbre d'expansió. Per a un graf connex amb V vèrtexs, qualsevol arbre d'expansió té V − 1 arestes i, per tant, un graf de E arestes i un dels seus arbres d'expansió tenen E − V + 1 cicles fonamentals. Per a qualsevol arbre d'expansió, el conjunt de tots els E − V + 1 cicles fonamentals formen una base de cicles, és a dir, una base de l'espai de cicles., pp. 65–67.
Conjunts de tall fonamentals La noció dual d'un cicle fonamental és el concepte de conjunt de tall fonamental. Si s'elimina només una aresta de l'arbre d'expansió, els vèrtexs queden separats en dos conjunts disjunts. El conjunt de tall fonamental es defineix com el conjunt d'arestes que cal eliminar del graf G per tal d'aconseguir la mateixa partició. Així, tot arbre d'expansió defineix un conjunt de V − 1 conjunts de tall fonamentals, un per a cada aresta de l'arbre d'expansió., pp. 67–69.
La dualitat entre els conjunts de tall fonamentals i els cicles fonamentals s'estableix observant que les arestes del cicle que no pertanyen a l'arbre generador només poden aparèixer en els conjunts de tall de la resta d'arestes del cicle, i viceversa: les arestes d'un conjunt de tall només poden aparèixer en aquells cicles que contenen l'aresta corresponent al conjunt de tall. Aquesta dualitat també es pot expressar emprant la teoria de matroides, segons la qual un arbre d'expansió és una base de la matroide gràfica, un cicle fonamental és l'únic circuit dins del conjunt que està format per addició d'un element a la base, i els conjunts de tall fonamentals estan definits de la mateixa manera a partir de la matroide dual.
Boscos d'expansió En el cas de grafs no connexos, no pot existir un arbre d'expansió, i hom ha de considerar els boscos d'expansió. Existeixen dues definicions alternatives: Alguns autors consideren que un bosc d'expansió és un subgraf acíclic maximal del graf donat, o equivalentment un graf consistent d'un arbre d'expansió en cada component connexa del graf.; Per a altres autors, un bosc d'expansió és un bosc que conté tots els vèrtexs, la qual cosa vol dir que cada vèrtex del graf és un vèrtex del bosc. Per a aquesta definició, fins i tot un graf connex pot tenir un bosc d'expansió no connex, com per exemple el bosc en què cada vèrtex forma un arbre d'un sol vèrtex. Per tal d'evitar confusions entre aquestes definicions, suggereixen el terme "bosc d'expansió complet" per a un bosc d'expansió amb la mateixa connectivitat que el graf inicial, mentre que anomenen aquest tipus de bosc un "bosc d'expansió maximal".;
Nombre d'arbres d'expansió miniatura|La fórmula de Cayley compta el nombre d'arbres d'expansió d'un graf complet. Hi ha 22-2=1 arbres en K₂, 33-2=3 arbres en K₃, i 44-2=16 arbres en K₄. El nombre t(G) d'arbres d'expansió d'un graf connex és un invariant molt estudiat.
Exemples En alguns casos, és senzill calcular directament el valor de t(G): Si G és un arbre, llavors t(G) = 1. Quan G és el graf cicle amb n vèrtexs, llavors t(G) = n. Per a un graf complet amb n vèrtexs, la fórmula de Cayley proporciona el nombre d'arbres d'expansió com nn − 2. Si G és el graf bipartit complet , llavors . Per al graf hipercub n-dimensional , el nombre d'arbres d'expansió és .
En grafs arbitraris
Més en general, donat un graf G qualsevol, hom pot calcular el nombre t(G) en temps polinòmic com el determinant d'una matriu derivada del graf, emprant el teorema de Kirchhoff.
Més específicament, per tal de calcular t(G), hom construeix una matriu quadrada on les files i les columnes estan indexades pels vèrtexs de G. L'entrada de la fila i i la columna j és un d'aquests tres valors: El grau del vèrtex i, si i = j, −1, si els vèrtexs i i j són adjacents, o 0, si els vèrtexs i i j són diferents, però no adjacents. La matriu resultant és singular, de tal manera que el seu determinant és zero. Tot i això, si s'elimina la fila i la columna per a un vèrtex escollit arbitràriament, obtenim una matriu més petita, el determinant de la qual és exactament t(G).
Supressió-contracció Si G és un graf o un multigraf i e és una aresta qualsevol de G, llavors el nombre t(G) d'arbres d'expansió de G satisfà la recurrència supressió-contracció t(G) = t(G − e) + t(G/e), on G − e és el multigraf obtingut mitjançant l'eliminació de e i G/e és la contracció de G per e., p. 109. El terme t(G − e) en aquesta fórmula compta els arbres d'expansió de G que no usen l'aresta e, i el terme t(G/e) compta els arbres d'expansió de G que usen e.
En aquesta fórmula, si el graf donat G és un multigraf, o si la contracció provoca que dos vèrtexs estiguin connectats per més d'una aresta, llavors les arestes redundants no s'han d'eliminar, ja que altrament portaria a un resultat incorrecte.
Polinomi de Tutte El polinomi de Tutte (per William Tutte, matemàtic canadenc) d'un graf es pot definir com la suma, sobre els arbres d'expansió del graf, de termes calculats a partir de l'"activitat interna" i de l'"activitat externa" de l'arbre. El seu valor amb els arguments (1,1) és el nombre d'arbres d'expansió o, en un graf no connex, el nombre de boscos d'expansió maximals., p. 351.
El polinomi de Tutte també es pot calcular emprant una recurrència supressió-contracció, però la seva complexitat computacional és alta: per a molts valors dels seus arguments, la dificultat de calcular-lo exactament és Numeral-P-complet, i també és difícil obtenir-ne una aproximació amb una precisió acceptable. El punt (1,1), en el qual es pot avaluar usant el teorema de Kirchhoff's, és una de les poques excepcions.;
Algorismes Construcció Hom pot trobar un arbre d'expansió d'un graf en temps lineal usant cerca en profunditat o cerca en amplada. Tots dos algorismes exploren el graf donat, començant des d'un vèrtex arbitari, recorrent els veïns dels vèrtexs i afegint cada nou veí a una estructura de dades que s'explora després. Aquests dos algorismes difereixen en si aquesta estructura de dades és una pila (en el cas de la cerca en profunditat) o una cua (en el cas de la cerca en amplada). En qualsevol cas, hom pot formar un arbre d'expansió connectant cada vèrtex, a part del vèrtex arrel v, al vèrtex des del qual s'ha descobert. Hom diu que aquest arbre és un arbre de cerca en profunditat o un arbre de cerca en amplada, depenent de l'algorisme emprat. Els arbres de cerca en profunditat són un cas especial d'una classe d'arbres d'expansió anomenats arbres de Trémaux, anomenats així pel descobridor de la cerca en profunditat el .
Els arbres d'expansió són importants en computació paral·lela i distribuïda, ja que es fan servir per a mantenir les comunicacions entre un conjunt de processadors. Tot i això, els mètodes de cerca en profunditat o de cerca en amplada no són adequats per a computadors paral·lels i distribuïts. En comptes d'això, els investigadors han creat algorismes més especialitzats per tal de trobar arbres d'expansió en aquests models de computació.; ;
Optimització En certs camps de la teoria de grafs és útil trobar un arbre generador mínim d'un graf ponderat. També s'han estudiat altres problemes d'optimització sobre arbres d'expansió, com per exemple l'arbre d'expansió màxim, l'arbre mínim que genera com a mínim k vèrtexs, l'arbre d'expansió amb el menor nombre d'arestes per vèrtex, l'arbre d'expansió amb el major nombre de fulles, l'arbre d'expansió amb el menor nombre de fulles (relacionat amb el problema del camí hamiltonià), l'arbre d'expansió de diàmetre mínim, i l'arbre d'expansió de dilatació mínima.
Els problemes sobre arbres d'expansió òptims han estat objecte d'estudi per a conjunts finits de punts en un espai geomètric com el pla euclidià. En un escenari com aquest, un arbre d'expansió és, de nou, un arbre que té com a vèrtexs els punts donats. La qualitat de l'arbre es mesura de la mateixa forma que en un graf, emprant la distància euclidiana entre parells de punts com el pes per a cada aresta. Així, per exemple, un arbre d'expansió mínim euclidià és el mateix que un arbre d'expansió mínim en un graf complet amb pesos euclidians a les arestes. Tot i això, no és necessari construir aquest graf per tal de resoldre el problema d'optimització; el problema de l'arbre d'expansió mínim euclidià, per exemple, es pot resoldre d'una manera més eficient en temps O(n log n) mitjançant la construcció de la triangulació de Delaunay i després aplicant un algorisme en temps lineal per tal de trobar l'arbre d'expansió mínim sobre un graf planar aplicat a la triangulació resultant.
Aleatorització Un arbre d'expansió escollit a l'atzar d'entre tots els arbres d'expansió amb igual probabilitat s'anomena un arbre d'expansió uniforme. Hom pot utilitzar l'algorisme de Wilson per generar arbres d'expansió uniformes en temps polinòmic, mitjançant la generació d'un camí aleatori sobre el graf, i després eliminant els cicles creats pel camí.
Alternativament, es poden generar arbres d'expansió de manera aleatòria (encara que no uniforme), assignant a cada aresta del graf un pes aleatori, i després construint l'arbre generador mínim del graf ponderat.
Enumeració Com que un graf pot tenir un nombre exponencial d'arbres d'expansió, no és possible enumerar-los tots en temps polinòmic. Tot i això, existeixen algorismes per enumerar tots els arbres d'expansió en temps polinòmic per a cada arbre.
Cas de grafs infinits