Arbre d'expansió

De Viquipèdia
Dreceres ràpides: navegació, cerca
«Spanning tree» redirigeix aquí. Vegeu-ne altres significats a «Spanning tree (desambiguació)».
Un arbre d'expansió (amb les arestes en blau) 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[modifica | modifica el codi]

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ó.

Definicions[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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]

Nombre d'arbres d'expansió[modifica | modifica el codi]

La fórmula de Cayley compta el nombre d'arbres d'expansió d'un graf complet. Hi ha 22-2=1 arbres en K2, 33-2=3 arbres en K3, i 44-2=16 arbres en K4.

El nombre t(G) d'arbres d'expansió d'un graf connex és un invariant molt estudiat.

Exemples[modifica | modifica el codi]

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 nn − 2.
  • Si G és el graf bipartit complet ,[9] llavors .
  • Per al graf hipercub n-dimensional ,[10] el nombre d'arbres d'expansió és .

En grafs arbitraris[modifica | modifica el codi]

Article principal: Teorema de Kirchhoff

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ó[modifica | modifica el codi]

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.[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[modifica | modifica el codi]

El polinomi de Tutte 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]

Algorismes[modifica | modifica el codi]

Construcció[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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]

Cas de grafs infinits[modifica | modifica el codi]

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]

Cas de multigrafs dirigits[modifica | modifica el codi]

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.

Referències[modifica | modifica el codi]

  1. R. L. Graham and Pavol Hell. "On the History of the Minimum Spanning Tree Problem". 1985.
  2. Kocay & Kreher (2004), pp. 65–67.
  3. Kocay & Kreher (2004), pp. 67–69.
  4. Oxley, J. G. (2006), Matroid Theory, vol. 3, Oxford Graduate Texts in Mathematics, Oxford University Press, p. 141, ISBN 978-0-19-920250-8, <http://books.google.com/books?id=puKta1Hdz-8C&pg=PA141>.
  5. Bollobás, Béla (1998), Modern Graph Theory, vol. 184, Graduate Texts in Mathematics, Springer, p. 350, ISBN 978-0-387-98488-9, <http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA350>; Mehlhorn, Kurt (1999), LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, p. 260, ISBN 978-0-521-56329-1, <http://books.google.com/books?id=Q2aXZl3fgvMC&pg=PA260>.
  6. Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, p. 163, ISBN 978-0-521-45761-3, <http://books.google.com/books?id=_aJIKWcifDwC&pg=PA163>.
  7. Gross, Jonathan L. & Yellen, Jay (2005), Graph Theory and Its Applications (2nd ed.), CRC Press, p. 168, ISBN 978-1-58488-505-4, <http://books.google.com/books?id=-7Q_POGh-2cC&pg=PA168>; Bondy, J. A. & Murty, U. S. R. (2008), Graph Theory, vol. 244, Graduate Texts in Mathematics, Springer, p. 578, ISBN 978-1-84628-970-5, <http://books.google.com/books?id=V0gUTxkOSboC&pg=PA578>.
  8. Aigner, Martin & Ziegler, Günter M. (1998), Proofs from THE BOOK, Springer-Verlag, pàg. 141–146.
  9. Hartsfield, Nora & Ringel, Gerhard (2003), Pearls in Graph Theory: A Comprehensive Introduction, Courier Dover Publications, p. 100, ISBN 978-0-486-43232-8, <http://books.google.com/books?id=R6pq0fbQG0QC&pg=PA100>.
  10. Harary, Frank; Hayes, John P. & Wu, Horng-Jyh (1988), "A survey of the theory of hypercube graphs", Computers & Mathematics with Applications 15 (4): 277–289, DOI 10.1016/0898-1221(88)90213-1.
  11. Kocay, William & Kreher, Donald L. (2004), "5.8 The matrix-tree theorem", Graphs, Algorithms, and Optimization, Discrete Mathematics and Its Applications, CRC Press, pàg. 111–116, ISBN 978-0-203-48905-5, <http://books.google.com/books?id=zxSmHAoMiRUC&pg=PA111>.
  12. Kocay & Kreher (2004), p. 109.
  13. Bollobás (1998), p. 351.
  14. Goldberg, L.A. & Jerrum, M. (2008), "Inapproximability of the Tutte polynomial", Information and Computation 206 (7): 908, DOI 10.1016/j.ic.2008.04.003; Jaeger, F.; Vertigan, D. L. & Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials", Mathematical Proceedings of the Cambridge Philosophical Society 108: 35–53, DOI 10.1017/S0305004100068936.
  15. Kozen, Dexter (1992), The Design and Analysis of Algorithms, Monographs in Computer Science, Springer, p. 19, ISBN 978-0-387-97687-7, <http://books.google.com/books?id=L_AMnf9UF9QC&pg=PA19>.
  16. de Fraysseix, Hubert & Rosenstiehl, Pierre (1982), "A depth-first-search characterization of planarity", Graph theory (Cambridge, 1981), vol. 13, Ann. Discrete Math., Amsterdam: North-Holland, pàg. 75–80.
  17. Reif, John H. (1985), "Depth-first search is inherently sequential", Information Processing Letters 20 (5): 229–234, DOI 10.1016/0020-0190(85)90024-9.
  18. Gallager, R. G.; Humblet, P. A. & Spira, P. M. (1983), "A distributed algorithm for minimum-weight spanning trees", ACM Transactions on Programming Languages and Systems 5 (1): 66–77, DOI 10.1145/357195.357200; Gazit, Hillel (1991), "An optimal randomized parallel algorithm for finding connected components in a graph", SIAM Journal on Computing 20 (6): 1046–1067, DOI 10.1137/0220066; Bader, David A. & Cong, Guojing (2005), "A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)", Journal of Parallel and Distributed Computing 65 (9): 994–1006, doi:10.1016/j.jpdc.2005.03.011, <http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf>.
  19. 19,0 19,1 Eppstein, David (1999), Spanning trees and spanners, Elsevier, pàg. 425–461, <http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf>.
  20. Wu, Bang Ye & Chao, Kun-Mao (2004), Spanning Trees and Optimization Problems, CRC Press, ISBN 1-58488-436-3.
  21. Wilson, David Bruce (1996), "Generating random spanning trees more quickly than the cover time", Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), pàg. 296–303, DOI 10.1145/237814.237880.
  22. McDiarmid, Colin; Johnson, Theodore & Stone, Harold S. (1997), "On finding a minimum spanning tree in a network with random weights", Random Structures & Algorithms 10 (1-2): 187–204, doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y, <http://www.stats.ox.ac.uk/~cstone/mst.pdf>.
  23. Gabow, Harold N. & Myers, Eugene W. (1978), "Finding all spanning trees of directed and undirected graphs", SIAM Journal on Computing 7 (3): 280–287, DOI 10.1137/0207024
  24. 24,0 24,1 Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23.
  25. Soukup, Lajos (2008), "Infinite combinatorics: from finite to infinite", Horizons of combinatorics, vol. 17, Bolyai Soc. Math. Stud., Berlin: Springer, pàg. 189–213, DOI 10.1007/978-3-540-77200-2_10. Vegeu en particular el Teorema 2.1, pp. 192–193.
  26. "Lionel Levine" «Sandpile groups and spanning trees of directed line graphs». Journal of Combinatorial Theory, Series A, vol. 118, 2011, pàg. 350 - 364. DOI: 10.1016/j.jcta.2010.04.001. ISSN: 0097-3165.