Mostra la font per a Arbre d'expansió

{{redirecció|Spanning tree|Spanning tree (desambiguació)}}

[[Fitxer:4x4 grid spanning tree.svg|miniatura|Un arbre d'expansió (amb les arestes en {{color|blue|blau}}) d'un graf]]
Al camp [[matemàtiques|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 [[Graf (matemàtiques)#Classes de grafs en termes de connectivitat|connex]] no pot contenir cap arbre d'expansió. Si totes les [[Aresta (teoria de grafs)|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]].<ref>
R. L. Graham and Pavol Hell.
[http://www.math.ucsd.edu/~ronspubs/85_07_minimum_spanning_tree.pdf "On the History of the Minimum Spanning Tree Problem"].
1985.
</ref>

Internet i moltes altres [[Xarxa de telecomunicacions|xarxes de telecomunicacions]] tenen enllaços de transmissió que connecten nodes en una [[Xarxa en malla|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 ==
Un ''arbre'' és un [[Graf (matemàtiques)#Graf no dirigit|graf no dirigit]] [[Graf (matemàtiques)#Classes de grafs en termes de connectivitat|connex]] sense [[Cicle (teoria de grafs)|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'' −&nbsp;1 arestes i, per tant, un graf de ''E'' arestes i un dels seus arbres d'expansió tenen ''E'' − ''V'' +&nbsp;1 cicles fonamentals. Per a qualsevol arbre d'expansió, el conjunt de tots els ''E'' − ''V'' +&nbsp;1 cicles fonamentals formen una [[base de cicles]], és a dir, una base de l'[[espai de cicles]].<ref>{{harvtxt|Kocay|Kreher|2004}}, pp. 65–67.</ref>

=== 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'' −&nbsp;1 conjunts de tall fonamentals, un per a cada aresta de l'arbre d'expansió.<ref>{{harvtxt|Kocay|Kreher|2004}}, pp. 67–69.</ref>

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 [[matroide]]s, 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]].<ref>{{citar ref|títol=Matroid Theory |volum=3 |series=Oxford [[Graduate Texts in Mathematics]] |nom=J. G. |cognom=Oxley |enllaçautor=James Oxley |editorial=Oxford University Press |any=2006 |isbn=978-0-19-920250-8 |pàgina=141 |url=http://books.google.cat/books?id=puKta1Hdz-8C&pg=PA141}}</ref>

=== 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 (teoria de grafs)|component connexa]] del graf.<ref>{{citar ref|títol=Modern Graph Theory |volum=184 |series=Graduate Texts in Mathematics |nom=Béla |cognom=Bollobás |enllaçautor=Béla Bollobás |editorial=Springer |any=1998 |isbn=978-0-387-98488-9 |pàgina=350 |url=http://books.google.cat/books?id=SbZKSZ-1qrwC&pg=PA350}}; {{citar ref|títol=LEDA: A Platform for Combinatorial and Geometric Computing |nom=Kurt |cognom=Mehlhorn |enllaçautor=Kurt Mehlhorn |editorial=Cambridge University Press |any=1999 |isbn=978-0-521-56329-1 |pàgina=260 |url=http://books.google.cat/books?id=Q2aXZl3fgvMC&pg=PA260}}</ref>
* 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.<ref>{{citar ref|títol=Combinatorics: Topics, Techniques, Algorithms |nom=Peter J. |cognom=Cameron |enllaçautor=Peter Cameron (mathematician) |editorial=Cambridge University Press |any=1994 |isbn=978-0-521-45761-3 |pàgina=163 |url=http://books.google.cat/books?id=_aJIKWcifDwC&pg=PA163}}</ref>
Per tal d'evitar confusions entre aquestes definicions, {{harvtxt|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 {{harvtxt|Bondy|Murty|2008}} anomenen aquest tipus de bosc un "bosc d'expansió maximal".<ref>{{citar ref|títol=Graph Theory and Its Applications |edició=2a edició|nom1=Jonathan L. |cognom1=Gross |nom2=Jay |cognom2=Yellen |editorial=CRC Press |any=2005 |isbn=978-1-58488-505-4 |pàgina=168 |url=http://books.google.cat/books?id=-7Q_POGh-2cC&pg=PA168}}; {{citar ref|títol=Graph Theory |volum=244 |series=Graduate Texts in Mathematics |nom1=J. A. |cognom1=Bondy |nom2=U. S. R. |cognom2=Murty |editorial=Springer |any=2008 |isbn=978-1-84628-970-5 |pàgina=578 |url=http://books.google.cat/books?id=V0gUTxkOSboC&pg=PA578}}</ref>

== Nombre d'arbres d'expansió ==
[[Fitxer:Cayley's formula 2-4.svg|miniatura|La [[fórmula de Cayley]] compta el nombre d'arbres d'expansió d'un graf complet. Hi ha 2<sup>2-2</sup>=1 arbres en ''K''₂, 3<sup>3-2</sup>=3 arbres en ''K''₃, i 4<sup>4-2</sup>=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'')&nbsp;=&nbsp;1.
* Quan ''G'' és el [[graf cicle]] amb ''n'' vèrtexs, llavors ''t''(''G'')&nbsp;= ''n''.
* Per a un [[graf complet]] amb ''n'' vèrtexs, la [[fórmula de Cayley]]<ref>{{citar ref|cognom1= Aigner |nom1= Martin |enllaçautor1= Martin Aigner
 |cognom2= Ziegler |nom2= Günter M. |enllaçautor2= Günter M. Ziegler
 |pàgines= 141-146
 |editorial= [[Springer-Verlag]]
 |títol= [[Proofs from THE BOOK]]
 |any= 1998}}</ref> proporciona el nombre d'arbres d'expansió com ''n''<sup>''n'' −&nbsp;2</sup>.
* Si ''G'' és el [[graf bipartit complet]] <math>K_{p,q}</math>,<ref>{{citar ref|títol=Pearls in Graph Theory: A Comprehensive Introduction |cognom1=Hartsfield |nom1=Nora |enllaçautor1=Nora Hartsfield |cognom2=Ringel |nom2=Gerhard |enllaçautor2=Gerhard Ringel |editorial=Courier Dover Publications |any=2003 |isbn=978-0-486-43232-8 |pàgina=100 |url=http://books.google.cat/books?id=R6pq0fbQG0QC&pg=PA100}}</ref> llavors <math>t(G)=p^{q-1}q^{p-1}</math>.
* Per al [[graf hipercub]] ''n''-dimensional <math>Q_n</math>,<ref>{{citar ref|cognom1= Harary |nom1= Frank |enllaçautor1= Frank Harary
 |cognom2= Hayes |nom2= John P.
 |cognom3= Wu |nom3= Horng-Jyh
 | doi = 10.1016/0898-1221(88)90213-1
 |exemplar= 4
 |publicació= Computers & Mathematics with Applications
 | mr = 949280
 |pàgines= 277–289
 |títol= A survey of the theory of hypercube graphs
 |volum= 15
 |any= 1988}}</ref> el nombre d'arbres d'expansió és <math>t(G)=2^{2^n-n-1}\prod_{k=2}^n k^{{n\choose k}}</math>.

=== En grafs arbitraris ===
{{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 (matemàtiques)|determinant]] d'una [[Matriu (matemàtiques)|matriu]] derivada del graf, emprant el [[teorema de Kirchhoff]].<ref>{{citar ref|títol=Graphs, Algorithms, and Optimization |series=Discrete Mathematics and Its Applications |nom1=William |cognom1=Kocay |nom2=Donald L. |cognom2=Kreher |editorial=CRC Press |any=2004 |isbn=978-0-203-48905-5 |pàgines=111-116 |citació=5.8 The matrix-tree theorem |url=http://books.google.cat/books?id=zxSmHAoMiRUC&pg=PA111}}</ref>

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 [[Matriu invertible|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'')&nbsp;= ''t''(''G'' − ''e'')&nbsp;+ ''t''(''G''/''e''), on ''G'' − ''e'' és el multigraf obtingut mitjançant l'eliminació de ''e''
i ''G''/''e'' és la [[Contracció d'arestes|contracció]] de ''G'' per ''e''.<ref>{{harvtxt|Kocay|Kreher|2004}}, p. 109.</ref> 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.<ref>{{harvtxt|Bollobás|1998}}, p. 351.</ref>

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.<ref>{{citar ref|cognom1=Goldberg |nom1= L.A. |enllaçautor1= Leslie Ann Goldberg
|cognom2=Jerrum |nom2= M.
|enllaçautor2=Mark Jerrum
|títol= Inapproximability of the Tutte polynomial
|publicació=Information and Computation
| doi=10.1016/j.ic.2008.04.003
|any=2008
|volum=206
|pàgina=908
|exemplar=7
}}; {{citar ref|cognom1= Jaeger |nom1= F.
|cognom2= Vertigan |nom2= D. L.
|cognom3= Welsh |nom3=D. J. A.|enllaçautor3=Dominic Welsh
|títol= On the computational complexity of the Jones and Tutte polynomials
|publicació=Mathematical Proceedings of the Cambridge Philosophical Society
|volum= 108|pàgines= 35–53
| doi= 10.1017/S0305004100068936
|any= 1990
}}</ref>

== 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 [[Memòria en pila (estructura de dades)|pila]] (en el cas de la cerca en profunditat) o una [[Cua (estructura de dades)|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.<ref>{{citar ref|títol=The Design and Analysis of Algorithms|series=Monographs in Computer Science |nom=Dexter |cognom=Kozen |enllaçautor=Dexter Kozen |editorial=Springer |any=1992 |isbn=978-0-387-97687-7 |pàgina=19 |url=http://books.google.cat/books?id=L_AMnf9UF9QC&pg=PA19}}</ref> 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}}.<ref>{{citar ref|cognom1= de Fraysseix |nom1= Hubert
 |cognom2= Rosenstiehl |nom2= Pierre |enllaçautor2= Pierre Rosenstiehl
 |citació= A depth-first-search characterization of planarity
 |lloc= Amsterdam
 | mr = 671906
 |pàgines= 75–80
 |editorial= North-Holland
 | series = Ann. Discrete Math.
 |títol= Graph theory (Cambridge, 1981)
 |volum= 13
 |any= 1982}}</ref>

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.<ref>{{citar ref|cognom= Reif |nom= John H. |enllaçautor= John Reif
 | doi = 10.1016/0020-0190(85)90024-9
 |exemplar= 5
 |publicació= Information Processing Letters
 | mr = 801987
 |pàgines= 229–234
 |títol= Depth-first search is inherently sequential
 |volum= 20
 |any= 1985}}</ref> En comptes d'això, els investigadors han creat algorismes més especialitzats per tal de trobar arbres d'expansió en aquests models de computació.<ref>{{citar ref|cognom1= Gallager |nom1= R. G.
 |cognom2= Humblet |nom2= P. A.
 |cognom3= Spira |nom3= P. M.
 | doi = 10.1145/357195.357200
 |exemplar= 1
 |publicació= ACM Transactions on Programming Languages and Systems
 |pàgines= 66–77
 |títol= A distributed algorithm for minimum-weight spanning trees
 |volum= 5
 |any= 1983}}; {{citar ref|cognom= Gazit |nom= Hillel
 | doi = 10.1137/0220066
 |exemplar= 6
 |publicació= SIAM Journal on Computing
 | mr = 1135748
 |pàgines= 1046–1067
 |títol= An optimal randomized parallel algorithm for finding connected components in a graph
 |volum= 20
 |any= 1991}}; {{citar ref|cognom1= Bader
 |nom1= David A.
 |cognom2= Cong
 |nom2= Guojing
 | doi = 10.1016/j.jpdc.2005.03.011
 |exemplar= 9
 |publicació= Journal of Parallel and Distributed Computing
 |pàgines= 994–1006
 |títol= A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
 | url = http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf
 |volum= 65
 |any= 2005
 | títol = Còpia arxivada
 | consulta = 2015-12-29
 | arxiuurl = https://web.archive.org/web/20150923201604/http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf
 | arxiudata = 2015-09-23
 }} {{Ref-web |url=http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf |títol=Còpia arxivada |consulta=2015-12-29 |arxiuurl=https://web.archive.org/web/20150923201604/http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf |arxiudata=2015-09-23 }}</ref>

=== Optimització ===
En certs camps de la teoria de grafs és útil trobar un [[arbre generador mínim]] d'un [[Glossari de teoria de grafs|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.<ref name="sts">{{citar ref|cognom=Eppstein |nom=David |enllaçautor=David Eppstein |títol=Spanning trees and spanners |booktitle=Handbook of Computational Geometry |editorial=Elsevier |any=1999 |pàgines=425–461 |url=http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf}}</ref><ref>{{citar ref|cognom1=Wu |nom1=Bang Ye |cognom2=Chao |nom2=Kun-Mao |títol=Spanning Trees and Optimization Problems |any=2004 |editorial=CRC Press |isbn=1-58488-436-3}}</ref>

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.<ref name="sts"/>

=== 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í.<ref>{{citar ref|cognom= Wilson |nom= David Bruce
 |citació= Generating random spanning trees more quickly than the cover time
 | doi = 10.1145/237814.237880
 | mr = 1427525
 |pàgines= 296–303
 |títol= [[Symposium on Theory of Computing|Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (STOC 1996)]]
 |any= 1996}}</ref>

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.<ref>{{citar ref|cognom1= McDiarmid
 |nom1= Colin
 |cognom2= Johnson
 |nom2= Theodore
 |cognom3= Stone
 |nom3= Harold S.
 | doi = 10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y
 |exemplar= 1-2
 |publicació= Random Structures & Algorithms
 | mr = 1611522
 |pàgines= 187–204
 |títol= On finding a minimum spanning tree in a network with random weights
 | url = http://www.stats.ox.ac.uk/~cstone/mst.pdf
 |volum= 10
 |any= 1997
 | títol = Còpia arxivada
 | consulta = 2015-12-29
 | arxiuurl = https://web.archive.org/web/20160304093622/http://www.stats.ox.ac.uk/~cstone/mst.pdf
 | arxiudata = 2016-03-04
 }} {{Ref-web |url=http://www.stats.ox.ac.uk/~cstone/mst.pdf |títol=Còpia arxivada |consulta=2015-12-29 |arxiuurl=https://web.archive.org/web/20160304093622/http://www.stats.ox.ac.uk/~cstone/mst.pdf |arxiudata=2016-03-04 }}</ref>

=== 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.<ref>{{citar ref|cognom1= Gabow |nom1= Harold N.
 |cognom2= Myers |nom2= Eugene W. |enllaçautor2= Eugene Myers
 | doi = 10.1137/0207024
 |exemplar= 3
 |publicació= [[SIAM Journal on Computing]]
 | mr = 0495152
 |pàgines= 280–287
 |títol= Finding all spanning trees of directed and undirected graphs
 |volum= 7
 |any= 1978}}</ref>

== Cas de grafs infinits ==
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.<ref name="serre"/>

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ó.<ref name="serre">{{citar ref|títol=Trees|nom=Jean-Pierre|cognom=Serre|enllaçautor=Jean-Pierre Serre|pàgina=23|editorial=Springer|series=Springer Monographs in Mathematics|any=2003}}</ref>

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.<ref>{{citar ref|cognom= Soukup |nom= Lajos
 |citació= Infinite combinatorics: from finite to infinite
 | doi = 10.1007/978-3-540-77200-2_10
 |lloc= Berlin
 | mr = 2432534
 |pàgines= 189–213
 |editorial= Springer
 | series = Bolyai Soc. Math. Stud.
 |títol= Horizons of combinatorics
 |volum= 17
 |any= 2008}}. Vegeu en particular el Teorema 2.1, [http://books.google.cat/books?id=kIKW18ENfUMC&pg=PA192 pp. 192–193].</ref>

== Cas de multigrafs dirigits ==
La idea d'un arbre d'expansió es pot generalitzar al cas de multigrafs dirigits.<ref name="Levine09">{{ref-publicació|títol= Sandpile groups and spanning trees of directed line graphs
 |publicació= Journal of Combinatorial Theory, Series A
 |volum= 118
 | number = 2
 |pàgines= 350 - 364
 |any= 2011
 | issn = 0097-3165
 | doi = 10.1016/j.jcta.2010.04.001
 | url = http://www.sciencedirect.com/science/article/pii/S0097316510000701
 |autor= "Lionel Levine"
}}</ref> 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 ==
{{Referències}}

{{ORDENA:Arbre D'Expansio}}
[[Categoria:Teoria de grafs]]