Modulär sönderdelning - Modular decomposition

I grafteori är den modulära sönderdelningen en sönderdelning av en graf i delmängder av hörn som kallas moduler. En modul är en generalisering av en ansluten komponent i ett diagram. Till skillnad från anslutna komponenter kan emellertid en modul vara en riktig delmängd av en annan. Moduler leder därför till en rekursiv (hierarkisk) sönderdelning av grafen, istället för bara en partition.

Det finns varianter av modulär sönderdelning för oriktade grafer och riktade grafer . För varje oriktad graf är denna sönderdelning unik.

Denna uppfattning kan generaliseras till andra strukturer (till exempel riktade grafer) och är användbar för att utforma effektiva algoritmer för igenkänning av vissa grafflasser, för att hitta transitiva orienteringar av jämförbarhetsgrafer , för optimeringsproblem på grafer och för grafritning .

Moduler

Eftersom begreppet moduler har återupptäckts inom många områden har moduler också kallats autonoma uppsättningar , homogena uppsättningar , intervall och partitiva uppsättningar . Kanske den tidigaste hänvisningen till dem och den första beskrivningen av modulära kvoter och grafnedbrytningen de ger upphov till ( Gallai 1967).

En modul i en graf är en generalisering av en ansluten komponent . En ansluten komponent har egenskapen att det är en uppsättning hörnor så att varje medlem i är en icke-granne till varje toppunkt som inte finns i . (Det är en sammanslutning av anslutna komponenter om och bara om den har denna egenskap.) Mer allmänt är en modul om, för varje hörn , antingen varje medlem i är en icke-granne till eller varje medlem i är en granne till . ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle v \ not \ i X}$ ${\ displaystyle X}$ ${\ displaystyle v}$ ${\ displaystyle X}$ ${\ displaystyle v}$

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

I motsats till de anslutna komponenterna är modulerna i ett diagram desamma som modulerna i dess komplement , och moduler kan "kapslas": en modul kan vara en riktig delmängd av en annan. Observera att uppsättningen hörn i en graf är en modul, liksom dess enelementundermängder och den tomma uppsättningen; dessa kallas triviala moduler . En graf kan ha eller inte ha andra moduler. En graf kallas primtal om alla dess moduler är triviala. ${\ displaystyle V}$

Trots dessa skillnader bevarar modulerna en önskvärd egenskap hos anslutna komponenter, vilket är att många egenskaper hos subgrafen som induceras av en ansluten komponent är oberoende av resten av grafen. Ett liknande fenomen gäller också för de subgrafer som induceras av moduler. ${\ displaystyle G [X]}$ ${\ displaystyle X}$

Modulerna i en graf är därför av stort algoritmiskt intresse. En uppsättning kapslade moduler, av vilka den modulära sönderdelningen är ett exempel, kan användas för att vägleda den rekursiva lösningen på många kombinatoriska problem på grafer, såsom att känna igen och transitivt orientera jämförbarhetsgrafer , känna igen och hitta permutationsrepresentationer av permutationsgrafer , erkänna om en graf är en cograph och att hitta ett certifikat för svaret på frågan, känna igen intervalldiagram och hitta intervallrepresentationer för dem, definiera avståndsarvliga grafer (Spinrad, 2003) och för grafritning (Papadopoulos, 2006). De spelar en viktig roll i Lovász berömda bevis på den perfekta grafsatsen (Golumbic, 1980).

För att känna igen avståndsärftliga grafer och cirkeldiagram är en ytterligare generalisering av modulär sönderdelning, kallad delad sönderdelning , särskilt användbar (Spinrad, 2003).

För att undvika möjligheten till oklarhet i definitionerna ovan ger vi följande formella definitioner av moduler. . är en modul med om: ${\ displaystyle G = (V, E)}$ ${\ displaystyle M \ subseteq V}$ ${\ displaystyle G}$

hörnen på kan inte särskiljas med någon toppunkt i , dvs antingen ligger intill båda och eller är varken intill eller till . ${\ displaystyle M}$ ${\ displaystyle V \ backslash M}$ ${\ displaystyle \ forall u, v \ in M, \ forall x \ in V \ backslash M}$ ${\ displaystyle x}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle x}$ ${\ displaystyle u}$ ${\ displaystyle v}$
hörnen av samma uppsättning av yttre grannar, dvs . ${\ displaystyle M}$ ${\ displaystyle \ forall u, v \ in M, N (u) \ setminus M = N (v) \ setminus M}$

${\ displaystyle \ emptyset}$ , och alla singletoner för är moduler, och kallas triviala moduler . En graf är prime om alla dess moduler är triviala. Anslutna komponenter i en graf eller dess komplementgraf är också moduler av . ${\ displaystyle V}$ ${\ displaystyle \ {v \}}$ ${\ displaystyle v \ i V}$ ${\ displaystyle G}$ ${\ displaystyle G}$

${\ displaystyle M}$ är en stark modul i en graf om den inte överlappar någon annan modul av : modul av , antingen eller eller . ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle \ forall M '}$ ${\ displaystyle G}$ ${\ displaystyle M \ cap M '= \ emptyset}$ ${\ displaystyle M \ subseteq M '}$ ${\ displaystyle M '\ subseteq M}$

Modulära kvoter och faktorer

Om och är separata moduler, är det lätt att se att antingen varje medlem i är en granne till varje element i , eller ingen del av, intill någon medlem av . Således är förhållandet mellan två olika moduler antingen intilliggande eller icke -intilliggande . Inget samband mellan dessa två ytterligheter kan existera. ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle Y}$

På grund av detta, modulära partitioner av där varje skiljevägg klass är en modul är av speciellt intresse. Antag att det är en modulär partition. Eftersom partitionsklasserna är oskiljaktiga utgör deras adjakenser ett nytt diagram, en kvotgraf , vars hörn är medlemmarna i . Det vill säga att varje hörn av är en modul av G, och adjakenserna för dessa moduler är kanterna på . ${\ displaystyle V}$ ${\ displaystyle P}$ ${\ displaystyle G/P}$ ${\ displaystyle P}$ ${\ displaystyle G/P}$ ${\ displaystyle 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 en modulär partition. I diagrammet uppe till höger visar kanterna mellan dessa uppsättningar kvoten som ges av denna partition, medan kanterna inuti uppsättningarna visar motsvarande faktorer.

Partitionerna och är de triviala modulära partitionerna . är bara en-toppunktsdiagrammet, medan . Antag att det är en icke -privat modul. Sedan och delelementen med enelement är en icke-modulär partition av . Således, förekomsten av eventuella icke-triviala moduler innebär att det finns icke-triviala modulära partitioner. I allmänhet kan många eller alla medlemmar vara icke -privata moduler. ${\ displaystyle \ {V \}}$ ${\ displaystyle \ {\ {x \} | x \ i V \}}$ ${\ displaystyle G/\ {V \}}$ ${\ displaystyle G/\ {\ {x \} | x \ i V \} = G}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle V \ backslash X}$ ${\ displaystyle V}$ ${\ displaystyle P}$

Om är en icke -modulär partition, är en kompakt representation av alla kanter som har slutpunkter i olika partitionsklasser av . För varje partitionsklass i kallas subgrafen inducerad av en faktor och ger en representation av alla kanter med båda slutpunkterna i . Därför kan kanterna av rekonstrueras endast med kvotdiagrammet och dess faktorer. Termen prime grafen kommer från det faktum att en utmärkt graf har endast triviala kvoter och faktorer. ${\ displaystyle P}$ ${\ displaystyle G/P}$ ${\ displaystyle P}$ ${\ displaystyle X}$ ${\ displaystyle P}$ ${\ displaystyle G [X]}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle G}$ ${\ displaystyle G/P}$

När är en faktor för en modulär kvot , är det möjligt att rekursivt kan brytas ned i faktorer och kvoter. Varje nivå av rekursionen ger upphov till en kvot. Som ett grundfall har grafen bara en toppunkt. Sammantaget kan rekonstrueras induktivt genom att rekonstruera faktorerna nedifrån och upp, invertera nedbrytningens steg genom att kombinera faktorer med kvoten på varje nivå. ${\ displaystyle G [X]}$ ${\ displaystyle G/P}$ ${\ displaystyle G [X]}$ ${\ displaystyle G}$

I figuren nedan representeras en sådan rekursiv sönderdelning av ett träd som visar ett sätt att rekursivt sönderdela faktorer för en initial modulär partition till mindre modulära partitioner.

Ett sätt att rekursivt sönderdela en graf till faktorer och kvoter är kanske inte unikt. (Till exempel är alla delmängder av hörnen i ett komplett diagram moduler, vilket innebär att det finns många olika sätt att sönderdela det rekursivt.) Vissa sätt kan vara mer användbara än andra.

Den modulära sönderdelningen

Lyckligtvis finns det en sådan rekursiv nedbrytning av en graf som implicit representerar alla sätt att sönderdela den; detta är den modulära sönderdelningen. Det är i sig ett sätt att sönderdela en graf rekursivt till kvoter, men den sammanfattar alla andra. Nedbrytningen som visas i figuren nedan är denna speciella sönderdelning för den givna grafen.

En graf, dess kvot där "påsar" med hörn i grafen motsvarar barnen i roten till det modulära sönderdelningsträdet och dess fullständiga modulära sönderdelningsträd: seriens noder är märkta "s", parallella noder "//" och prim noder "p".

Följande är en viktig observation för att förstå den modulära sönderdelningen:

Om är en modul av och är en delmängd av ${\ displaystyle X}$ ${\ displaystyle G}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ , så är en modul av , om och bara om den är en modul av . ${\ displaystyle Y}$ ${\ displaystyle G}$ ${\ displaystyle G [X]}$

I (Gallai, 1967) definierade Gallai den modulära sönderdelningen rekursivt på en graf med toppunktsuppsättning , enligt följande: ${\ displaystyle V}$

Som ett basfall, om den bara har en toppunkt, är dess modulära sönderdelning en enda trädnod. ${\ displaystyle G}$
Gallai visade att om den är ansluten och dess komplement, så är de maximala moduler som är rätt delmängder en partition av . De är därför en modulär partition. Kvoten som de definierar är prime. Trädets rot är märkt som en primär nod, och dessa moduler tilldelas som barn till . Eftersom de är maximala finns varje modul som inte representerats hittills i ett barn till . För varje barn av , ersättning med det modulära sönderdelningsträdet av ger en representation av alla moduler av , genom nyckelobservationen ovan. ${\ displaystyle G}$ ${\ displaystyle V}$ ${\ displaystyle V}$ ${\ displaystyle V}$ ${\ displaystyle X}$ ${\ displaystyle V}$ ${\ displaystyle X}$ ${\ displaystyle V}$ ${\ displaystyle X}$ ${\ displaystyle G [X]}$ ${\ displaystyle G}$
Om den är bortkopplad är dess komplement anslutet. Varje sammanslutning av anslutna komponenter är en modul av . Alla andra moduler är delmängder av en enda ansluten komponent. Detta representerar alla moduler, förutom delmängder av anslutna komponenter. För varje komponent ger ersättning med det modulära sönderdelningsträdet en representation av alla moduler av , med nyckelobservationen ovan. Trädets rot är märkt som en parallell nod, och den fästs istället som ett barn till roten. Kvoten som definieras av barnen är komplementet till en komplett graf. ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle G [X]}$ ${\ displaystyle G}$ ${\ displaystyle X}$
Om komplementet till är frånkopplat, är anslutet. Subträden som är barn till definieras på ett sätt som är symmetriskt med fallet där det är frånkopplat, eftersom modulerna i en graf är desamma som modulerna i dess komplement. Trädets rot är märkt som en seriell nod, och kvoten som definierats av barnen är en fullständig graf. ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle V}$ ${\ displaystyle G}$

Det sista trädet har ett-element uppsättningar av hörn av som sina blad, på grund av basfodralet. En uppsättning hörn av är en modul om och bara om det är en nod i trädet eller en sammanslutning av barn i en serie eller parallell nod. Detta ger implicit alla modulära partitioner av . Det är i den meningen att det modulära sönderdelningsträdet "sänker" alla andra sätt att rekursivt sönderdelas till kvoter. ${\ displaystyle G}$ ${\ displaystyle Y}$ ${\ displaystyle G}$ ${\ displaystyle V}$ ${\ displaystyle G}$

Algoritmiska frågor

En datastruktur för att representera det modulära sönderdelningsträdet bör stödja operationen som matar in en nod och returnerar den uppsättning hörn som noden representerar. Ett uppenbart sätt att göra detta är att tilldela varje nod en lista över de hörn som den representerar. Med en pekare till en nod kan den här strukturen returnera den uppsättning hörn som den representerar i tid. Denna datastruktur skulle dock kräva utrymme i värsta fall. ${\ displaystyle G}$ ${\ displaystyle k}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle {\ mathcal {O}} (k)}$ ${\ displaystyle \ Theta (n^{2})}$

En representation av den modulära sönderdelningen

{\ displaystyle {\ mathcal {O}} (n)}

Ett alternativ för rymden som matchar denna prestanda erhålls genom att representera det modulära sönderdelningsträdet med hjälp av en standarddatastruktur med rotat träd och märka varje blad med toppunktet för det som det representerar. Uppsättningen som representeras av en intern nod ges av uppsättningen etiketter för dess bladavkomlingar. Det är välkänt att alla rotade träd med löv har högst interna noder. Man kan använda en djup-första sökning från och med att rapportera etiketterna på blad-ättlingar i tid. ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle G}$ ${\ displaystyle v}$ ${\ displaystyle k}$ ${\ displaystyle k-1}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle {\ mathcal {O}} (k)}$

Den modulära sönderdelningen, förstärkt med en kvot på barnen i varje intern nod, ger en fullständig representation av .

{\ displaystyle G}

Varje nod är en uppsättning hörn av och, om det är en intern nod, är uppsättningen barn till en partition av var varje partitionsklass är en modul. De inducerar därför kvoten in . Hörnen för denna kvot är elementen i , så kan representeras genom att installera kanter bland barnen i . Om och är två medlemmar av och och , då och är intilliggande i om och bara om och är intilliggande i denna kvot. För alla hörnpar bestäms detta av kvoten hos barn till den minst vanliga förfadern till och i det modulära sönderdelningsträdet. Därför ger den modulära sönderdelningen, märkt på detta sätt med kvoter, en fullständig representation av . ${\ displaystyle X}$ ${\ displaystyle G}$ ${\ displaystyle X}$ ${\ displaystyle P}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle G [X]/P}$ ${\ displaystyle G [X]}$ ${\ displaystyle P}$ ${\ displaystyle G [X]/P}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle Z}$ ${\ displaystyle P}$ ${\ displaystyle u \ i Y}$ ${\ displaystyle v \ i Z}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle G}$ ${\ displaystyle Y}$ ${\ displaystyle Z}$ ${\ displaystyle \ {u, v \}}$ ${\ displaystyle G}$ ${\ displaystyle \ {u \}}$ ${\ displaystyle \ {v \}}$ ${\ displaystyle G}$

Många kombinatoriska problem kan lösas genom att lösa problemet separat på var och en av dessa kvoter. Till exempel är en jämförbarhet graf om och bara om var och en av dessa kvoter är en jämförbarhet graf (Gallai, 67; Möhring, 85). Därför, för att hitta om en graf är en jämförbarhet graf, behöver man bara hitta om var och en av kvoterna är. För att hitta en transitiv orientering av ett jämförbarhetsgraf räcker det faktiskt med att transitivt orientera var och en av dessa kvoter av dess modulära sönderdelning (Gallai, 67; Möhring, 85). Ett liknande fenomen gäller permutationsgrafer, (McConnell och Spinrad '94), intervallgrafer (Hsu och Ma '99), perfekta grafer och andra grafklasser. Vissa viktiga kombinatoriska optimeringsproblem på grafer kan lösas med en liknande strategi (Möhring, 85). ${\ displaystyle G}$ ${\ displaystyle G}$

Cographs är graferna som bara har parallella eller seriens noder i sitt modulära sönderdelningsträd.

Den första polynomalgoritmen för att beräkna det modulära sönderdelningsträdet i en graf publicerades 1972 (James, Stanton & Cowan 1972) och nu är linjära algoritmer tillgängliga (McConnell & Spinrad 1999, Tedder et al. 2007, Cournier & Habib 1994).

Generaliseringar

Modulär sönderdelning av riktade grafer kan göras i linjär tid ( McConnell & de Montgolfier 2005 ).

Med ett litet antal enkla undantag har varje graf med en icke -modulär sönderdelning också en sneddelning ( Reed 2008 ).

Referenser

Gallai, Tibor (1967). "Transitiv orientierbare Graphen" . Acta Mathematica Academiae Scientiarum Hungaricae . 18 (1–2): 25–66. doi : 10.1007/BF02020961 . MR 0221974 . S2CID 119485995 .
James, Lee O .; Stanton, Ralph G .; Cowan, Donald D. (1972). "Grafnedbrytning för oreglerade grafer". Proc. 3: e sydöstra internationella konferensen om Combinatorics, Graph Theory och Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972) . Florida Atlantic University . s. 281–290. MR 0351909 .
Golumbic, Martin C. (1980). Algoritmisk grafteori och perfekta grafer . Academic Press. ISBN 0-444-51530-5.
Hsu, WL; Ma, T. (1999). "Snabba och enkla algoritmer för att känna igen ackordförlikningsgrafer och intervallgrafer". SIAM Journal on Computing . 28 (3): 1004–1020. CiteSeerX 10.1.1.104.4647 . doi : 10.1137/S0097539792224814 .
McConnell, Ross M .; de Montgolfier, Fabien (2005). "Linjär tidsmodulär sönderdelning av riktade grafer" . Diskret tillämpad matematik . 145 (2): 198–209. doi : 10.1016/j.dam.2004.02.017 .
McConnell, Ross M .; Spinrad, Jeremy P. (1999). "Modulär sönderdelning och transitiv orientering" (PDF) . Diskret matematik . 201 (1–3): 189–241. doi : 10.1016/S0012-365X (98) 00319-7 . MR 1687819 .
Möhring, Rolf H. (1985). I. Rival (red.). "Algoritmiska aspekter av jämförbarhetsgrafer och intervallgrafer". Grafer och ordning . D. Reidel: 41–101. doi : 10.1007/978-94-009-5315-4_2 . ISBN 978-94-010-8848-0.
Möhring, Rolf H. (1985). "Algoritmiska aspekter av substitutionsnedbrytningen vid optimering över relationer, uppsatta system och booleska funktioner". Annals of Operations Research . 4 : 195–225. doi : 10.1007/BF02022041 . S2CID 119982014 .
Papadopoulos, Charis; Voglis, Constantinos (2005). "Rita grafer med modulär sönderdelning" (PDF) . Proc. 13: e internationella symposiet om grafritning (GD'05) . Föreläsningsanteckningar i datavetenskap. 3843 . Springer-Verlag. s. 343–354. doi : 10.1007/11618058_31 . MR 2229205 .
Reed, Bruce (2008). "Snedställda partitioner i perfekta grafer" (PDF) . Diskret tillämpad matematik . 156 (7): 1150–1156. doi : 10.1016/j.dam.2007.05.054 . MR 2404228 . Arkiverad från originalet (PDF) 2015-09-19 . Hämtad 2012-08-13 .
Spinrad, Jeremy P. (2003). Effektiva grafrepresentationer . Fields Institute Monografier. American Mathematical Society. ISBN 0-8218-2815-0.
Tedder, Marc; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008). "Enklare linjär tidsmodulär sönderdelning via rekursiva faktoriserande permutationer". Proc. 35: e internationella kollokviumet om automatik, språk och programmering (ICALP 2008) . Föreläsningsanteckningar i datavetenskap. 5125 . Springer-Verlag. s. 634–645. arXiv : 0710.3901 . doi : 10.1007/978-3-540-70575-8_52 .
Zahedi, Emad; Smith, Jason (31 juli 2019). "Modulär sönderdelning av grafer och avståndsbevarande egenskap" . Diskret tillämpad matematik . 265 (7): 192–198. arXiv : 1805.09853 . Bibcode : 2018arXiv180509853Z . doi : 10.1016/j.dam.2019.03.019 .

Languages

In other projects