Arbre d'expansió

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.^[1]

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 l'Spanning Tree Protocol, l'OSPF, o el protocol d'estat d'enllaç) requereixen que cada encaminador recordi un arbre d'expansió.

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.^[2]

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ó.^[3]

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.^[4]

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.^[5]
• 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.^[6]

Per tal d'evitar confusions entre aquestes definicions, Gross & Yellen (2005) suggereixen el terme "bosc d'expansió complet" per a un bosc d'expansió amb la mateixa connectivitat que el graf inicial, mentre que Bondy & Murty (2008) anomenen aquest tipus de bosc un "bosc d'expansió maximal".^[7]

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^[8] proporciona el nombre d'arbres d'expansió com n^{n − 2}.
• Si G és el graf bipartit complet ${\displaystyle K_{p,q}}$ ,^[9] llavors ${\displaystyle t(G)=p^{q-1}q^{p-1}}$ .
• Per al graf hipercub n-dimensional ${\displaystyle Q_{n}}$ ,^[10] el nombre d'arbres d'expansió és ${\displaystyle t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$ .

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.^[11]

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 ei G/e és la contracció de G per e.^[12] 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.^[13]

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.^[14]

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.^[15] 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 segle xix.^[16]

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.^[17] En comptes d'això, els investigadors han creat algorismes més especialitzats per tal de trobar arbres d'expansió en aquests models de computació.^[18]

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.^[19][20]

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.^[19]

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í.^[21]

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.^[22]

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.^[23]

Tot graf connex finit té un arbre d'expansió. En canvi, si el graf és connex i infinit, l'existència d'arbres d'expansió és equivalent a l'axioma de l'elecció. Un graf infinit és connex si cada parell de vèrtexs forma el parell d'extrems d'un camí finit. De la mateixa manera que amb els grafs finits, un arbre és un graf connex sense cicles finits, i hom pot definir un arbre d'expansió com un conjunt d'arestes acíclic maximal, o com un arbre que conté tots els vèrtexs.^[24]

Els arbres de dins d'un graf es poden ordenar parcialment mitjançant la seva relació de subgraf, i qualsevol cadena infinita en aquest ordre parcial té una fita superior (la unió de tots els arbres de la cadena). El lema de Zorn, un dels enunciats equivalents a l'axioma de l'elecció, requereix que un ordre parcial en el qual totes les cadenes estiguin afitades superiorment tinguin un element maximal; en l'ordre parcial sobre els arbres del graf, aquest element maximal ha de ser un arbre d'expansió. Així, si s'accepta el lema de Zorn, tot graf connex infinit té un arbre d'expansió.^[24]

Recíprocament, donada una família de conjunts, és possible construir un graf infinit tal que tot arbre d'expansió del graf correspon a una funció d'elecció de la família de conjunts. Per tant, si tot graf connex infinit té un arbre d'expansió, llavors l'axioma de l'elecció és cert.^[25]

La idea d'un arbre d'expansió es pot generalitzar al cas de multigrafs dirigits.^[26] Donat un vèrtex v d'un multigraf dirigit G, un arbre d'expansió orientat T amb arrel a v és un subgraf acíclic de G en el qual tot vèrtex excepte v té grau de sortida 1. Aquesta definició només se satisfà quan les “branques” de T estan orientades cap a v.