Modulaarinen hajoaminen

Modulaarinen hajottelu on graafin hajoamista kärkien osajoukkoihin, joita kutsutaan moduuleiksi. Moduuli on graafin yhdistetyn komponentin yleistys. Toisin kuin liitettävyyskomponentit, yksi moduuli voi kuitenkin olla toisen osajoukko . Siksi moduulit johtavat graafin rekursiiviseen (hierarkkiseen) hajotukseen, eivät vain osioihin.

Suuntaamattomille ja suunnatuille graafeille on olemassa modulaarisia hajottelumuunnelmia . Jokaiselle suuntaamattomalle graafille tällainen jaottelu on ainutlaatuinen.

Käsite voidaan yleistää muihin rakenteisiin (kuten suunnattuihin kaavioihin), ja se on hyödyllinen kehitettäessä tehokkaita algoritmeja tiettyjen graafiluokkien tunnistamiseen , vertailtavien kaavioiden transitiivisten suuntausten löytämiseen , kaavioiden optimointiongelmiin ja kaavioiden visualisointiin .

Moduulit

Moduulin käsite on löydetty uudelleen monilta aloilta. Tätä käsitettä varten käytettiin nimiä autonomiset joukot , homogeeniset joukot , intervallit ja murtolukujoukot . Ilmeisesti varhaisin maininta ja ensimmäinen kuvaus tässä tapauksessa esiintyvistä modulaarisista osamääräistä ja graafien osittamisesta oli Galain artikkelissa vuonna 1967.

Graafimoduuli on yleistys yhdistetystä komponentista . Yhdistetyllä komponentilla on ominaisuus, että se on joukko pisteitä siten, että mikään jäsen ei ole minkään muun kuin pisteen naapuri . Yleistys on, on moduuli, kun jokaisessa kärjessä joko mikään jäsen ei ole naapuri tai mikä tahansa jäsen on naapuri . $X$ $X$ $X$ $X$ $v\not \in X$ $X$ $v$ $X$ $v$

Vastaavasti on moduuli, jos kaikilla jäsenillä on samat naapurit sellaisten kärkien joukossa, jotka eivät ole :ssä . $X$ $X$ $X$

Toisin kuin yhdistetyt komponentit, graafin moduulit ovat samat kuin sen komplementin moduulit, ja moduulit voidaan "sisäistää" - yksi moduuli voi olla toisen osajoukko. Huomaa, että graafin kärkijoukko on moduuli, samoin kuin yksittäiset joukot ja tyhjä joukko . Niitä kutsutaan triviaalimoduuleiksi . Kaaviossa voi olla muita moduuleja tai ei. Graafia kutsutaan yksinkertaiseksi , jos kaikki sen moduulit ovat triviaaleja. $V$

Eroista huolimatta moduulit säilyttävät halutun yhdistetyn komponentin ominaisuuden, eli monet yhdistetyn komponentin generoiman aligraafin ominaisuudet ovat riippumattomia muusta graafista. Samanlainen ilmiö havaitaan moduulien generoimien osagraafien kohdalla. $G[X]$ $X$

Graafimoduulit ovat siksi erittäin kiinnostavia algoritmisesti. Joukko sisäkkäisiä moduuleja, joista modulaarinen laajennus on esimerkki, voidaan käyttää rekursiivisen ratkaisun saamiseksi moniin kaavioiden kombinatorisiin ongelmiin, kuten vertailtavien graafien transitiivisen suunnan tunnistamiseen ja löytämiseen, permutaatiokaavioiden permutaatioesityksen tunnistamiseen ja löytämiseen . , tunnistaa, onko graafi kografi , tunnistaa intervallikuvaajat ja löytää sille intervalliesityksen , etäisyyden periytyvien graafien määrittely [1] ja graafin visualisointi [2] . Niillä on tärkeä rooli täydellisen graafin lauseen todistuksessa [3] .

Etäisyyden perittyjen kuvaajien ja ympyräkaavioiden tunnistamiseksi modulaarisen hajotuksen lisäyleistys, jota kutsutaan split-hajotelmaksi [1] , on erityisen hyödyllinen .

Yllä olevan määritelmän epäselvyyden välttämiseksi annamme seuraavan muodollisen määritelmän moduuleille. . on graafin moduuli , jos: $G=(V,E)$ $M\subseteq V$ $G$

kärkipisteitä ei voida erottaa pisteellä , eli joko molempien ja c :n vieressä tai ei molempien ja ja . $M$ $V\backslash M$ $\forall u,v\in M,\forall x\in V\backslash M$ $x$ $u$ $v$ $x$ $u$ $v$
pisteillä on sama joukko ulkonaapureita, eli . $M$ $\forall u,v\in M,N(u)\setminus M=N(v)\setminus M$

$\emptyset$ , ja kaikki singletons for ovat moduuleja ja niitä kutsutaan triviaalimoduuleiksi . Graafi on yksinkertainen , jos kaikki sen moduulit ovat triviaaleja. Graafin liitettävyyskomponentit tai niiden komplementit ovat myös graafin moduuleja . $V$ ${\näyttötyyli \{v\))$ $v\in V$ $G$ $G$

$M$ on vahva graafimoduuli , jos se ei ole (osittain) päällekkäinen minkään muun grafiikkamoduulin kanssa — graafimoduuli on joko , tai , tai . $G$ $G$ $\forall M'$ $G$ $M\cap M'=\emptyset$ $M\subseteq M'$ $M'\subseteq M$

Modulaariset osamäärät ja tekijät

Jos ja ovat disjunktoituja moduuleja, on helppo nähdä, että joko mikä tahansa jäsen on minkä tahansa elementin naapuri tai mikään jäsen ei ole minkään :n jäsenen vieressä . Siten kahden ei-leikkaavan moduulin kaikki elementit ovat joko vierekkäin tai eivät vierekkäin . Näiden kahden ääripään välillä ei ole välitilaa. $X$ $Y$ $X$ $Y$ $X$ $Y$

Tämän vuoksi modulaariset hajotukset , joissa jokainen hajotteluluokka on moduuli, ovat erityisen kiinnostavia. Oletetaan, että se on modulaarinen hajotelma. Koska osioluokat eivät leikkaa, muodostaa niiden vierekkäisyydestä uuden graafin, osamäärägraafin , jonka kärjet ovat termit . Toisin sanoen jokainen kärkipiste on graafin G moduuli, ja näiden moduulien viereisyys määrittää reunat . $V$ $P$ $G/P$ $P$ $G/P$ $G/P$

Alla olevassa kuvassa kärki 1, pisteet 2 - 4, kärki 5, pisteet 6 ja 7 sekä pisteet 8 - 11 ovat modulaarisia. Yläoikeassa kaaviossa näiden joukkojen väliset reunat osoittavat annetun jaottelun osamäärät, kun taas joukkojen sisällä olevat reunat vastaavat tekijät.

Osiot ja ovat triviaaleja modulaarisia osioita . on yhden kärjen graafi, kun taas . Oletetaan, että se on ei-triviaali moduuli. Tällöin yksielementtiosajoukko on myös ei-triviaali modulaarinen osio . Siten kaikkien ei-triviaalien moduulien olemassaolo tarkoittaa ei-triviaalien moduuliosioiden olemassaoloa. Yleensä useimmat tai kaikki jäsenet voivat olla ei-triviaaleja moduuleja. ${\näyttötyyli \{V\))$ $\{\{x\}|x\in V\}$ $G/\{V\}$ $G/\{\{x\}|x\in V\}=G$ $X$ $X$ $V\backslash X$ $V$ $P$

If on ei-triviaali modulaarinen osio, niin se on kompakti esitys kaikista reunoista, jotka päättyvät eri osioluokkiin . Jokaiselle aligraafin luomaa luokkaa kutsutaan tekijäksi ja se antaa esityksen kaikista reunoista, joiden molemmat päät ovat . Siten graafin reunat voidaan rekonstruoida, jos osamäärägraafi ja sen tekijät tunnetaan. Termi yksinkertainen graafi tulee siitä tosiasiasta, että yksinkertaisella graafilla on vain triviaaleja osamäärät ja tekijät. $P$ $G/P$ $P$ $X$ $P$ $G[X]$ $X$ $X$ $G$ $G/P$

Jos on kerroin moduuliosamäärästä , voi käydä ilmi, että se voidaan kertoa rekursiivisesti ja osamäärät. Jokainen rekursiotaso tuottaa osamäärän. Perustapauksessa graafilla on yksi kärki. Graafi voidaan rekonstruoida rekonstruoimalla tekijöitä alhaalta, kääntämällä osiointivaiheet kokoamalla kertoimia osamäärällä kullakin tasolla. $G[X]$ $G/P$ $G[X]$ $G$

Alla olevassa kuvassa tällainen rekursiivinen hajotelma on esitetty puuna, joka kuvastaa yhtä tapaa rekursiivisesti jakaa alkuperäiset modulaariset hajottelutekijät pienempiin modulaarisiin osioihin.

Menetelmä graafin rekursiiviseksi osittamiseksi tekijöiksi ja osamääräiksi ei ehkä ole ainoa. (Esimerkiksi kaikki täydellisen graafin kärkien osajoukot ovat moduuleja, mikä tarkoittaa, että on monia eri tapoja hajottaa graafi rekursiivisesti.) Jotkut hajotustavat voivat olla hyödyllisempiä kuin toiset.

Modularisointi

Onneksi on olemassa graafin rekursiivinen hajottaminen, joka edustaa implisiittisesti kaikkia tapoja, joilla se voidaan hajottaa. Tämä on modularisointia. Se on itsessään tapa hajottaa graafi rekursiivisesti osamääräiksi, mutta se sisältää kaikki muut. Alla olevassa kuvassa esitetty hajotus on tietyn graafin erityinen hajotelma.

Alla on keskeinen havainto modulaarisen hajoamisen ymmärtämiseksi:

If on kaavion moduuli ja on osajoukko $X$ $G$ $Y$ $X$ , niin on moduuli silloin ja vain, jos se on moduulin . $Y$ $G$ $G[X]$

Gallai [4] määritteli modulaarisen hajautuksen rekursiivisesti graafille, jossa on useita pisteitä seuraavasti: $V$

Perustapauksessa, jos sillä on vain yksi kärki, sen modulaarinen hajotelma on puu, jossa on yksi solmu. $G$
Gallai osoitti, että jos on kytketty ja niin on myös sen komplementti, niin maksimimoduulit, jotka ovat oikeita osajoukkoja , ovat osio . Siksi ne ovat modulaarisia. Niiden määrittämät osamäärät ovat yksinkertaisia. Puun juuri on merkitty yksinkertaiseksi solmuksi, ja joukon jälkeläiset hyväksyvät nämä moduulit . Koska ne ovat maksimaalisia, kaikki moduulit, joita ei esitetä tällä tavalla, sisältyvät :n jälkeläiseen . Joukon kullekin jälkeläiselle modularisointipuun korvaaminen modulaarisella hajotuspuulla antaa esityksen kaikista graafin moduuleista yllä olevan avainhavainnon mukaisesti. $G$ $V$ $V$ $V$ $X$ $V$ $X$ $V$ $X$ $G[X]$ $G$
Jos sitä ei ole kytketty, sen komplementti on kytketty. Mikä tahansa yhdistettyjen komponenttien liitto on kuvaajamoduuli . Kaikki muut moduulit ovat erillisen liitettävyyskomponentin osajoukkoja. Tämä edustaa kaikkia moduuleja paitsi liitettävyyskomponenttien osajoukkoja. Kunkin komponentin korvaaminen modulaarisella hajotuspuulla antaa esityksen kaikista graafin moduuleista yllä olevan keskeisen havainnon mukaisesti. Puun juuri on merkitty rinnakkaiseksi solmuksi, mutta se on juuren lapsi. Jälkeläisen määrittelemä osamäärä on kokonaisen graafin komplementti. $G$ $G$ $X$ $X$ $G[X]$ $G$ $X$
Jos graafin komplementtia ei ole yhdistetty, graafi on yhdistetty. Alipuut, jotka ovat lapsia, määritellään symmetrisesti tapaukseen, jossa graafia ei ole yhdistetty, koska graafin moduulit ovat samat kuin sen komplementin moduulit. Puun juuri on merkitty peräkkäiseksi solmuksi, ja jälkeläisten määrittelemä osamäärä on täydellinen graafi. $G$ $G$ $V$ $G$

Lopullisessa puussa on yksittäinen joukko graafin kärkipisteitä lehtinä, jotka ovat perustapaus. Graafin kärkien joukko on moduuli silloin ja vain, jos se on puusolmu tai sarja- tai rinnakkaissolmun jälkeläisten liitto. Tämä määrittää implisiittisesti kaikki modulaariset laajennukset yläosaan . Tässä mielessä modulaarinen hajautuspuu "keskittää itseensä" kaikki muut tavat hajottaa graafi rekursiivisesti osittaisiksi. $G$ $Y$ $G$ $V$ $G$

Algoritmiset ongelmat

Modulaarisen hajottelupuun esittämiseen tarkoitetun tietorakenteen on tuettava operaatioita, jotka ottavat syötteeksi solmun ja palauttavat solmun edustaman graafin kärkijoukon . Ilmeinen tapa tehdä tämä on määrittää kullekin solmulle luettelo graafin pisteistä, joita solmu edustaa. Annettu osoitin solmuun, solmun edustama graafin kärkijoukko voidaan hakea ajassa . Tällainen rakenne vaatii kuitenkin muistia pahimmassa tapauksessa . $G$ $k$ $G$ $G$ ${\mathcal {O}}(k)$ $\Theta (n^{2})$

Muistivaihtoehto saadaan esittämällä modulaarinen hajotuspuu millä tahansa tavallisella juurtuneella puupohjaisella tietorakenteella ja merkitsemällä jokainen lehti sen edustamalla graafin kärjellä. Sisäisen solmun edustama joukko määritellään sen jälkeläisten lehtien etiketeillä. Tiedetään hyvin, että missä tahansa juurtuneessa puussa, jossa on lehtiä, on enintään sisäisiä solmuja. Voit käyttää syvyyshakua alkaen numerosta saadaksesi jälkeläisten lehtien tunnisteet kerralla . ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$ $G$ $v$ $k$ $k-1$ $v$ $v$ ${\mathcal {O}}(k)$

Jokainen solmu on joukko graafin pisteitä, ja jos se on sisäinen solmu, jälkeläisten joukko on jako , jossa jokainen jaettu luokka on moduuli. Siksi ne tuottavat osamäärän . Tämän osamäärän kärjet ovat elementtejä , joten ne voidaan esittää muodostamalla reunat luvun lasten välille . Jos ja ovat kaksi termiä ja , , Sitten ja ovat vierekkäisiä, jos ja vain jos ja ovat vierekkäisiä osamäärässä. Kaikille graafin kärkipisteiden parille tämän määrittävät suurimman yhteisen esi-isän yksityiset jälkeläiset ja modulaarinen hajotuspuu. Siksi tällä tavalla osamääräiksi merkitty modulaarinen hajotelma antaa graafin täydellisen esityksen . $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$ ${\näyttötyyli \{u,v\))$ $G$ $\{u\}$ ${\näyttötyyli \{v\))$ $G$

Monet kombinatoriset ongelmat voidaan ratkaista graafilla ratkaisemalla ne erikseen kullekin osamäärälle. Onko esimerkiksi vertailukäyrä jos ja vain jos jokainen osamäärä on vertailukelpoisuuskaavio [4] [5] . Siksi sen määrittämiseksi, onko graafi vertailukelpoinen graafi, riittää tarkistaa tämä kunkin osamäärän osalta. Itse asiassa vertailtavuusgraafin transitiivisen orientaation löytämiseksi riittää löytää kunkin osamäärän transitiivinen orientaatio modulaarisessa hajotuksessa [4] [5] . Samanlainen ilmiö havaitaan permutaatiograafien [6] , intervalligraafien [7] , täydellisen graafin ja muiden graafiluokkien kohdalla. Jotkut tärkeät graafien kombinatoriset optimointiongelmat voidaan ratkaista käyttämällä samanlaisia strategioita [8] . $G$ $G$

Kuvaajat ovat kaavioita, joiden modulaarisessa hajottelupuussa on vain rinnakkaisia tai peräkkäisiä solmuja.

Ensimmäinen polynomiaikaalgoritmi graafin modulaarisen hajottelupuun laskemiseen julkaistiin vuonna 1972 [9] , ja nyt on saatavilla lineaarisia aikaalgoritmeja [6] [10] .

Yleistykset

Suunnattujen graafien modulaarinen hajotus voidaan saada lineaarisessa ajassa [11] .

Muutamia yksinkertaisia poikkeuksia lukuun ottamatta jokaisella graafilla, jolla on ei-triviaali modulaarinen hajottelu, on myös vino osio [12] .

Muistiinpanot

↑ 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 .

Kirjallisuus

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. Suuntaamattomien graafien kuvaajahajotus // Proc. 3. Southeastern International Conference on Combinatoriics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972). - Florida Atlantic University , 1972.
Martin C. Golumbic. Algoritminen graafiteoria ja täydelliset kuvaajat. - Academic Press, 1980. - ISBN 0-444-51530-5 .
Hsu WL, Ma T. Nopeat ja yksinkertaiset algoritmit sointuvertailukaavioiden ja intervallikaavioiden tunnistamiseen // SIAM Journal on Computing. - 1999. - T. 28 , no. 3 . - doi : 10.1137/S0097539792224814 .
Ross M. McConnell, Fabien de Montgolfier. Suunnattujen graafien lineaariaikainen modulaarinen hajottaminen // Discrete Applied Mathematics. - 2005. - T. 145 , no. 2 . - doi : 10.1016/j.dam.2004.02.017 .
Ross M. McConnell, Jeremy P. Spinrad. Modulaarinen hajottelu ja transitiivinen suuntaus // Diskreetti matematiikka . - 1999. - T. 201 . - doi : 10.1016/S0012-365X(98)00319-7 .
Rolf H. Möhring. Vertailukaavioiden ja intervallikaavioiden algoritmiset näkökohdat // Graphs and Order. - D. Reidel, 1985a.
Rolf H. Möhring. Korvaushajottamisen algoritmiset näkökohdat suhteiden, joukkojärjestelmien ja Boolen funktioiden optimoinnissa // Annals of Operations Research. – 1985b. - T. 4 . - doi : 10.1007/BF02022041 .
Charis Papadopoulos, Constantinos Voglis. Graafisten piirtäminen modulaarista hajotusta käyttäen // Proc. 13th International Symposium on Graph Drawing (GD'05) . - Springer-Verlag, 2005. - T. 3843. - (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/11618058_31 .
Bruce Reed. Vino osiot täydellisissä kaavioissa // Discrete Applied Mathematics. - 2008. - T. 156 , no. 7 . - S. 1150-1156 . - doi : 10.1016/j.dam.2007.05.054 . Arkistoitu alkuperäisestä 19. syyskuuta 2015.
Jeremy P Spinrad. Tehokkaat graafiset esitykset. - American Mathematical Society, 2003. - (Fields Institute Monographs). — ISBN 0-8218-2815-0 .
Marc Tedder, Derek Corneil, Michel Habib, Christophe Paul. Yksinkertaisempi lineaariaikainen modulaarinen hajottaminen rekursiivisten tekijöiden permutaatioiden avulla // Proc. 35. kansainvälinen kollokviumi automaateista, kielistä ja ohjelmoinnista (ICALP 2008) . - Springer-Verlag, 2008. - T. 5125. - (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/978-3-540-70575-8_52 .
Emad Zahedi, Jason Smith. Graafisten modulaarinen hajottaminen ja etäisyyden säilyttämisominaisuus // Diskreetti sovellettu matematiikka. - 2018. - Numero. 7 .

Linkit

Perl Modulaarisen hajottelualgoritmin toteutus
Modulaarisen hajottelualgoritmin Java - toteutus
Modulaarisen hajottelualgoritmin toteutus Juliassa