Spennende tre
I feltmatematikken for grafteori er et spennende tre av en ikke-rettet graf og tilhørende en aksel som inngår i denne grafen, som forbinder alle nodene i grafen.
Tilsvarende er det et maksimalt acyklisk subgraf , eller til og med et minimalt tilkoblet dekkende subgraf .
Eiendommer
I noen tilfeller er det mulig å beregne antall spennende trær i en tilkoblet graf . For eksempel, hvis det i seg selv er et tre, da , mens det er en n-syklus , da . For hvilken som helst graf kan beregnes ved hjelp av Kirchhoffs teorem .
Den formelen Cayley- også beregne direkte for en fullstendig graf . Vi får det .
Hvis G er en komplett tosidig graf , så er .
De spennende trærne i en graf danner en matroid , og kan derfor telles opp av en algoritme med polynomforsinkelse .
Minimum vekt som spenner over treet
Et klassisk algoritmisk problem er å finne, i en vektet graf, et spennende tre med minimal vekt . Vekten kan representere vanskeligheten med å ta en lenke, for eksempel en krysset tid med høy kobling. Når det gjelder grafen som er vektet også, er det flere algoritmer ( algoritme Borůvka , Prim-algoritmen , algoritme Kruskal ...).
Spennende trær studeres i teoretisk informatikk for deres applikasjoner på datanettverk.
De kan således definere en bane som tillater informasjon å overføres fra en node i et nettverk til en hvilken som helst annen node, mens de unngår tilstedeværelsen av sløyfer. Sløyfer er irriterende i et datanettverk fordi informasjon kan bevege seg gjennom sløyfen og rotere flere ganger før den når målet, eller til og med rotere på ubestemt tid i sløyfen, og aldri nå målet. I ekstreme tilfeller av kringkastingsstormen blir nettverket ubrukelig.
Spanning Tree Protocol- algoritmen oppdaget av Radia Perlman i 1985 gjør det mulig å finne et spennende tre i en vilkårlig graf. Det gjør det til og med mulig å finne et slikt tre i et multigrafi , som derfor kan inkludere flere kanter mellom et gitt par noder. Når det spennende treet er definert, blokkerer enhetene som ligger ved nodene i nettverket administrativt alle overflødige lenker. Hvis en kobling som spenner over tre, mislykkes, beregnes et nytt tre, slik at nettverket kan fortsette å operere hvis det var en reserve overflødig kobling.
Referanser
- Steven Klee og Matthew T. Stamps, “ Lineære algebraiske teknikker for spenning av treoppregning, ” Amer. Matte. Månedlig , vol. 127, nr . 4,februar 2020, s. 297-307 ( DOI 10.1080 / 00029890.2020.1708171 )
Se også
Bibliografi
- Eppstein, David (1999). “ Spanning trees and spanners ” Handbook of Computational Geometry : 425–461 s., Elsevier.
- (en) Garey, Michael R.; Johnson, David S. , Computers and intractability: a guide to the theory of NP-completeeness , New York, WH Freeman,1979, 338 s. ( ISBN 978-0-7167-1045-5 , varsel BNF n o FRBNF37670394 ) A2.1: ND2, s. 206.
- (i) Wu, Bang Ye; Chao, Kun-Mao, spennende trær og optimaliseringsproblemer , CRC Press,2004, 200 s. ( ISBN 978-1-58488-436-1 )
- (no) Gabow, Harold N.; Myers, Eugene W., “ Finding All Spanning Trees of Directed and Undirected Graphs ” , SIAM J. Comput. , vol. 7, n o 280,1978( les online )