Modulær nedbrydning

Modulær nedbrydning er nedbrydning af en graf i delmængder af toppunkter, kaldet moduler. Et modul er en generalisering af en forbundet komponent i en graf. I modsætning til tilslutningskomponenter kan et modul dog være sin egen undergruppe af et andet. Moduler fører derfor til en rekursiv (hierarkisk) dekomponering af grafen, ikke kun partitioner.

Modulære dekomponeringsvarianter findes for urettede grafer og rettede grafer . For hver urettet graf er en sådan dekomponering unik.

Begrebet kan generaliseres til andre strukturer (såsom rettede grafer) og er nyttigt til at udvikle effektive algoritmer til at genkende visse klasser af grafer, til at finde transitive orienteringer af sammenlignelighedsgrafer , til optimeringsproblemer på grafer og til visualisering af grafer .

Moduler

Konceptet med et modul er blevet genopdaget på mange områder. Til dette koncept blev navnene autonome mængder , homogene mængder , intervaller og brøkmængder brugt . Tilsyneladende var den tidligste omtale og den første beskrivelse af modulære kvotienter og opdelingen af grafer, der opstår i dette tilfælde, i Galais papir i 1967.

Grafmodulet er en generalisering af den tilsluttede komponent . En forbundet komponent har den egenskab, at den er et sæt toppunkter, således at ethvert medlem ikke er nabo til ethvert toppunkt, der ikke er i . En generalisering vil være, er et modul, når, for hvert toppunkt , enten ethvert medlem ikke er en nabo , eller ethvert medlem er en nabo . $x$ $x$ $x$ $x$ $v\ikke \i X$ $x$ $v$ $x$ $v$

Tilsvarende er et modul, hvis alle medlemmer har det samme sæt af naboer blandt hjørner, der ikke er i . $x$ $x$ $x$

I modsætning til forbundne komponenter er modulerne i en graf de samme som modulerne i dens komplement , og moduler kan "indlejres" - ét modul kan være sin egen delmængde af et andet. Bemærk, at toppunktet i en graf er et modul, ligesom singleton-sæt og det tomme sæt . De kaldes trivielle moduler . Grafen kan have andre moduler eller ej. En graf kaldes simpel , hvis alle dens moduler er trivielle. $V$

På trods af forskellene bevarer moduler den ønskede egenskab for forbundne komponenter, hvilket er, at mange egenskaber af subgrafen genereret af en tilsluttet komponent er uafhængige af resten af grafen. Et lignende fænomen observeres for subgrafer genereret af moduler. $G[X]$ $x$

Grafmoduler er derfor af stor algoritmisk interesse. Et sæt indlejrede moduler, som modulær ekspansion er et eksempel på, kan bruges til at opnå en rekursiv løsning på mange kombinatoriske problemer på grafer, såsom genkendelse og finding af den transitive orientering af sammenlignelighedsgrafer , genkendelse og søgning af permutationsrepræsentationen af permutationsgrafer , genkende om en graf er en kograf , genkende intervalgrafer og finde en intervalrepræsentation for den, definitionen af afstandsnedarvede grafer [1] og til grafvisualisering [2] . De spiller en vigtig rolle i beviset for den perfekte grafsætning [3] .

Til genkendelse af afstandsarvede grafer og cirkelgrafer er en yderligere generalisering af modulær dekomponering, kaldet split dekomponering [1] , særlig nyttig .

For at undgå tvetydigheden af ovenstående definition giver vi følgende formelle definition af moduler. . er et modul af en graf, hvis: $G=(V,E)$ $M\subseteq V$ $G$

hjørner kan ikke skelnes af et toppunkt i , det vil sige enten støder op til både , og c , eller ikke støder op til både , og . $M$ $V\backslash M$ $\forall u,v\in M,\forall x\in V\backslash M$ $x$ $u$ $v$ $x$ $u$ $v$
hjørnerne har det samme sæt af ydre naboer, dvs. $M$ $\forall u,v\in M,N(u)\setminus M=N(v)\setminus M$

$\tomt sæt$ , og alle singletons for er moduler, og de kaldes trivielle moduler . En graf er enkel , hvis alle dens moduler er trivielle. Forbindelseskomponenter i en graf eller deres komplementer er også moduler af en graf . $V$ ${\displaystyle \{v\))$ $v\in V$ $G$ $G$

$M$ er et stærkt grafmodul , hvis det ikke (delvist) overlapper noget andet grafmodul — grafmodulet er enten , eller , eller . $G$ $G$ $\forall M'$ $G$ $M\cap M'=\emptyset$ $M\subseteq M'$ $M'\subseteq M$

Modulære kvotienter og faktorer

Hvis og er usammenhængende moduler, så er det let at se, at enten er ethvert medlem nabo til ethvert element af , eller intet medlem støder op til noget medlem af . Således er alle elementer i to ikke-skærende moduler enten tilstødende eller ikke tilstødende . Der er ingen mellemtilstand mellem disse to yderpunkter. $x$ $Y$ $x$ $Y$ $x$ $Y$

I lyset af dette er modulære dekomponeringer , hvor hver dekomponeringsklasse er et modul, af særlig interesse. Antag, at det er en modulær nedbrydning. Da partitionsklasserne ikke skærer hinanden, danner deres naboskab en ny graf, kvotientgrafen , hvis hjørner er termerne . Det vil sige, at hvert toppunkt er et modul af grafen G, og nærheden af disse moduler definerer kanterne . $V$ $P$ $G/P$ $P$ $G/P$ $G/P$

I figuren nedenfor er top 1, top 2 til 4, top 5, top 6 og 7 og top 8 til 11 modulære. I diagrammet øverst til højre viser kanterne mellem disse sæt kvotienterne givet ved den givne nedbrydning, mens kanterne inden for sættene viser de tilsvarende faktorer.

Partitioner og er trivielle modulære partitioner . er en graf med ét hjørne, mens . Antag, at det er et ikke-trivielt modul. Så er et-element-undersættet også en ikke-triviel modulær partition . Således indebærer eksistensen af ikke -trivielle moduler eksistensen af ikke-trivielle modulpartitioner. Generelt kan de fleste eller alle medlemmer være ikke-trivielle moduler. $\{V\}$ $\{\{x\}|x\in V\}$ $G/\{V\}$ $G/\{\{x\}|x\in V\}=G$ $x$ $x$ $V\backslash X$ $V$ $P$

Hvis er en ikke-triviel modulær partition, så er en kompakt repræsentation af alle kanter, der ender i forskellige partitionsklasser . For hver undergraf kaldes partitionsklasse genereret af en faktor, og den giver en repræsentation af alle kanter med begge ender i . Således kan kanterne af en graf rekonstrueres, hvis kvotientgrafen og dens faktorer er kendt. Udtrykket simpel graf kommer fra det faktum, at en simpel graf kun har trivielle kvotienter og faktorer. $P$ $G/P$ $P$ $x$ $P$ $G[X]$ $x$ $x$ $G$ $G/P$

Hvis er en multiplikator af modulo-kvotienten , kan det vise sig, at der kan faktoriseres rekursivt og kvotienter. Hvert niveau af rekursion giver en kvotient. Som basistilfælde har grafen ét toppunkt. Grafen kan rekonstrueres ved at rekonstruere faktorer nedefra, vende partitioneringstrinene ved at samle faktorer med kvotienter på hvert niveau. $G[X]$ $G/P$ $G[X]$ $G$

I figuren nedenfor er en sådan rekursiv dekomponering repræsenteret som et træ, hvilket afspejler en af måderne til rekursivt at faktorisere de indledende modulære dekomponeringsfaktorer i mindre modulære partitioner.

Metoden til rekursivt at opdele en graf i faktorer og kvotienter er muligvis ikke den eneste. (For eksempel er alle delmængder af hjørnerne af en komplet graf moduler, hvilket betyder, at der er mange forskellige måder at dekomponere den graf på rekursivt.) Nogle måder at dekomponere kan være mere nyttige end andre.

Modularisering

Heldigvis er der en rekursiv dekomponering af en graf, der implicit repræsenterer alle de måder, hvorpå den kan dekomponeres. Dette er modularisering. Det er i sig selv en måde at rekursivt dekomponere en graf i kvotienter, men den inkluderer alle de andre. Nedbrydningen vist i figuren nedenfor er en speciel dekomponering af den givne graf.

Nedenfor er en central observation til forståelse af modulær nedbrydning:

Hvis er et modul af grafen og er en delmængde af $x$ $G$ $Y$ $x$ , så er et modul hvis og kun hvis det er et modul af . $Y$ $G$ $G[X]$

Gallai [4] definerede en modulær dekomponering rekursivt på en graf med mange hjørner som følger: $V$

I basistilfældet, hvis den kun har et toppunkt, er dens modulære nedbrydning et træ med en knude. $G$
Gallai viste, at hvis er forbundet, og det samme er dets komplement, så er de maksimale moduler, som er korrekte delmængder af , en partition af . De er derfor modulopbyggede. De kvotienter, de definerer, er enkle. Træets rod er markeret som en simpel node, og disse moduler accepteres af sættets efterkommere . Fordi de er maksimale, er ethvert modul, der ikke er repræsenteret på denne måde, indeholdt i efterkommeren af . For hver efterkommer af sættet, udskiftning af modulariseringstræet med et modulært nedbrydningstræ giver en repræsentation af alle modulerne i grafen, i henhold til nøgleobservationen ovenfor. $G$ $V$ $V$ $V$ $x$ $V$ $x$ $V$ $x$ $G[X]$ $G$
Hvis den ikke er forbundet, er dens komplement forbundet. Enhver forening af tilsluttede komponenter er et grafmodul . Alle andre moduler er undersæt af en separat tilslutningskomponent. Dette repræsenterer alle moduler undtagen undersæt af tilslutningskomponenter. For hver komponent giver udskiftning med et modulært nedbrydningstræ en repræsentation af alle moduler i grafen i overensstemmelse med nøgleobservationen ovenfor. Træets rod er markeret som en parallel knude, men er et barn af roden. Kvotienten defineret af efterkommeren er komplementet til den komplette graf. $G$ $G$ $x$ $x$ $G[X]$ $G$ $x$
Hvis komplementet af grafen ikke er forbundet, er grafen forbundet. De undertræer, der er børn af , er defineret symmetrisk i det tilfælde, hvor grafen ikke er forbundet, da grafens moduler er de samme som modulerne i dens komplement. Træets rod er mærket som en sekventiel node, og kvotienten defineret af efterkommerne er den komplette graf. $G$ $G$ $V$ $G$

Det endelige træ har et enkelt sæt af grafhjørner som blade, som er basissagen. Et sæt grafhjørner er et modul, hvis og kun hvis det er en træknude eller en forening af efterkommere af en seriel eller parallel knude. Dette tildeler implicit alle modulære udvidelser til toppen . I denne forstand "koncentrerer det modulære nedbrydningstræ i sig selv" alle andre måder at rekursivt dekomponere en graf til delvise. $G$ $Y$ $G$ $V$ $G$

Algoritmiske problemer

Datastrukturen til at repræsentere et modulært nedbrydningstræ skal understøtte operationer, der tager en node som input og returnerer det sæt af grafspidser , som knudepunktet repræsenterer. Den oplagte måde at gøre dette på er at tildele hver knude en liste over hjørner i grafen , som knudepunktet repræsenterer. Givet en pointer til en knude, kan det sæt af grafspidser , som knudepunktet repræsenterer, hentes i tide . En sådan struktur vil dog i værste fald kræve hukommelse . $G$ $k$ $G$ $G$ ${\mathcal {O}}(k)$ $\Theta (n^{2})$

Hukommelsesalternativet opnås ved at repræsentere det modulære nedbrydningstræ med en hvilken som helst standard rodfæstet træbaseret datastruktur og mærke hvert blad med det grafiske toppunkt , det repræsenterer. Sættet repræsenteret af den interne node er defineret af sættet af etiketter af dets efterkommerblade. Det er velkendt, at ethvert rodfæstet træ med blade højst har indre noder. Du kan bruge dybde-først-søgning startende ved for at få etiketter af efterkommerblade på et tidspunkt . ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$ $G$ $v$ $k$ $k-1$ $v$ $v$ ${\mathcal {O}}(k)$

Hver knude er et sæt af hjørner i grafen , og hvis det er en intern knude, er sættet af efterkommere en opdeling , hvor hver opdelt klasse er et modul. Derfor genererer de en kvotient i . Hjørnerne i denne kvotient er elementer af , så de kan repræsenteres ved at etablere kanter mellem børnene af . Hvis og er to led og , , Så og er tilstødende i hvis og kun hvis og er tilstødende i kvotienten. For ethvert par af grafhjørner bestemmes dette af de private efterkommere af den største fælles forfader og i det modulære nedbrydningstræ. Derfor giver en modulær dekomponering mærket som kvotienter på denne måde en komplet repræsentation af 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$ $\{u,v\}$ $G$ ${\displaystyle \{u\))$ ${\displaystyle \{v\))$ $G$

Mange kombinatoriske problemer kan løses på en graf ved at løse dem separat for hver kvotient. For eksempel er en sammenlignelighedsgraf, hvis og kun hvis hver af disse kvotienter er en sammenlignelighedsgraf [4] [5] . For at afgøre, om en graf er en sammenlignelighedsgraf, er det derfor tilstrækkeligt at kontrollere dette for hver af dens kvotienter. Faktisk, for at finde den transitive orientering af en sammenlignelighedsgraf, er det tilstrækkeligt at finde den transitive orientering af hver af dens kvotienter i den modulære dekomponering [4] [5] . Et lignende fænomen findes for permutationsgrafer [6] , intervalgrafer [7] , perfekte grafer og andre klasser af grafer. Nogle vigtige kombinatoriske optimeringsproblemer på grafer kan løses ved hjælp af lignende strategier [8] . $G$ $G$

Kografer er grafer, der kun har parallelle eller sekventielle noder i deres modulære nedbrydningstræ.

Den første polynomiske tidsalgoritme til beregning af det modulære nedbrydningstræ af en graf blev offentliggjort i 1972 [9] , og lineære tidsalgoritmer er nu tilgængelige [6] [10] .

Generaliseringer

Modulær dekomponering af rettede grafer kan opnås i lineær tid [11] .

Med nogle få enkle undtagelser har enhver graf med en ikke-triviel modulær dekomponering også en skæv partition [12] .

Noter

↑ 12 Spinrad , 2003 .
↑ Papadopoulos, Voglis, 2005 .
↑ Golumbic, 1980 .
↑ 1 2 3 Gallai, 1967 , s. 25-66.
↑ 12 Möhring , 1985a , s. 41-101.
↑ 1 2 McConnell, Spinrad, 1999 , s. 189-241.
↑ Hsu, Ma, 1999 , s. 1004-1020.
↑ Möhring, 1985b , s. 195-225.
↑ James, Stanton, Cowan, 1972 , s. 281-290.
↑ Tedder, Corneil, Habib, Paul, 2008 , s. 634-645.
↑ McConnell, de Montgolfier, 2005 , s. 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. Grafnedbrydning for urettede grafer // Proc. 3. 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 og perfekte grafer. - Academic Press, 1980. - ISBN 0-444-51530-5 .
Hsu WL, Ma T. Hurtige og enkle algoritmer til genkendelse af akkordsammenlignelighedsgrafer og intervalgrafer // SIAM Journal on Computing. - 1999. - T. 28 , no. 3 . - doi : 10.1137/S0097539792224814 .
Ross M. McConnell, Fabien de Montgolfier. Lineær-tids modulær dekomponering af rettede grafer // Diskret anvendt matematik. - 2005. - T. 145 , no. 2 . - doi : 10.1016/j.dam.2004.02.017 .
Ross M. McConnell, Jeremy P. Spinrad. Modulær nedbrydning og transitiv orientering // Diskret matematik . - 1999. - T. 201 . - doi : 10.1016/S0012-365X(98)00319-7 .
Rolf H. Möhring. Algoritmiske aspekter af sammenlignelighedsgrafer og intervalgrafer // Grafer og rækkefølge. — D. Reidel, 1985a.
Rolf H. Möhring. Algoritmiske aspekter af substitutionsnedbrydningen i optimering over relationer, sætsystemer og booleske funktioner // Annals of Operations Research. - 1985b. - T. 4 . - doi : 10.1007/BF02022041 .
Charis Papadopoulos, Constantinos Voglis. Tegning af grafer ved hjælp af modulær dekomponering // Proc. 13. internationale symposium om graftegning (GD'05) . - Springer-Verlag, 2005. - T. 3843. - (Lecture Notes in Computer Science). - doi : 10.1007/11618058_31 .
Bruce Reed. Skæv partitioner i perfekte grafer // Diskret anvendt matematik. - 2008. - T. 156 , no. 7 . - S. 1150-1156 . - doi : 10.1016/j.dam.2007.05.054 . Arkiveret fra originalen den 19. september 2015.
Jeremy P Spinrad. Effektive grafrepræsentationer. - American Mathematical Society, 2003. - (Fields Institute Monographs). — ISBN 0-8218-2815-0 .
Marc Tedder, Derek Corneil, Michel Habib, Christophe Paul. Enklere lineær-tidsmodulær dekomponering via rekursive faktoriserende permutationer // Proc. 35. internationale kollokvium om automater, sprog og 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 nedbrydning af grafer og den afstandsbevarende egenskab // Diskret anvendt matematik. - 2018. - Udgave. 7 .