Viquipèdia

Arbre d'expansió

(S'ha redirigit des de: Spanning tree)
«Spanning tree» redirigeix aquí. Vegeu-ne 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è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ó (amb les arestes en blau) d'un 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

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

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

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

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

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

 
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 modifica

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

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

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

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]

Algorismes modifica

Construcció modifica

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

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

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

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

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

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

  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.. Matroid Theory. 3. Oxford University Press, 2006, p. 141. ISBN 978-0-19-920250-8. 
  5. ↑ Bollobás, Béla. Modern Graph Theory. 184. Springer, 1998, p. 350. ISBN 978-0-387-98488-9. ; Mehlhorn, Kurt. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, 1999, p. 260. ISBN 978-0-521-56329-1. 
  6. ↑ Cameron, Peter J. Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, 1994, p. 163. ISBN 978-0-521-45761-3. 
  7. ↑ Gross, Jonathan L.; Yellen, Jay. Graph Theory and Its Applications. 2nd. CRC Press, 2005, p. 168. ISBN 978-1-58488-505-4. ; Bondy, J. A.; Murty, U. S. R.. Graph Theory. 244. Springer, 2008, p. 578. ISBN 978-1-84628-970-5. 
  8. ↑ Aigner, Martin; Ziegler, Günter M. Proofs from THE BOOK. Springer-Verlag, 1998, p. 141-146. 
  9. ↑ Hartsfield, Nora; Ringel, Gerhard. Pearls in Graph Theory: A Comprehensive Introduction. Courier Dover Publications, 2003, p. 100. ISBN 978-0-486-43232-8. 
  10. ↑ Harary, Frank; Hayes, John P.; Wu, Horng-Jyh «A survey of the theory of hypercube graphs». Computers & Mathematics with Applications, 15, 4, 1988, p. 277–289. DOI: 10.1016/0898-1221(88)90213-1.
  11. ↑ Kocay, William; Kreher, Donald L. Graphs, Algorithms, and Optimization. CRC Press, 2004, p. 111-116. ISBN 978-0-203-48905-5. «5.8 The matrix-tree theorem» 
  12. ↑ Kocay & Kreher (2004), p. 109.
  13. ↑ Bollobás (1998), p. 351.
  14. ↑ Goldberg, L.A.; Jerrum, M. «Inapproximability of the Tutte polynomial». Information and Computation, 206, 7, 2008, p. 908. DOI: 10.1016/j.ic.2008.04.003.; Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. «On the computational complexity of the Jones and Tutte polynomials». Mathematical Proceedings of the Cambridge Philosophical Society, 108, 1990, p. 35–53. DOI: 10.1017/S0305004100068936.
  15. ↑ Kozen, Dexter. The Design and Analysis of Algorithms. Springer, 1992, p. 19. ISBN 978-0-387-97687-7. 
  16. ↑ de Fraysseix, Hubert; Rosenstiehl, Pierre. Graph theory (Cambridge, 1981). 13. Amsterdam: North-Holland, 1982, p. 75–80. «A depth-first-search characterization of planarity» 
  17. ↑ Reif, John H. «Depth-first search is inherently sequential». Information Processing Letters, 20, 5, 1985, p. 229–234. DOI: 10.1016/0020-0190(85)90024-9.
  18. ↑ Gallager, R. G.; Humblet, P. A.; Spira, P. M. «A distributed algorithm for minimum-weight spanning trees». ACM Transactions on Programming Languages and Systems, 5, 1, 1983, p. 66–77. DOI: 10.1145/357195.357200.; Gazit, Hillel «An optimal randomized parallel algorithm for finding connected components in a graph». SIAM Journal on Computing, 20, 6, 1991, p. 1046–1067. DOI: 10.1137/0220066.; Bader, David A.; Cong, Guojing «Còpia arxivada». Journal of Parallel and Distributed Computing, 65, 9, 2005, p. 994–1006. Arxivat de l'original el 2015-09-23. DOI: 10.1016/j.jpdc.2005.03.011 [Consulta: 29 desembre 2015]. «Còpia arxivada». Arxivat de l'original el 2015-09-23. [Consulta: 29 desembre 2015].
  19. ↑ 19,0 19,1 Eppstein, David. Spanning trees and spanners. Elsevier, 1999, p. 425–461. 
  20. ↑ Wu, Bang Ye; Chao, Kun-Mao. Spanning Trees and Optimization Problems. CRC Press, 2004. ISBN 1-58488-436-3. 
  21. ↑ Wilson, David Bruce. Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), 1996, p. 296–303. DOI 10.1145/237814.237880. «Generating random spanning trees more quickly than the cover time» 
  22. ↑ McDiarmid, Colin; Johnson, Theodore; Stone, Harold S. «Còpia arxivada». Random Structures & Algorithms, 10, 1-2, 1997, p. 187–204. Arxivat de l'original el 2016-03-04. DOI: 10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y [Consulta: 29 desembre 2015]. «Còpia arxivada». Arxivat de l'original el 2016-03-04. [Consulta: 29 desembre 2015].
  23. ↑ Gabow, Harold N.; Myers, Eugene W. «Finding all spanning trees of directed and undirected graphs». SIAM Journal on Computing, 7, 3, 1978, p. 280–287. DOI: 10.1137/0207024.
  24. ↑ 24,0 24,1 Serre, Jean-Pierre. Trees. Springer, 2003, p. 23. 
  25. ↑ Soukup, Lajos. Horizons of combinatorics. 17. Berlin: Springer, 2008, p. 189–213. DOI 10.1007/978-3-540-77200-2_10. «Infinite combinatorics: from finite to infinite» . 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, 118, 2011, pàg. 350 - 364. DOI: 10.1016/j.jcta.2010.04.001. ISSN: 0097-3165.
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Arbre_d%27expansió&oldid=32854652»