Modulær spaltning - Modular decomposition

I grafteori er den modulære nedbrytningen en dekomponering av en graf i undersett av hjørner som kalles moduler. En modul er en generalisering av en tilkoblet komponent i en graf. I motsetning til tilkoblede komponenter kan imidlertid en modul være en skikkelig delsett av en annen. Moduler fører derfor til en rekursiv (hierarkisk) dekomponering av grafen, i stedet for bare en partisjon.

Det er varianter av modulær dekomponering for ikke -styrte grafer og dirigerte grafer . For hver ikke -rettet graf er denne dekomponeringen unik.

Denne oppfatningen kan generaliseres til andre strukturer (for eksempel dirigerte grafer) og er nyttig for å designe effektive algoritmer for gjenkjenning av noen grafklasser, for å finne transitive orienteringer av sammenlignbarhetsgrafer , for optimaliseringsproblemer på grafer og for graftegning .

Moduler

Siden begrepet moduler har blitt gjenoppdaget på mange områder, har moduler også blitt kalt autonome sett , homogene sett , intervaller og partitive sett . Kanskje den tidligste referansen til dem, og den første beskrivelsen av modulære kvotienter og grafnedbrytningen de gir opphav til, dukket opp i ( Gallai 1967).

En modul i en graf er en generalisering av en tilkoblet komponent . En tilkoblet komponent har egenskapen at det er et sett med hjørner slik at hvert medlem av er en ikke-nabo til hvert toppunkt som ikke er i . (Det er en sammenslutning av tilkoblede komponenter hvis og bare hvis den har denne egenskapen.) Mer generelt sett er en modul hvis for hvert toppunkt enten hvert medlem av er en ikke-nabo til eller hvert medlem av er en nabo til . ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle v \ not \ in X}$ ${\ displaystyle X}$ ${\ displaystyle v}$ ${\ displaystyle X}$ ${\ displaystyle v}$

Tilsvarende er en modul hvis alle medlemmer har samme sett med naboer blant hjørner som ikke er i . ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle X}$

I motsetning til de tilkoblede komponentene er modulene i en graf de samme som modulene i komplementet , og modulene kan "nestes": en modul kan være en riktig delmengde av en annen. Vær oppmerksom på at settet med hjørner i en graf er en modul, i likhet med delelementene med ett element og det tomme settet; disse kalles de trivielle modulene . En graf kan ha andre moduler eller ikke. En graf kalles prime hvis alle modulene er trivielle. ${\ displaystyle V}$

Til tross for disse forskjellene, beholder moduler en ønskelig egenskap for tilkoblede komponenter, som er at mange egenskaper til undergrafen indusert av en tilkoblet komponent er uavhengige av resten av grafen. Et lignende fenomen gjelder også for subgrafer indusert av moduler. ${\ displaystyle G [X]}$ ${\ displaystyle X}$

Modulene i en graf er derfor av stor algoritmisk interesse. Et sett med nestede moduler, som den modulære nedbrytningen er et eksempel på, kan brukes til å veilede den rekursive løsningen på mange kombinatoriske problemer på grafer, for eksempel å gjenkjenne og transitivt orientere sammenligningsgrafer , gjenkjenne og finne permutasjonsrepresentasjoner av permutasjonsgrafer , gjenkjenne om en graf er en cograph og finne et sertifikat for svaret på spørsmålet, gjenkjenne intervallgrafer og finne intervallrepresentasjoner for dem, definere avstandsarvelige grafer (Spinrad, 2003) og for graftegning (Papadopoulos, 2006). De spiller en viktig rolle i Lovászs berømte bevis på det perfekte grafsetningen (Golumbic, 1980).

For å gjenkjenne avstandsarvelige grafer og sirkeldiagrammer , er en ytterligere generalisering av modulær dekomponering, kalt splittet dekomponering , spesielt nyttig (Spinrad, 2003).

For å unngå muligheten for tvetydighet i definisjonene ovenfor, gir vi følgende formelle definisjoner av moduler. . er en modul av hvis: ${\ displaystyle G = (V, E)}$ ${\ displaystyle M \ subseteq V}$ ${\ displaystyle G}$

toppunktene til kan ikke skilles med noen toppunkt i , dvs. enten er ved siden av begge og eller verken er tilstøtende til eller til . ${\ 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}$
punktene av har samme sett av ytre naboer, dvs. . ${\ displaystyle M}$ ${\ displaystyle \ forall u, v \ in M, N (u) \ setminus M = N (v) \ setminus M}$

${\ displaystyle \ emptyset}$ , og alle singletonene for er moduler, og kalles trivielle moduler . En graf er prime hvis alle modulene er trivielle. Tilkoblede komponenter i en graf eller komplementgrafen er også moduler av . ${\ displaystyle V}$ ${\ displaystyle \ {v \}}$ ${\ displaystyle v \ in V}$ ${\ displaystyle G}$ ${\ displaystyle G}$

${\ displaystyle M}$ er en sterk modul i en graf hvis den ikke overlapper noen annen modul av : modul av , enten 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ære kvotienter og faktorer

Hvis og er usammenhengende moduler, så er det lett å se at enten hvert medlem av er en nabo til hvert element av , eller ikke noe medlem av, er i nærheten av et medlem av . Dermed er forholdet mellom to usammenhengende moduler enten tilstøtende eller ikke -tilstøtende . Ingen relasjon mellom disse to ytterpunktene kan eksistere. ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle Y}$

På grunn av dette modulære partisjoner av hvor hver partisjon klasse er en modul som er av spesiell interesse. Anta at det er en modulær partisjon. Siden partisjonsklassene er usammenhengende, utgjør deres adjacenser en ny graf, en kvotientgraf , hvis hjørner er medlemmene av . Det vil si at hvert toppunkt av er en modul av G, og tilstøtene til disse modulene er kantene på . ${\ displaystyle V}$ ${\ displaystyle P}$ ${\ displaystyle G/P}$ ${\ displaystyle P}$ ${\ displaystyle G/P}$ ${\ displaystyle G/P}$

På figuren nedenfor er toppunkt 1, hjørner 2 til 4, toppunkt 5, hjørner 6 og 7 og hjørner 8 til 11 en modulær partisjon. I diagrammet øverst til høyre viser kantene mellom disse settene kvoten gitt av denne partisjonen, mens kantene innvendig i settene viser de tilsvarende faktorene.

Partisjonene og er de trivielle modulære partisjonene . er bare en-toppunkt-grafen, mens . Anta at det er en ikke -privat modul. Deretter og delelementene til en-elementene er en ikke-modulær partisjon av . Således er tilstedeværelsen av eventuelle ikke-triviell moduler innebærer eksistensen av triviell modulære partisjoner. Generelt kan mange eller alle medlemmer av være ikke -private 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}$

Hvis er en ikke -modulær partisjon, er en kompakt fremstilling av alle kantene som har endepunkter i forskjellige partisjonsklasser av . For hver partisjonsklasse i kalles subgrafen indusert av en faktor og gir en representasjon av alle kanter med begge endepunktene i . Derfor kan kantene av rekonstrueres kun gitt kvotientgrafen og dens faktorer. Begrepet prime Grafen kommer fra det faktum at en førsteklasses graf har kun trivielle kvotienter og 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 er en faktor for en modulær kvotient , er det mulig at den kan rekursivt dekomponeres til faktorer og kvotienter. Hvert nivå av rekursjonen gir opphav til en kvotient. Som et grunnfall har grafen bare ett toppunkt. Samlet kan rekonstrueres induktivt ved å rekonstruere faktorene nedenfra og opp, invertere trinnene i nedbrytningen ved å kombinere faktorer med kvoten på hvert nivå. ${\ displaystyle G [X]}$ ${\ displaystyle G/P}$ ${\ displaystyle G [X]}$ ${\ displaystyle G}$

I figuren nedenfor er en slik rekursiv dekomponering representert av et tre som viser en måte for rekursivt å bryte ned faktorer for en innledende modulær partisjon til mindre modulære partisjoner.

En måte å rekursivt dekomponere en graf til faktorer og kvotienter er kanskje ikke unik. (For eksempel er alle undersett av hjørnene i en komplett graf moduler, noe som betyr at det er mange forskjellige måter å dekomponere det rekursivt på.) Noen måter kan være mer nyttige enn andre.

Den modulære nedbrytningen

Heldigvis eksisterer det en så rekursiv nedbrytning av en graf som implisitt representerer alle måter å dekomponere den på; dette er den modulære nedbrytningen. Det er i seg selv en måte å dekomponere en graf rekursivt til kvotienter, men den underbygger alle andre. Nedbrytningen som er vist i figuren nedenfor er denne spesielle nedbrytningen for den gitte grafen.

En graf, kvoten hvor "poser" med hjørner i grafen tilsvarer barna til roten til det modulære nedbrytningstreet, og dets fulle modulære dekomponeringstre: serienoder er merket "s", parallelle noder "//" og primtall noder "p".

Følgende er en sentral observasjon for å forstå den modulære nedbrytningen:

Hvis er en modul av og er en delmengde av ${\ displaystyle X}$ ${\ displaystyle G}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ , så er en modul av , hvis og bare hvis den er en modul av . ${\ displaystyle Y}$ ${\ displaystyle G}$ ${\ displaystyle G [X]}$

I (Gallai, 1967) definerte Gallai den modulære nedbrytningen rekursivt på en graf med toppunktsett , som følger: ${\ displaystyle V}$

Som et grunnleggende tilfelle, hvis den bare har ett toppunkt, er dens modulære nedbrytning en enkelt trenode. ${\ displaystyle G}$
Gallai viste at hvis den er tilkoblet og dens komplement, så er de maksimale modulene som er riktige undersett av en partisjon av . De er derfor en modulær partisjon. Kvoten som de definerer er prime. Roten av treet er merket med et primtall node, og disse moduler er tildelt som barn . Siden de er maksimale, er hver modul som ikke er representert så langt, inneholdt i et barn av . For hvert barn av , erstatter det med det modulære nedbrytningstreet av gir en representasjon av alle moduler av , av nøkkelobservasjonen ovenfor. ${\ displaystyle G}$ ${\ displaystyle V}$ ${\ displaystyle V}$ ${\ displaystyle V}$ ${\ displaystyle X}$ ${\ displaystyle V}$ ${\ displaystyle X}$ ${\ displaystyle V}$ ${\ displaystyle X}$ ${\ displaystyle G [X]}$ ${\ displaystyle G}$
Hvis den er frakoblet, er komplementet tilkoblet. Hver forening av tilkoblede komponenter er en modul av . Alle andre moduler er delsett av en enkelt tilkoblet komponent. Dette representerer alle moduler, bortsett fra delsett av tilkoblede komponenter. For hver komponent gir erstatning med det modulære dekomponeringstreet av en representasjon av alle moduler av , med nøkkelobservasjonen ovenfor. Roten til treet er merket som en parallell node, og den er festet i stedet for som et barn av roten. Kvoten definert av barna er komplementet til en komplett graf. ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle G [X]}$ ${\ displaystyle G}$ ${\ displaystyle X}$
Hvis komplementet til er frakoblet, er tilkoblet. Subtrærne som er barn av er definert på en måte som er symmetrisk med tilfellet der den er frakoblet, siden modulene i en graf er de samme som modulene i komplementet. Roten til treet er merket med en seriell node, og kvoten som er definert av barna er en komplett graf. ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle V}$ ${\ displaystyle G}$

Det endelige treet har ett-element sett med hjørner som bladene, på grunn av grunnkassen. Et sett med hjørner av er en modul hvis og bare hvis det er en node på treet eller en sammenslutning av barn i en serie eller parallell node. Dette gir implisitt alle modulære partisjoner av . Det er i denne forstand at det modulære nedbrytningstræret "undertrykker" alle andre måter å rekursivt dekomponere til kvotienter. ${\ displaystyle G}$ ${\ displaystyle Y}$ ${\ displaystyle G}$ ${\ displaystyle V}$ ${\ displaystyle G}$

Algoritmiske problemstillinger

En datastruktur for å representere det modulære dekomponeringstreet bør støtte operasjonen som legger inn en node og returnerer settet med hjørner for noden som representerer. En åpenbar måte å gjøre dette på er å tilordne hver node en liste over toppunktene til den den representerer. Gitt en peker til en node, kan denne strukturen returnere settet med hjørner for det den representerer i tide. Imidlertid vil denne datastrukturen kreve plass i verste fall. ${\ displaystyle G}$ ${\ displaystyle k}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle {\ mathcal {O}} (k)}$ ${\ displaystyle \ Theta (n^{2})}$

En fremstilling av den modulære nedbrytningen

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

Et alternativ til et mellomrom som samsvarer med denne ytelsen, oppnås ved å representere det modulære nedbrytningstreet ved å bruke en standard datastruktur med forankret tre og merke hvert blad med toppunktet til det det representerer. Settet representert av en intern node er gitt av settet med etiketter til bladets etterkommere. Det er velkjent at ethvert forankret tre med blader har de fleste interne noder. Man kan bruke et dybde-første søk som starter med å rapportere etikettene til blad-etterkommere av i tide. ${\ 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ære nedbrytningen, forsterket med en kvotient på barna til hver indre node, gir en fullstendig representasjon av .

{\ displaystyle G}

Hver node er et sett med hjørner av, og hvis det er en intern node, er settet med barn en partisjon av hvor hver partisjonsklasse er en modul. De induserer derfor kvoten i . Hodepunktene i denne kvoten er elementene i , så kan representeres ved å installere kanter blant barna til . Hvis og er to medlemmer av og og , så og er tilstøtende i hvis og bare hvis og er tilstøtende i denne kvoten. For et hvilket som helst par hjørner av , bestemmes dette av kvotienten til barn av den minst vanlige stamfaren til og i det modulære nedbrytningstreet. Derfor gir den modulære nedbrytningen, merket på denne måten med kvotienter, en fullstendig representasjon 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}$

Mange kombinatoriske problemer kan løses ved å løse problemet separat på hver av disse kvotientene. For eksempel er en sammenligningsgraf hvis og bare hvis hver av disse kvotientene er en sammenlignbarhetsgraf (Gallai, 67; Möhring, 85). Derfor, for å finne ut om en graf er en sammenlignbarhetsgraf, trenger du bare finne ut om hver av kvotientene er. For å finne en transitiv orientering av en sammenligningsgraf, er det faktisk tilstrekkelig å orientere hver av disse kvotientene i dens modulære nedbrytning (Gallai, 67; Möhring, 85). Et lignende fenomen gjelder permutasjonsgrafer (McConnell og Spinrad '94), intervallgrafer (Hsu og Ma '99), perfekte grafer og andre grafklasser. Noen viktige kombinatoriske optimaliseringsproblemer på grafer kan løses ved hjelp av en lignende strategi (Möhring, 85). ${\ displaystyle G}$ ${\ displaystyle G}$

Cographs er grafer som bare har parallelle eller seriens noder i deres modulære dekomponeringstreet.

Den første polynomiske algoritmen for å beregne det modulære dekomponeringstreet i en graf ble publisert i 1972 (James, Stanton & Cowan 1972) og nå er lineære algoritmer tilgjengelige (McConnell & Spinrad 1999, Tedder et al. 2007, Cournier & Habib 1994).

Generaliseringer

Modulær dekomponering av dirigerte grafer kan gjøres i lineær tid ( McConnell & de Montgolfier 2005 ).

Med et lite antall enkle unntak har hver graf med en ikke -modulær dekomponering også en skjev partisjon ( Reed 2008 ).

Referanser

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 for ustyrte grafer". Proc. Tredje sørøstlige internasjonale konferanse om kombinatorikk, grafteori og databehandling (Florida Atlantic Univ., Boca Raton, Fla., 1972) . Florida Atlantic University . s. 281–290. MR 0351909 .
Golumbic, Martin C. (1980). Algoritmisk grafteori og perfekte grafer . Academic Press. ISBN 0-444-51530-5.
Hsu, WL; Ma, T. (1999). "Raske og enkle algoritmer for å gjenkjenne akkord -sammenligningsgrafer og 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). "Modulær dekomponering i lineær tid av dirigerte grafer" . Diskret anvendt matematikk . 145 (2): 198–209. doi : 10.1016/j.dam.2004.02.017 .
McConnell, Ross M .; Spinrad, Jeremy P. (1999). "Modulær dekomponering og transitiv orientering" (PDF) . Diskret matematikk . 201 (1–3): 189–241. doi : 10.1016/S0012-365X (98) 00319-7 . MR 1687819 .
Möhring, Rolf H. (1985). I. Rival (red.). "Algoritmiske aspekter ved sammenlignbarhetsgrafer og intervallgrafer". Grafer og rekkefølge . D. Reidel: 41–101. doi : 10.1007/978-94-009-5315-4_2 . ISBN 978-94-010-8848-0.
Möhring, Rolf H. (1985). "Algoritmiske aspekter ved substitusjon dekomponering i optimalisering over relasjoner, sett systemer og boolske funksjoner". Annals of Operations Research . 4 : 195–225. doi : 10.1007/BF02022041 . S2CID 119982014 .
Papadopoulos, Charis; Voglis, Constantinos (2005). "Tegne grafer ved hjelp av modulær dekomponering" (PDF) . Proc. 13. internasjonale symposium om graftegning (GD'05) . Forelesningsnotater i informatikk. 3843 . Springer-Verlag. s. 343–354. doi : 10.1007/11618058_31 . MR 2229205 .
Reed, Bruce (2008). "Skeve partisjoner i perfekte grafer" (PDF) . Diskret anvendt matematikk . 156 (7): 1150–1156. doi : 10.1016/j.dam.2007.05.054 . MR 2404228 . Arkivert fra originalen (PDF) 2015-09-19 . Hentet 2012-08-13 .
Spinrad, Jeremy P. (2003). Effektive grafrepresentasjoner . Fields Institute Monografier. American Mathematical Society. ISBN 0-8218-2815-0.
Tedder, Marc; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008). "Enklere lineær tid modulær nedbrytning via rekursive faktoriserende permutasjoner". Proc. 35. internasjonale kollokvium om automatikk, språk og programmering (ICALP 2008) . Forelesningsnotater i informatikk. 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 dekomponering av grafer og avstandsbevarende eiendom" . Diskret anvendt matematikk . 265 (7): 192–198. arXiv : 1805.09853 . Bibkode : 2018arXiv180509853Z . doi : 10.1016/j.dam.2019.03.019 .

Languages

In other projects