Modulär nedbrytning

Modulär sönderdelning är sönderdelningen av en graf i delmängder av hörn, kallade moduler. En modul är en generalisering av en sammankopplad komponent i en graf. Till skillnad från anslutningskomponenter kan dock en modul vara sin egen delmängd av en annan. Moduler leder därför till en rekursiv (hierarkisk) nedbrytning av grafen, inte bara partitioner.

Modulära nedbrytningsvarianter finns för oriktade grafer och riktade grafer . För varje oriktad graf är en sådan nedbrytning unik.

Begreppet kan generaliseras till andra strukturer (som riktade grafer) och är användbart för att utveckla effektiva algoritmer för att känna igen vissa klasser av grafer, för att hitta transitiva orienteringar av jämförbarhetsgrafer , för optimeringsproblem på grafer och för att visualisera grafer .

Moduler

Konceptet med en modul har återupptäckts inom många områden. För detta koncept användes namnen autonoma uppsättningar , homogena uppsättningar , intervaller och bråksatser . Tydligen var det tidigaste omnämnandet och den första beskrivningen av modulära kvoter och uppdelningen av grafer som uppstår i detta fall i Galais tidning 1967.

Grafmodulen är en generalisering av den anslutna komponenten . En ansluten komponent har egenskapen att den är en uppsättning hörn så att vilken medlem som helst inte är granne med någon vertex som inte är i . En generalisering kommer att vara, är en modul när, för varje vertex , antingen någon medlem inte är en granne eller någon medlem är en granne . $X$ $X$ $X$ $X$ $v\not \in X$ $X$ $v$ $X$ $v$

På motsvarande sätt är en modul om alla medlemmar har samma uppsättning grannar bland hörn som inte är i . $X$ $X$ $X$

Till skillnad från anslutna komponenter är modulerna i en graf desamma som modulerna i dess komplement , och moduler kan "kapslas" - en modul kan vara sin egen delmängd av en annan. Observera att vertexuppsättningen av en graf är en modul, liksom singletonuppsättningar och den tomma uppsättningen . De kallas triviala moduler . Grafen kan ha andra moduler eller inte. En graf kallas enkel om alla dess moduler är triviala. $V$

Trots skillnaderna behåller moduler den önskade egenskapen hos anslutna komponenter, vilket är att många egenskaper hos subgrafen som genereras av en ansluten komponent är oberoende av resten av grafen. Ett liknande fenomen observeras för subgrafer som genereras av moduler. $G[X]$ $X$

Grafmoduler är därför av stort algoritmiskt intresse. En uppsättning kapslade moduler, varav modulär expansion är ett exempel, kan användas för att erhålla en rekursiv lösning på många kombinatoriska problem på grafer, såsom att känna igen och hitta den transitiva orienteringen av jämförbarhetsgrafer , känna igen och hitta permutationsrepresentationen av permutationsgrafer , känna igen om en graf är en kograf , känna igen intervallgrafer och hitta en intervallrepresentation för den, definitionen av avståndsärvda grafer [1] och för grafvisualisering [2] . De spelar en viktig roll i beviset för den perfekta grafsatsen [3] .

För att känna igen avståndsärvda grafer och cirkelgrafer , är en ytterligare generalisering av modulupplösning, kallad split decomposition [1] , särskilt användbar .

För att undvika tvetydigheten i definitionen ovan, ger vi följande formella definition av moduler. . är en modul av en graf om: $G=(V,E)$ $M\subseteq V$ $G$

hörn kan inte särskiljas av en vertex i , det vill säga antingen intill både , och c , eller inte intill båda , och . $M$ $V\backslash M$ $\forall u,v\in M,\forall x\in V\backslash M$ $x$ $u$ $v$ $x$ $u$ $v$
hörnen har samma uppsättning av yttre grannar, dvs. $M$ $\forall u,v\in M,N(u)\setminus M=N(v)\setminus M$

$\emptyset$ , och alla singlar för är moduler och de kallas triviala moduler . En graf är enkel om alla dess moduler är triviala. Anslutningskomponenter i en graf eller deras komplement är också moduler i en graf . $V$ $\{v\}$ $v\in V$ $G$ $G$

$M$ är en stark grafmodul om den inte (delvis) överlappar någon annan grafmodul — grafmodulen är antingen , eller , eller . $G$ $G$ $\forall M'$ $G$ $M\cap M'=\emptyset$ $M\subseteq M'$ $M'\subseteq M$

Modulära kvoter och faktorer

Om och är osammanhängande moduler, är det lätt att se att antingen någon medlem är granne till något element i , eller så är ingen medlem intill någon medlem av . Således är alla element i två icke-korsande moduler antingen intilliggande eller inte intill . Det finns inget mellantillstånd mellan dessa två ytterligheter. $X$ $Y$ $X$ $Y$ $X$ $Y$

Med tanke på detta är modulära nedbrytningar , där varje nedbrytningsklass är en modul, av särskilt intresse. Antag att det är en modulär nedbrytning. Eftersom partitionsklasserna inte skär varandra, bildar deras närhet en ny graf, kvotgrafen , vars hörn är termerna . Det vill säga, varje vertex är en modul i grafen G, och närliggande moduler definierar kanterna . $V$ $P$ $G/P$ $P$ $G/P$ $G/P$

I figuren nedan är hörn 1, hörn 2 till 4, hörn 5, hörn 6 och 7 och hörn 8 till 11 modulära. I det övre högra diagrammet visar kanterna mellan dessa mängder de kvoter som ges av den givna nedbrytningen, medan kanterna inom mängderna visar motsvarande faktorer.

Partitioner och är triviala modulära partitioner . är en graf med en vertex, medan . Anta att det är en icke-trivial modul. Sedan är en-elements delmängd också en icke-trivial modulär partition . Sålunda innebär förekomsten av icke -triviala moduler existensen av icke-triviala modulpartitioner. I allmänhet kan de flesta eller alla medlemmar vara icke-triviala moduler. ${\displaystyle \{V\))$ $\{\{x\}|x\in V\}$ $G/\{V\}$ $G/\{\{x\}|x\in V\}=G$ $X$ $X$ $V\backslash X$ $V$ $P$

Om är en icke-trivial modulär partition, då är en kompakt representation av alla kanter som slutar i olika partitionsklasser . För varje subgraf kallas partitionsklass som genereras av en faktor och den ger en representation av alla kanter med båda ändar i . Således kan kanterna på en graf rekonstrueras om kvotgrafen och dess faktorer är kända. Termen enkel graf kommer från det faktum att en enkel graf bara har triviala kvoter och faktorer. $P$ $G/P$ $P$ $X$ $P$ $G[X]$ $X$ $X$ $G$ $G/P$

Om är en multiplikator av modulo-kvoten , kan det visa sig att den kan faktoriseras rekursivt och kvotienter. Varje nivå av rekursion ger en kvot. Som basfall har grafen en vertex. Grafen kan rekonstrueras genom att rekonstruera faktorer underifrån, vända partitioneringsstegen genom att sammanställa faktorer med kvoter på varje nivå. $G[X]$ $G/P$ $G[X]$ $G$

I figuren nedan representeras en sådan rekursiv nedbrytning som ett träd, vilket återspeglar ett av sätten att rekursivt faktorisera de initiala modulära nedbrytningsfaktorerna till mindre modulära partitioner.

Metoden att rekursivt dela upp en graf i faktorer och kvoter är kanske inte den enda. (Till exempel är alla delmängder av hörn i en komplett graf moduler, vilket innebär att det finns många olika sätt att dekomponera den grafen rekursivt.) Vissa sätt att dekomponera kan vara mer användbara än andra.

Modularisering

Lyckligtvis finns det en rekursiv nedbrytning av en graf som implicit representerar alla sätt på vilka den kan dekomponeras. Detta är modularisering. Det är i sig ett sätt att rekursivt dekomponera en graf i kvoter, men det inkluderar alla andra. Nedbrytningen som visas i figuren nedan är en speciell uppdelning av den givna grafen.

Nedan följer en viktig observation för att förstå modulär nedbrytning:

Om är en modul i grafen och är en delmängd av $X$ $G$ $Y$ $X$ , då är en modul om och endast om det är en modul av . $Y$ $G$ $G[X]$

Gallai [4] definierade en modulär nedbrytning rekursivt på en graf med många hörn enligt följande: $V$

I basfallet, om den bara har en vertex, är dess modulära nedbrytning ett träd med en nod. $G$
Gallai visade att om är ansluten och så är dess komplement, då är de maximala modulerna, som är korrekta delmängder av , en partition av . De är därför modulära. De kvoter som de definierar är enkla. Trädets rot är markerad som en enkel nod, och dessa moduler accepteras av ättlingarna till uppsättningen . Eftersom de är maximala, finns alla moduler som inte representeras på detta sätt i avkomling av . För varje avkomling av uppsättningen, ersättning av modulariseringsträdet med ett modulärt nedbrytningsträd ger en representation av alla moduler i grafen, enligt nyckelobservationen ovan. $G$ $V$ $V$ $V$ $X$ $V$ $X$ $V$ $X$ $G[X]$ $G$
Om den inte är ansluten är dess komplement ansluten. Varje förening av anslutna komponenter är en grafmodul . Alla andra moduler är underuppsättningar av en separat anslutningskomponent. Detta representerar alla moduler utom undergrupper av anslutningskomponenter. För varje komponent, ersättning med ett modulärt nedbrytningsträd ger en representation av alla moduler i grafen enligt nyckelobservationen ovan. Trädets rot är markerad som en parallell nod, men är ett barn till roten. Den kvot som definieras av efterkommande är komplementet till hela grafen. $G$ $G$ $X$ $X$ $G[X]$ $G$ $X$
Om komplementet till grafen inte är anslutet, är grafen ansluten. Underträden som är barn till definieras symmetriskt till det fall där grafen inte är ansluten, eftersom modulerna i grafen är desamma som modulerna i dess komplement. Trädets rot är märkt som en sekventiell nod, och kvoten som definieras av ättlingarna är hela grafen. $G$ $G$ $V$ $G$

Det sista trädet har en enkel uppsättning grafhörn som löv, som är basfallet. En uppsättning grafhörn är en modul om och endast om det är en trädnod eller en förening av ättlingar till en seriell eller parallell nod. Detta tilldelar implicit alla modulära expansioner till toppen . I denna mening "koncentrerar det modulära nedbrytningsträdet i sig självt" alla andra sätt att rekursivt bryta ned en graf till partiella. $G$ $Y$ $G$ $V$ $G$

Algoritmiska problem

Datastrukturen för att representera ett modulärt nedbrytningsträd måste stödja operationer som tar en nod som indata och returnerar den uppsättning grafhörn som noden representerar. Det uppenbara sättet att göra detta är att tilldela varje nod en lista med hörn i grafen som noden representerar. Givet en pekare till en nod kan uppsättningen av grafhörn som noden representerar hämtas i tid . En sådan struktur kräver dock minne i värsta fall . $G$ $k$ $G$ $G$ ${\mathcal {O}}(k)$ $\Theta (n^{2})$

Minnesalternativet erhålls genom att representera det modulära sönderdelningsträdet med vilken standard rotad trädbaserad datastruktur som helst, och märka varje blad med grafens hörn det representerar. Uppsättningen som representeras av den interna noden definieras av uppsättningen etiketter för dess efterkommande blad. Det är välkänt att alla rotade träd med löv har som mest inre noder. Du kan använda djup-först-sökning från och med för att få etiketter på avkomblad vid tidpunkten . ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$ $G$ $v$ $k$ $k-1$ $v$ $v$ ${\mathcal {O}}(k)$

Varje nod är en uppsättning hörn i grafen och, om det är en intern nod, är uppsättningen av avkomlingar en split , där varje delad klass är en modul. Därför genererar de en kvot i . Spetsen i denna kvot är delar av , så kan representeras genom att upprätta kanter mellan barnen till . Om och är två termer och , , då och är angränsande i om och endast om och är intilliggande i kvoten. För varje par av grafhörn bestäms detta av de privata ättlingarna till den största gemensamma förfadern och i det modulära nedbrytningsträdet. Därför ger en modulär nedbrytning märkt som kvoter på detta sätt en fullständig representation av grafen . $X$ $G$ $X$ $P$ $X$ $X$ $G[X]/P$ $G[X]$ $P$ $G[X]/P$ $X$ $Y$ $Z$ $P$ $u\in Y$ $v\in Z$ $u$ $v$ $G$ $Y$ $Z$ ${\displaystyle \{u,v\))$ $G$ ${\displaystyle \{u\))$ $\{v\}$ $G$

Många kombinatoriska problem kan lösas på en graf genom att lösa dem separat för varje kvot. Till exempel är en jämförbarhetsgraf om och endast om var och en av dessa kvoter är en jämförbarhetsgraf [4] [5] . Därför, för att avgöra om en graf är en jämförbarhetsgraf, räcker det att kontrollera detta för var och en av dess kvoter. I själva verket, för att hitta den transitiva orienteringen av en jämförbarhetsgraf, är det tillräckligt att hitta den transitiva orienteringen för var och en av dess kvoter i den modulära uppdelningen [4] [5] . Ett liknande fenomen finns för permutationsgrafer [6] , intervallgrafer [7] , perfekta grafer och andra klasser av grafer. Vissa viktiga kombinatoriska optimeringsproblem på grafer kan lösas med liknande strategier [8] . $G$ $G$

Kografer är grafer som bara har parallella eller sekventiella noder i sitt modulära nedbrytningsträd.

Den första polynomtidsalgoritmen för att beräkna det modulära nedbrytningsträdet för en graf publicerades 1972 [9] , och linjära tidsalgoritmer finns nu tillgängliga [6] [10] .

Generaliseringar

Modulär uppdelning av riktade grafer kan erhållas i linjär tid [11] .

Med några få enkla undantag har varje graf med en icke-trivial moduluppdelning också en skev partition [12] .

Anteckningar

↑ 12 Spinrad , 2003 .
↑ Papadopoulos, Voglis, 2005 .
↑ Golumbic, 1980 .
↑ 1 2 3 Gallai, 1967 , sid. 25–66.
↑ 12 Möhring , 1985a , sid. 41–101.
↑ 1 2 McConnell, Spinrad, 1999 , sid. 189–241.
↑ Hsu, Ma, 1999 , sid. 1004–1020.
↑ Möhring, 1985b , sid. 195–225.
↑ James, Stanton, Cowan, 1972 , sid. 281–290.
↑ Tedder, Corneil, Habib, Paul, 2008 , sid. 634–645.
↑ McConnell, de Montgolfier, 2005 , sid. 198–209.
↑ Reed, 2008 .

Litteratur

Tibor Gallai. Transitiv orientierbare Graphen // Acta Mathematica Academiae Scientiarum Hungaricae. - 1967. - T. 18 . - doi : 10.1007/BF02020961 .
Lee O. James, Ralph G. Stanton, Donald D. Cowan. Grafnedbrytning för oriktade grafer // Proc. 3rd Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972). — Florida Atlantic University , 1972.
Martin C. Golumbic. Algoritmisk grafteori och perfekta grafer. - Academic Press, 1980. - ISBN 0-444-51530-5 .
Hsu WL, Ma T. Snabba och enkla algoritmer för att känna igen ackordsjämförbarhetsgrafer och intervallgrafer // SIAM Journal on Computing. - 1999. - T. 28 , nr. 3 . - doi : 10.1137/S0097539792224814 .
Ross M. McConnell, Fabien de Montgolfier. Linjär-tidsmodulär uppdelning av riktade grafer // Diskret tillämpad matematik. - 2005. - T. 145 , nr. 2 . - doi : 10.1016/j.dam.2004.02.017 .
Ross M. McConnell, Jeremy P. Spinrad. Modulär nedbrytning och transitiv orientering // Diskret matematik . - 1999. - T. 201 . - doi : 10.1016/S0012-365X(98)00319-7 .
Rolf H. Möhring. Algoritmiska aspekter av jämförbarhetsgrafer och intervallgrafer // Grafer och ordning. — D. Reidel, 1985a.
Rolf H. Möhring. Algoritmiska aspekter av substitutionsupplösningen vid optimering över relationer, uppsättningssystem och booleska funktioner // Annals of Operations Research. — 1985b. - T. 4 . - doi : 10.1007/BF02022041 .
Charis Papadopoulos, Constantinos Voglis. Rita grafer med modulär nedbrytning // Proc. 13:e internationella symposium om grafritning (GD'05) . - Springer-Verlag, 2005. - T. 3843. - (Lecture Notes in Computer Science). - doi : 10.1007/11618058_31 .
Bruce Reed. Skev partitioner i perfekta grafer // Diskret tillämpad matematik. - 2008. - T. 156 , nr. 7 . - S. 1150-1156 . - doi : 10.1016/j.dam.2007.05.054 . Arkiverad från originalet den 19 september 2015.
Jeremy P Spinrad. Effektiva grafrepresentationer. - American Mathematical Society, 2003. - (Fields Institute Monographs). — ISBN 0-8218-2815-0 .
Marc Tedder, Derek Corneil, Michel Habib, Christophe Paul. Enklare linjär-tidsmodulär nedbrytning via rekursiva faktoriserande permutationer // Proc. 35:e internationella kollokviet om automater, språk och programmering (ICALP 2008) . - Springer-Verlag, 2008. - T. 5125. - (Lecture Notes in Computer Science). - doi : 10.1007/978-3-540-70575-8_52 .
Emad Zahedi, Jason Smith. Modulär uppdelning av grafer och den avståndsbevarande egenskapen // Diskret tillämpad matematik. - 2018. - Utgåva. 7 .

Länkar

Perl- implementering av den modulära nedbrytningsalgoritmen
Java -implementering av den modulära nedbrytningsalgoritmen
Implementering i Julia av den modulära nedbrytningsalgoritmen