Spanning Tree - Spanning tree

Ett spännande träd (blåa tunga kanter) i ett rutnätdiagram

I matematisk området för grafteori , en spanning tree T av en oriktad graf G är en subgraf som är ett träd som innehåller alla de hörn av G . I allmänhet kan ett diagram ha flera spännande träd, men ett diagram som inte är anslutet kommer inte att innehålla ett spännande träd (se spännande skogar nedan). Om alla kanterna på G också är kanter på ett spännande träd T av G , är G ett träd och är identiskt med T (det vill säga ett träd har ett unikt spännande träd och det är det självt).

Applikationer

Flera banfindande algoritmer, inklusive Dijkstras algoritm och A * -sökalgoritmen , bygger internt ett spännande träd som ett mellansteg för att lösa problemet.

För att minimera kostnaden för kraftnät, ledningsanslutningar, rörledningar, automatisk taligenkänning etc., använder människor ofta algoritmer som gradvis bygger ett spännande träd (eller många sådana träd) som mellansteg i processen att hitta det minsta spännande trädet .

Internet och många andra telekommunikationsnät har överföringslänkar som kopplar ihop noder i en mesh-topologi som innehåller några slingor. För att undvika bryggslingor och dirigeringsslingor kräver många routingsprotokoll som är utformade för sådana nätverk - inklusive Spanning Tree Protocol , Open Shortest Path First , Link-state routing protocol , Augmented tree-based routing , etc. - varje router för att komma ihåg en Spanning Tree.

En speciell typ av spännande träd, Xuong-trädet , används i topologisk grafteori för att hitta grafinbäddningar med maximalt släkt . Ett Xuong-träd är ett spännande träd så att i den återstående grafen är antalet anslutna komponenter med ett udda antal kanter så litet som möjligt. Ett Xuong-träd och en tillhörande inbäddning av maximalt släkte finns i polynomtid .

Definitioner

Ett träd är en ansluten oriktad graf utan cykler . Det är ett spännande träd i en graf G om det spänner över G (det vill säga det inkluderar varje toppunkt för G ) och är en underbild av G (varje kant i trädet tillhör G ). Ett spännande träd i en ansluten graf G kan också definieras som en maximal uppsättning kanter av G som inte innehåller någon cykel, eller som en minimal uppsättning kanter som förbinder alla hörn.

Grundläggande cykler

Att lägga till bara en kant i ett spännande träd skapar en cykel; en sådan cykel kallas en grundcykel . Det finns en distinkt grundcykel för varje kant inte i det spännande trädet; sålunda finns det en en-till-en-korrespondens mellan grundläggande cykler och kanter som inte finns i det spännande trädet. För ett anslutet diagram med V- hörn kommer varje spännande träd att ha V  - 1 kanter, och därmed kommer en graf med E- kanter och ett av dess spännande träd att ha E  -  V  + 1 grundcykler (Antalet kanter subtraherat med antalet kanter som ingår i ett spännande träd; vilket anger antalet kanter som inte ingår i det spännande trädet). För varje givet spännande träd utgör uppsättningen av alla E  -  V  + 1 grundcykler en cykelbas , en grund för cykelutrymmet .

Grundläggande skär

Dual till begreppet en grundläggande cykel är begreppet en grundläggande skärning . Genom att ta bort bara en kant av det spännande trädet delas hörnpunkterna i två separata uppsättningar. Den grundläggande skärsatsen definieras som den uppsättning kanter som måste tas bort från diagrammet G för att uppnå samma partition. Således definierar varje spännande träd en uppsättning V  - 1 grundläggande skär, en för varje kant av det spännande trädet.

Dualiteten mellan grundläggande skärpunkter och grundläggande cykler upprättas genom att notera att cykelkanter inte i det spännande trädet endast kan förekomma i skärningarna på de andra kanterna i cykeln; och tvärtom : kanterna i en skärsats kan bara visas i de cykler som innehåller kanten som motsvarar skärsatsen. Denna dualitet kan också uttryckas med hjälp av teorin om matroider , enligt vilka ett spännande träd är en bas för den grafiska matroiden , en grundcykel är den unika kretsen i uppsättningen som bildas genom att lägga till ett element till basen och grundläggande skärsnitt definieras på samma sätt från den dubbla matroiden .

Spännande skogar

I diagram som inte är anslutna kan det inte finnas något spännande träd, och man måste överväga att spänna skog istället. Här finns två konkurrerande definitioner:

• Vissa författare anser att en spännande skog är en maximal acyklisk delgraf av den angivna grafen, eller motsvarande en graf som består av ett spännande träd i varje ansluten komponent i diagrammet.
• För andra författare är en spännande skog en skog som sträcker sig över alla hörnpunkterna, vilket bara betyder att varje toppunkt i diagrammet är ett toppunkt i skogen. För denna definition kan till och med en ansluten graf ha en frånkopplad spännande skog, såsom den skog där varje toppunkt bildar ett enda vertexträd.

För att undvika förvirring mellan dessa två definitioner föreslår Gross & Yellen (2005) termen "fullspänningsskog" för en spänningsskog med samma anslutningsmöjligheter som den angivna grafen, medan Bondy & Murty (2008) istället kallar denna typ av skog en " maximal spännande skog ".

Räknar spännande träd

Cayleys formel räknar antalet spännande träd i en fullständig graf. Det finns träd i , träd i och träd i .${\ displaystyle 2 ^ {2-2} = 1}$${\ displaystyle K_ {2}}$${\ displaystyle 3 ^ {3-2} = 3}$${\ displaystyle K_ {3}}$${\ displaystyle 4 ^ {4-2} = 16}$${\ displaystyle K_ {4}}$

Antalet t ( G ) som spänner över träd i en ansluten graf är en väl studerad invariant .

I specifika diagram

I vissa fall är det enkelt att beräkna t ( G ) direkt:

• Om G i sig är ett träd är t ( G ) = 1 .
• När G är cyklisk graf C _n med n hörn, då t ( G ) =  n .
• För en komplett graf med n hörn, ger Cayleys formel antalet spännande träd som n ^{n  - 2} .
• Om G är den fullständiga bipartitgrafen , då .${\ displaystyle K_ {p, q}}$${\ displaystyle t (G) = p ^ {q-1} q ^ {p-1}}$
• För den n -dimensionella hyperkubdiagrammet är antalet spännande träd .${\ displaystyle Q_ {n}}$${\ displaystyle t (G) = 2 ^ {2 ^ {n} -n-1} \ prod _ {k = 2} ^ {n} k ^ {n \ välj k}}$

I godtyckliga diagram

Mer allmänt, för varje graf G , antalet t ( G ) kan beräknas på polynomisk tid som determinanten av en matris härrörande från grafen, med användning av Kirchhoffs matristrädet teorem .

Specifikt, för att beräkna t ( G ), konstruerar man Laplacian-matrisen i diagrammet, en kvadratisk matris där raderna och kolumnerna båda indexeras av G-hörnpunkterna . Inmatningen i rad i och kolumn j är ett av tre värden:

• Graden av vertex i , om i  =  j ,
• −1, om hörn i och j är intill varandra, eller
• 0, om hörn i och j skiljer sig från varandra men inte intill varandra.

Den resulterande matrisen är singular , så dess determinant är noll. Att radera raden och kolumnen för ett godtyckligt valt toppunkt leder dock till en mindre matris vars determinant är exakt  t ( G ).

Radering-sammandragning

Om G är en graf eller multigraf och e är en godtycklig kant av G , så uppfyller antalet t ( G ) av spännande träd av G borttagning-kontraktionsåterfallet t ( G ) =  t ( G  -  e ) +  t ( G / e ), där G  -  e är det multigrafi som erhålls genom att radera e och G / e är sammandragningen av G med e . Termen t ( G  -  e ) i denna formel räknar de spännande träd av  G som inte använder kant  e , och termen t ( G / e ) räknar de spännande träd av  G som använder  e .

I den här formeln, om den givna grafen G är ett multigrafik , eller om en sammandragning gör att två hörn ska anslutas till varandra med flera kanter, bör de redundanta kanterna inte tas bort, eftersom det skulle leda till fel total. Till exempel har ett bindningsdiagram som förbinder två hörn med k kanter k olika spännande träd, var och en består av en enda av dessa kanter.

Tutte polynom

Den Tutte polynom av en graf kan definieras som en summa under de spänner träden i diagrammet av termer beräknade från "intern aktivitet" och "yttre aktivitet" i trädet. Dess värde vid argumenten (1,1) är antalet spännande träd eller, i ett frånkopplat diagram, antalet maximala spännande skogar.

Tutte-polynomet kan också beräknas med en återkommande återhämtning av kontraktion, men dess beräkningskomplexitet är hög: för många värden för dess argument är beräkningen exakt # P-komplett , och det är också svårt att approximera med ett garanterat approximationsförhållande . Poängen (1,1), där den kan utvärderas med Kirchhoffs sats, är ett av få undantag.

Algoritmer

Konstruktion

Ett enda spännande träd i en graf kan hittas i linjär tid genom antingen djup-första sökning eller bredd-första-sökning . Båda dessa algoritmer utforskar den givna grafen, med utgångspunkt från ett godtyckligt toppunkt v , genom att slinga igenom grannarna till de hörn som de upptäcker och lägga till varje outforskad granne till en datastruktur som ska undersökas senare. De skiljer sig åt om den här datastrukturen är en stack (i fallet med djup-första sökning) eller en kö (i fallet med bredd-första-sökning). I båda fallen kan man bilda ett spännande träd genom att ansluta varje toppunkt, annat än rotkanten v , till toppunktet från vilket det upptäcktes. Detta träd är känt som ett djup-första sökträd eller ett bredd-första sökträd enligt den grafutforskningsalgoritm som används för att konstruera det. Djup-först sökträd är ett speciellt fall av en klass av spännande träd som kallas Trémaux-träd , uppkallad efter 1800-talets upptäckare av djup-första sökning.

Spännande träd är viktiga i parallell och distribuerad databehandling, som ett sätt att upprätthålla kommunikationen mellan en uppsättning processorer; se till exempel Spanning Tree Protocol som används av OSI- länklagerenheter eller Shout (protokoll) för distribuerad databehandling. Dyp-första och bredd-första-metoderna för att konstruera spännande träd på sekventiella datorer är dock inte lämpliga för parallella och distribuerade datorer. Istället har forskare tagit fram flera mer specialiserade algoritmer för att hitta spännande träd i dessa beräkningsmodeller.

Optimering

I vissa fält inom grafteorin är det ofta användbart att hitta ett minimalt spännande träd i ett viktat diagram . Andra optimeringsproblem på spännande träd har också studerats, inklusive det maximala spännande trädet, det minsta trädet som sträcker sig åtminstone k-hörn, det spännande trädet med flest kanter per vertex , det spännande trädet med flest blad , det spännande trädet med minst löv (nära besläktat med Hamiltonian-vägproblemet ), träd med minimidiameter och minimalt spännande träd.

Optimala spännande trädproblem har också studerats för ändliga uppsättningar av punkter i ett geometriskt utrymme såsom det euklidiska planet . För en sådan inmatning är ett spännande träd återigen ett träd som har som hörn de givna punkterna. Kvaliteten på trädet mäts på samma sätt som i en graf med det euklidiska avståndet mellan punkterna som vikt för varje kant. Således är till exempel ett euklidiskt minst spännande träd detsamma som ett grafiskt minimum spännande träd i en komplett graf med euklidiska kantvikter. Det är dock inte nödvändigt att konstruera denna graf för att lösa optimeringsproblemet; det euklidiska minsta spännande trädproblemet kan till exempel lösas mer effektivt under O ( n  log  n ) -tid genom att konstruera Delaunay-trianguleringen och sedan tillämpa en linjär tidsplan- minsta spännande trädalgoritm på den resulterande trianguleringen.

Randomisering

Ett spännande träd valt slumpmässigt bland alla spännande träd med lika sannolikhet kallas ett enhetligt spännande träd . Wilsons algoritm kan användas för att generera enhetliga spännande träd under polynomtid genom en process att ta en slumpmässig promenad på den angivna grafen och radera de cykler som skapas av denna promenad.

En alternativ modell för att generera spännande träd slumpmässigt men inte enhetligt är det slumpmässiga minimala spännande trädet . I den här modellen tilldelas kanterna på diagrammet slumpmässiga vikter och sedan konstrueras det minsta spännande trädet i det viktade diagrammet.

Uppräkning

Eftersom en graf kan ha exponentiellt många spännande träd är det inte möjligt att lista dem alla i polynomtid . Algoritmer är dock kända för att lista alla spännande träd i polynomtid per träd.

I oändliga diagram

Varje ändlig ansluten graf har ett spännande träd. För oändliga anslutna grafer motsvarar dock förekomsten av spännande träd den valda axiomen . En oändlig graf är ansluten om varje par av dess hörn bildar paret slutpunkter för en ändlig bana. Som med ändliga grafer är ett träd en ansluten graf utan ändliga cykler, och ett spännande träd kan definieras antingen som en maximal acyklisk uppsättning kanter eller som ett träd som innehåller varje toppunkt.

Träden i en graf kan delvis ordnas efter deras subgrafrelation, och vilken oändlig kedja som helst i denna partiella ordning har en övre gräns (föreningen av träden i kedjan). Zorns lemma , ett av många motsvarande uttalanden till det axiom du väljer, kräver att en partiell ordning i vilken alla kedjor är övre gränsen har ett maximalt element; i den delade ordningen på träden i diagrammet måste detta maximala element vara ett spännande träd. Därför, om Zorns lemma antas, har varje oändligt ansluten graf ett spännande träd.

I den andra riktningen, med tanke på en familj av uppsättningar , är det möjligt att konstruera ett oändligt diagram så att varje spännande träd i diagrammet motsvarar en valfunktion av familjen uppsättningar. Därför, om varje oändligt ansluten graf har ett spännande träd, så är valet av axiom sant.

I riktade multigrafer

Idén om ett spännande träd kan generaliseras till riktade multigrafer. Med tanke på en vertex v på en riktad multigraph G , är ett orienterat spännande träd T rotat vid v ett acykliskt subgraph av G där varje vertex annat än v har outgrad 1. Denna definition uppfylls endast när "grenarna" av T pekar mot v .

Se även

• Översvämningsalgoritm
• Bra spännande träd - Spännande träd för inbäddad plan graf

Referenser