Tung vägsönderdelning
I kombinatorisk matematik och teoretisk datavetenskap är tung vägnedbrytning (även kallad tung -ljusupplösning ) en teknik för att bryta ner ett rotat träd till en uppsättning banor . I en tung vägsönderdelning väljer varje icke-bladsnod en "tung kant", kanten till barnet som har det största antalet avkomlingar (bryter band godtyckligt). De valda kanterna bildar nedbrytningsbanorna.
Nedbrytning till stigar
Om kanterna på ett träd T är uppdelade i en uppsättning tunga kanter och lätta kanter, med en tung kant från varje icke-bladsnod till ett av dess underordnade, så består subgrafen som bildas av de tunga kanterna av en uppsättning banor, med varje icke-bladspunkt tillhörande exakt en bana, den som innehåller dess tunga kant. Lövnoder i trädet som inte är ändpunkten för en tung kant kan anses utgöra banor med längden noll. På så sätt tillhör varje vertex exakt en av banorna. Varje bana har en huvudpunkt, dess översta vertex.
Alternativt kan vägarna för tunga kanter förlängas genom att inkludera en lätt kant, den från banans huvud till dess överordnade. I denna variant av nedbrytningen tillhör vissa hörn flera banor, men varje kant av T tillhör exakt en väg.
Stigträdet
Banorna för nedbrytningen kan i sig vara organiserade i ett träd som kallas "stigträdet", "tungt stigträd" eller "komprimerat träd". Varje nod i vägträdet motsvarar en väg för den tunga vägnedbrytningen. Om p är en bana för den tunga bannedbrytningen, så är föräldern till p i sökvägsträdet den väg som innehåller föräldern till huvudet för p . Roten till sökvägsträdet är den sökväg som innehåller roten till det ursprungliga trädet. Alternativt kan vägträdet bildas från det ursprungliga trädet genom kantsammandragning av alla tunga kanter.
En "lätt" kant på ett givet träd är en kant som inte valdes som en del av den tunga vägnedbrytningen. Om en ljus kant förbinder två trädnoder x och y , med x föräldern till y , måste x ha minst dubbelt så många avkomlingar som y . På vilken rot-till-blad-bana som helst av ett träd med n noder kan det därför finnas högst log 2 n ljusa kanter. På motsvarande sätt har stigträdet högst log 2 n höjd .
Ansökningar
Heavy path decomposition introducerades av Sleator & Tarjan (1983) som en del av den amortiserade analysen av deras länk/kapade trädstruktur , och av Harel & Tarjan (1984) som en del av deras datastruktur för lägsta gemensamma förfäder , The link/cut tree datastrukturen använder en partition av ett dynamiskt träd i banor som inte nödvändigtvis är den tunga vägnedbrytningen; dess analys använder en potentiell funktion som mäter dess avstånd från den tunga vägnedbrytningen, och den lilla höjden på vägträdet innebär att varje datastrukturoperation endast utför ett litet antal steg som inte kan belastas med förbättringar av denna funktion. I den lägsta gemensamma förfäderdatastrukturen används nedbrytningen för att bädda in inmatningsträdet i ett komplett binärt träd med logaritmiskt djup, vilket gör att varje fråga kan lösas med bitvisa operationer med konstant tid .
Efterföljande tillämpningar av tung vägnedbrytning har inkluderat att lösa nivåförfäderproblemet , beräkna redigeringsavståndet mellan träd, grafritning och girig inbäddning , hitta en väg nära alla noder i en given graf, feldiagnos i fiberoptiska kommunikationsnätverk och avkodning av grammatik -baserade koder , bland annat.