Transitiv reduktion
Inom det matematiska området grafteorin är en transitiv reduktion av en riktad graf D en annan riktad graf med samma hörn och så få kanter som möjligt, så att för alla par av hörn v , w en (riktad) väg från v till w i D finns om och endast om en sådan väg finns i reduktionen. Transitiva reduktioner introducerades av Aho, Garey & Ullman (1972), som gav snäva gränser för beräkningskomplexiteten i att konstruera dem.
Mer tekniskt är reduktionen en riktad graf som har samma nåbarhetsrelation som D . På motsvarande sätt D och dess transitiva reduktion ha samma transitiva stängning som varandra, och den transitiva reduktionen av D bör ha så få kanter som möjligt bland alla grafer med den egenskapen.
Den transitiva reduktionen av en finit riktad acyklisk graf (en riktad graf utan riktade cykler ) är unik och är en subgraf till den givna grafen. Emellertid misslyckas unikhet för grafer med (riktade) cykler, och för oändliga grafer är inte ens existens garanterad. [ exempel behövs ]
Det närbesläktade konceptet med en minsta ekvivalent graf är en subgraf av D som har samma nåbarhetsrelation och så få kanter som möjligt. Skillnaden är att en transitiv reduktion inte behöver vara en subgraf till D . För ändligt riktade acykliska grafer är den minsta ekvivalenta grafen densamma som den transitiva reduktionen. Men för grafer som kan innehålla cykler är minsta ekvivalenta grafer NP-svåra att konstruera, medan transitiva reduktioner kan konstrueras i polynomtid .
Transitiv reduktion kan definieras för en abstrakt binär relation på en mängd genom att tolka paren av relationen som bågar i en riktad graf.
I acykliska riktade grafer
Den transitiva reduktionen av en finit riktad graf G är en graf med minsta möjliga kanter som har samma nåbarhetsrelation som den ursprungliga grafen. Det vill säga, om det finns en väg från en vertex x till en vertex y i grafen G måste det också finnas en väg från x till y i den transitiva reduktionen av G , och vice versa. Specifikt, om det finns någon väg från x till y, och en annan från y till z, så kanske det inte finns någon väg från x till z som inte inkluderar y. Transitivitet för x, y och z betyder att om x < y och y < z, då x < z. Om det för någon väg från y till z finns en väg x till y, så finns det en väg x till z; det är dock inte sant att det för alla vägar x till y och x till z finns en väg y till z, och därför exkluderas varje kant mellan hörn x och z under en transitiv reduktion, eftersom de representerar promenader som inte är transitiva . Följande bild visar ritningar av grafer som motsvarar en icke-transitiv binär relation (till vänster) och dess transitiva reduktion (till höger).
|
|
Den transitiva reduktionen av en finit riktad acyklisk graf G är unik och består av kanterna på G som bildar den enda vägen mellan deras ändpunkter. I synnerhet är det alltid en spännande subgraf av den givna grafen. Av denna anledning sammanfaller den transitiva minskningen med minimiekvivalentgrafen i detta fall.
I den matematiska teorin om binära relationer kan varje relation R på en mängd X ses som en riktad graf som har mängden X som sin vertexmängd och som har en båge xy för varje ordnat par av element som är relaterade i R . I synnerhet låter denna metod partiellt ordnade uppsättningar omtolkas som riktade acykliska grafer, där det finns en båge xy i grafen när det finns en ordningsrelation x < y mellan det givna paret av element i den partiella ordningen. När den transitiva reduktionsoperationen appliceras på en riktad acyklisk graf som har konstruerats på detta sätt, genererar den den täckande relationen för delordningen, som ofta ges visuellt uttryck med hjälp av ett Hasse-diagram .
Transitiv reduktion har använts på nätverk som kan representeras som riktade acykliska grafer (t.ex. citeringsdiagram eller citeringsnätverk ) för att avslöja strukturella skillnader mellan nätverk.
I grafer med cykler
I en finit graf som har cykler kanske den transitiva reduktionen inte är unik: det kan finnas mer än en graf på samma vertexuppsättning som har ett minsta antal kanter och har samma nåbarhetsrelation som den givna grafen. Dessutom kan det vara så att ingen av dessa minimigrafer är en subgraf till den givna grafen. Ändå är det enkelt att karakterisera minimigraferna med samma nåbarhetsrelation som den givna grafen G . Om G är en godtyckligt riktad graf och H är en graf med minsta möjliga antal kanter som har samma nåbarhetsrelation som G , så består H av
- En riktad cykel för varje starkt ansluten komponent av G , som förbinder hörnen i denna komponent
- En kant xy för varje kant XY av den transitiva reduktionen av kondensationen av G , där X och Y är två starkt sammankopplade komponenter av G som är förbundna med en kant i kondensationen, x är valfri vertex i komponent X , och y är vilken som helst vertex i komponent Y . Kondensationen av G är en riktad acyklisk graf som har en vertex för varje starkt sammankopplad komponent av G och en kant för varannan två komponenter som är förbundna med en kant i G . I synnerhet, eftersom den är acyklisk, kan dess transitiva reduktion definieras som i föregående avsnitt.
Det totala antalet kanter i denna typ av transitiv reduktion är då lika med antalet kanter i den transitiva reduktionen av kondensationen, plus antalet hörn i icke-triviala starkt sammankopplade komponenter (komponenter med mer än en vertex).
Kanterna på den transitiva reduktionen som motsvarar kondensationskanterna kan alltid väljas att vara en subgraf till den givna grafen G . Cykeln inom varje starkt ansluten komponent kan dock bara väljas att vara en subgraf av G om den komponenten har en Hamiltonsk cykel , något som inte alltid är sant och är svårt att kontrollera. På grund av denna svårighet är det NP-svårt att hitta den minsta subgrafen i en given graf G med samma nåbarhet (dess minsta ekvivalenta graf).
Beräkningskomplexitet
Som Aho et al. visa, när tidskomplexiteten för grafalgoritmer mäts endast som en funktion av antalet n hörn i grafen, och inte som en funktion av antalet kanter, har transitiv stängning och transitiv reduktion av riktade acykliska grafer samma komplexitet. Det hade redan visat sig att transitiv stängning och multiplikation av booleska matriser av storlek n × n hade samma komplexitet som varandra, så detta resultat placerade transitiv reduktion i samma klass. De bästa exakta algoritmerna för matrismultiplikation , från och med 2015, tar tid O( n 2,3729 ), och detta ger den snabbaste kända värsta tänkbara tiden för transitiv reduktion i täta grafer.
Beräknar minskningen med hjälp av stängningen
För att bevisa att transitiv reduktion är lika lätt som transitiv stängning, Aho et al. lita på den redan kända ekvivalensen med boolesk matrismultiplikation. De låter A vara närliggande matris för den givna riktade acykliska grafen och B vara närliggande matris för dess transitiva stängning (beräknad med hjälp av vilken standard transitiv stängning som helst). Då hör en kant uv till den transitiva reduktionen om och endast om det finns en post som inte är noll i rad u och kolumn v i matris A , och det finns en nollpost i samma position för matrisprodukten AB . I denna konstruktion representerar elementen som inte är noll i matrisen AB par av hörn sammankopplade med banor med längden två eller fler.
Beräknar stängningen med hjälp av reduktionen
För att bevisa att transitiv reduktion är lika svårt som transitiv stängning, Aho et al. konstruera från en given riktad acyklisk graf G en annan graf H , där varje hörn av G ersätts av en bana med tre hörn, och varje kant på G motsvarar en kant i H som förbinder motsvarande mittpunkt i dessa banor. Dessutom, i grafen H , Aho et al. lägg till en kant från varje vägs början till varje vägslut. I den transitiva reduktionen av H finns det en kant från banans start för u till banans slut för v , om och endast om kanten uv inte hör till den transitiva stängningen av G . Därför, om den transitiva reduktionen av H kan beräknas effektivt, kan den transitiva stängningen av G läsas av direkt från den.
Beräknar minskningen av glesa grafer
När det mäts både i termer av antalet n av hörn och antalet m av kanter i en riktad acyklisk graf, kan transitiva reduktioner också hittas i tiden O( nm ), en gräns som kan vara snabbare än matrismultiplikationsmetoderna för glesa grafer . För att göra det, tillämpa en linjär algoritm för längsta vägen för tiden i den givna riktade acykliska grafen, för varje möjligt val av startpunkt. Från de beräknade längsta banorna, behåll endast de med längd ett (enkant); med andra ord, behåll de kanter ( u , v ) för vilka det inte finns någon annan väg från u till v . Denna tidsgräns för O( nm ) matchar komplexiteten i att konstruera transitiva förslutningar genom att använda djup-först-sökning eller breddförst-sökning för att hitta de hörn som kan nås från varje val av startpunkt, så återigen med dessa antaganden kan transitiva stängningar och transitiva reduktioner hittas i samma tid.
Anteckningar
- Aho, AV ; Garey, MR ; Ullman, JD (1972), "The transitive reduction of a directed graph", SIAM Journal on Computing , 1 (2): 131–137, doi : 10.1137/0201008 , MR 0306032 .
- Clough, JR; Gollings, J.; Loach, TV; Evans, TS (2015), "Transitive reduction of citation networks", Journal of Complex Networks , 3 (2): 189–203, arXiv : 1310.8224 , doi : 10.1093/comnet/cnu039 .
- Moyles, Dennis M.; Thompson, Gerald L. (1969), "An Algorithm for Finding a Minimum Equivalent Graph of a Digraph", Journal of the ACM , 16 (3): 455–460, doi : 10.1145/321526.321534 .
- Le Gall, François (2014), "Powers of Tensors and Fast Matrix Multiplication", Proc. 39th International Symposium on Symbolic and Algebraic Computation (ISSAC '14) , s. 296–303, doi : 10.1145/2608628.2608664 .