Modulární rozklad

Modulární rozklad je rozklad grafu na podmnožiny vrcholů, nazývané moduly. Modul je zobecněním spojené složky grafu. Na rozdíl od komponent konektivity však může být jeden modul svou vlastní podmnožinou jiného. Moduly tedy vedou k rekurzivnímu (hierarchickému) rozkladu grafu, nikoli pouze oddílů.

Existují varianty modulárního rozkladu pro neorientované grafy a řízené grafy . Pro každý neorientovaný graf je takový rozklad jedinečný.

Tento pojem lze zobecnit na další struktury (jako jsou orientované grafy) a je užitečný pro vývoj účinných algoritmů pro rozpoznávání určitých tříd grafů, pro nalezení tranzitivních orientací grafů srovnatelnosti , pro optimalizační problémy na grafech a pro vizualizaci grafů .

Moduly

Koncept modulu byl znovu objeven v mnoha oblastech. Pro tento koncept byly použity názvy autonomní množiny , homogenní množiny , intervaly a zlomkové množiny . Zdá se, že nejstarší zmínka a první popis modulárních kvocientů a rozdělení grafů, které v tomto případě vznikají, byly v Galaiově článku v roce 1967.

Modul grafu je zobecněním připojené komponenty . Připojená komponenta má tu vlastnost, že jde o množinu vrcholů, takže žádný člen není sousedem žádného vrcholu mimo . Zobecnění bude, je modul, když pro každý vrchol buď kterýkoli člen není sousedem nebo kterýkoli člen je sousedem . $X$ $X$ $X$ $X$ $v\not \in X$ $X$ $proti$ $X$ $proti$

Ekvivalentně je modul, pokud mají všechny členy stejnou sadu sousedů mezi vrcholy, které nejsou v . $X$ $X$ $X$

Na rozdíl od připojených komponent jsou moduly grafu stejné jako moduly jeho doplňku a moduly lze „vnořovat“ – jeden modul může být vlastní podmnožinou druhého. Všimněte si, že množina vrcholů grafu je modul, stejně jako množiny singleton a prázdná množina . Říká se jim triviální moduly . Graf může nebo nemusí mít další moduly. Graf se nazývá jednoduchý , pokud jsou všechny jeho moduly triviální. $PROTI$

Navzdory rozdílům si moduly zachovávají požadovanou vlastnost připojených komponent, což je, že mnoho vlastností podgrafu generovaného připojenou komponentou je nezávislých na zbytku grafu. Podobný jev je pozorován u podgrafů generovaných moduly. $G[X]$ $X$

Grafové moduly jsou proto velmi zajímavé z hlediska algoritmů. Sadu vnořených modulů, jejichž příkladem je modulární expanze, lze použít k získání rekurzivního řešení mnoha kombinatorických problémů na grafech, jako je rozpoznání a nalezení tranzitivní orientace grafů srovnatelnosti , rozpoznání a nalezení permutační reprezentace permutačních grafů. , rozpoznání, zda je graf kografem , rozpoznání intervalových grafů a nalezení pro něj intervalové reprezentace, definice vzdálenostně zděděných grafů [1] a pro vizualizaci grafů [2] . Hrají důležitou roli při důkazu věty o dokonalém grafu [3] .

Pro rozpoznání vzdálenostně zděděných grafů a kruhových grafů je zvláště užitečné další zobecnění modulárního rozkladu, nazývané dělený rozklad [1] .

Abychom se vyhnuli nejednoznačnosti výše uvedené definice, uvádíme následující formální definici modulů. . je modul grafu , pokud: $G=(V,E)$ $M\subseteq V$ $G$

vrcholy nemohou být rozlišeny vrcholem v , to je buď sousedící s oběma , a c , nebo nesousedící s oběma , a . $M$ $V\obrácené lomítko M$ $\forall u,v\in M,\forall x\in V\obrácené lomítko M$ $X$ $u$ $proti$ $X$ $u$ $proti$
vrcholy mají stejnou množinu vnějších sousedů, tj . $M$ $\forall u,v\in M,N(u)\setminus M=N(v)\setminus M$

$\emptyset$ , a všechny singletony pro jsou moduly a nazývají se triviální moduly . Graf je jednoduchý , pokud jsou všechny jeho moduly triviální. Konektivní komponenty grafu nebo jejich doplňky jsou také moduly grafu . $PROTI$ ${\displaystyle \{v\))$ $v\in V$ $G$ $G$

$M$ je silný grafový modul , pokud (částečně) nepřekrývá žádný jiný grafový modul — grafový modul je buď , nebo , nebo . $G$ $G$ $\forall M'$ $G$ $M\cap M'=\emptyset$ $M\subseteq M'$ $M'\subseteq M$

Modulární kvocienty a faktory

Jestliže a jsou disjunktní moduly, pak je snadné vidět, že buď kterýkoli člen je sousedem libovolného prvku , nebo žádný člen nesousedí s žádným členem . Všechny prvky dvou neprotínajících se modulů tedy buď sousedí , nebo nesousedí . Mezi těmito dvěma extrémy neexistuje žádný mezistav. $X$ $Y$ $X$ $Y$ $X$ $Y$

Vzhledem k tomu jsou zvláště zajímavé modulární dekompozice , kde každá třída dekompozice je modulem. Předpokládejme, že jde o modulární rozklad. Protože se třídy oddílů neprotínají, jejich sousedství tvoří nový graf, graf podílu , jehož vrcholy jsou členy . To znamená, že každý vrchol je modulem grafu G a sousedství těchto modulů definuje hrany . $PROTI$ $P$ $G/P$ $P$ $G/P$ $G/P$

Na obrázku níže jsou vrchol 1, vrcholy 2 až 4, vrchol 5, vrcholy 6 a 7 a vrcholy 8 až 11 modulární. V pravém horním diagramu hrany mezi těmito množinami znázorňují podíly dané daným rozkladem, zatímco hrany uvnitř množin znázorňují odpovídající faktory.

Oddíly a jsou triviální modulární oddíly . je graf s jedním vrcholem, zatímco . Předpokládejme, že se jedná o netriviální modul. Pak je jednoprvková podmnožina také netriviální modulární oddíl . Existence jakýchkoli netriviálních modulů tedy implikuje existenci netriviálních oddílů modulů. Obecně většina nebo všechny členy mohou být netriviální moduly. ${\displaystyle \{V\))$ $\{\{x\}|x\in V\}$ $G/\{V\}$ $G/\{\{x\}|x\in V\}=G$ $X$ $X$ $V\obrácené lomítko X$ $PROTI$ $P$

If je netriviální modulární oddíl, pak je kompaktní reprezentace všech hran, které končí různými třídami oddílů . Pro každou třídu oddílu podgrafu generovanou pomocí se nazývá faktor a poskytuje reprezentaci všech hran s oběma konci v . Okraje grafu lze tedy rekonstruovat, pokud jsou známy podílový graf a jeho faktory. Termín jednoduchý graf pochází ze skutečnosti, že jednoduchý graf má pouze triviální kvocienty a faktory. $P$ $G/P$ $P$ $X$ $P$ $G[X]$ $X$ $X$ $G$ $G/P$

Pokud je násobitel modulo kvocientu , může se ukázat, že lze faktorizovat rekurzivně a podíly. Každá úroveň rekurze dává kvocient. Jako základní případ má graf jeden vrchol. Graf lze rekonstruovat rekonstrukcí faktorů zdola, obrácením kroků rozdělení sestavením faktorů s kvocienty na každé úrovni. $G[X]$ $G/P$ $G[X]$ $G$

Na obrázku níže je taková rekurzivní dekompozice znázorněna jako strom, který odráží jeden ze způsobů, jak rekurzivně faktorizovat počáteční modulární dekompoziční faktory na menší modulární oddíly.

Metoda rekurzivního rozdělení grafu na faktory a kvocienty nemusí být jediná. (Například všechny podmnožiny vrcholů úplného grafu jsou moduly, což znamená, že existuje mnoho různých způsobů, jak tento graf rekurzivně rozložit.) Některé způsoby rozkladu mohou být užitečnější než jiné.

Modularizace

Naštěstí existuje rekurzivní rozklad grafu, který implicitně reprezentuje všechny způsoby, jakými jej lze rozložit. To je modularizace. Je to samo o sobě způsob rekurzivního rozkladu grafu na kvocienty, ale zahrnuje všechny ostatní. Rozklad znázorněný na obrázku níže je speciálním rozkladem daného grafu.

Níže je hlavní pozorování pro pochopení modulárního rozkladu:

Jestliže je modul grafu a je podmnožinou $X$ $G$ $Y$ $X$ , pak je modul právě tehdy, když je modulem . $Y$ $G$ $G[X]$

Gallai [4] definoval modulární rozklad rekurzivně na grafu s mnoha vrcholy takto: $PROTI$

V základním případě, pokud má pouze jeden vrchol, je jeho modulární rozklad strom s jedním uzlem. $G$
Gallai ukázal, že pokud je připojen a jeho doplněk také, pak maximální moduly, které jsou vlastními podmnožinami , jsou rozdělením . Jsou tedy modulární. Kvocienty, které definují, jsou jednoduché. Kořen stromu je označen jako jednoduchý uzel a tyto moduly jsou akceptovány potomky sady . Protože jsou maximální, jakýkoli modul, který není reprezentován tímto způsobem, je obsažen v potomku . Pro každého potomka množiny nahrazení modularizačního stromu modulárním dekompozičním stromem poskytuje reprezentaci všech modulů grafu podle klíčového pozorování výše. $G$ $PROTI$ $PROTI$ $PROTI$ $X$ $PROTI$ $X$ $PROTI$ $X$ $G[X]$ $G$
Pokud není připojen, je připojen jeho doplněk. Jakékoli spojení připojených komponent je modul grafu . Všechny ostatní moduly jsou podmnožinami samostatné součásti konektivity. To představuje všechny moduly kromě podmnožin komponent pro připojení. Pro každou komponentu nahrazení modulárním dekompozičním stromem poskytuje reprezentaci všech modulů grafu podle klíčového pozorování výše. Kořen stromu je označen jako paralelní uzel, ale je potomkem kořene. Kvocient definovaný potomkem je doplňkem celého grafu. $G$ $G$ $X$ $X$ $G[X]$ $G$ $X$
Pokud doplněk grafu není souvislý, je graf souvislý. Podstromy, které jsou potomky, jsou definovány symetricky k případu, kdy graf není spojen, protože moduly grafu jsou stejné jako moduly jeho doplňku. Kořen stromu je označen jako sekvenční uzel a kvocient definovaný potomky je úplný graf. $G$ $G$ $PROTI$ $G$

Konečný strom má jedinou sadu vrcholů grafu jako listy, které jsou základním případem. Sada vrcholů grafu je modulem právě tehdy, když se jedná o uzel stromu nebo spojení potomků sériového nebo paralelního uzlu. To implicitně přiřadí všechna modulární rozšíření k horní části . V tomto smyslu modulární dekompoziční strom „soustředí v sobě“ všechny ostatní způsoby rekurzivního rozkladu grafu na dílčí. $G$ $Y$ $G$ $PROTI$ $G$

Algoritmické problémy

Datová struktura pro reprezentaci modulárního dekompozičního stromu musí podporovat operace, které berou uzel jako vstup a vracejí sadu vrcholů grafu , které uzel reprezentuje. Zřejmý způsob, jak toho dosáhnout, je přiřadit každému uzlu seznam vrcholů v grafu , které uzel reprezentuje. Vzhledem k ukazateli na uzel lze množinu vrcholů grafu , které uzel reprezentuje, získat v čase . Taková struktura však bude v nejhorším případě vyžadovat paměť . $G$ $k$ $G$ $G$ ${\mathcal {O}}(k)$ $\Theta (n^{2})$

Paměťová alternativa je získána reprezentací modulárního dekompozičního stromu libovolnou standardní datovou strukturou založenou na stromech a označením každého listu vrcholem grafu , který reprezentuje. Množina reprezentovaná vnitřním uzlem je definována množinou návěští jeho podřízených listů. Je dobře známo, že každý zakořeněný strom s listy má nanejvýš vnitřní uzly. Můžete použít hloubkové vyhledávání počínaje od , abyste získali popisky potomků listů v čase . ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$ $G$ $proti$ $k$ $k-1$ $proti$ $proti$ ${\mathcal {O}}(k)$

Každý uzel je množinou vrcholů v grafu , a pokud se jedná o vnitřní uzel, množinou potomků je split , kde každá rozdělená třída je modul. Proto generují kvocient v . Vrcholy tohoto kvocientu jsou prvky , takže je lze reprezentovat vytvořením hran mezi potomky . Jestliže a jsou dva členy a , , pak a jsou sousední v tehdy a pouze tehdy, když a jsou v kvocientu sousedící. Pro libovolnou dvojici vrcholů grafu je to určeno soukromými potomky největšího společného předka a ve stromu modulárního rozkladu. Modulární rozklad označený tímto způsobem jako kvocient poskytuje kompletní reprezentaci grafu . $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$ $proti$ $G$ $Y$ $Z$ $\{u,v\}$ $G$ $\{u\}$ ${\displaystyle \{v\))$ $G$

Mnoho kombinatorických problémů lze vyřešit na grafu tak, že je vyřešíme samostatně pro každý kvocient. Například je graf srovnatelnosti právě tehdy, když každý z těchto kvocientů je grafem srovnatelnosti [4] [5] . Abychom tedy určili, zda je graf grafem srovnatelnosti, stačí to zkontrolovat pro každý z jeho kvocientů. Ve skutečnosti k nalezení tranzitivní orientace grafu srovnatelnosti stačí najít tranzitivní orientaci každého z jeho kvocientů v modulárním rozkladu [4] [5] . Podobný jev se vyskytuje u permutačních grafů [6] , intervalových grafů [7] , dokonalých grafů a dalších tříd grafů. Některé důležité kombinatorické optimalizační problémy na grafech lze vyřešit pomocí podobných strategií [8] . $G$ $G$

Cographs jsou grafy, které mají ve svém modulárním dekompozičním stromu pouze paralelní nebo sekvenční uzly.

První polynomiální časový algoritmus pro výpočet modulárního dekompozičního stromu grafu byl publikován v roce 1972 [9] a nyní jsou k dispozici algoritmy lineárního času [6] [10] .

Zobecnění

Modulární rozklad orientovaných grafů lze získat v lineárním čase [11] .

Až na několik jednoduchých výjimek má každý graf s netriviálním modulárním rozkladem také šikmou část [12] .

Poznámky

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

Literatura

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. Rozklad grafů pro neorientované grafy // Proc. 3. Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Florida, 1972). — Florida Atlantic University , 1972.
Martin C. Golumbic. Algoritmická teorie grafů a dokonalé grafy. - Academic Press, 1980. - ISBN 0-444-51530-5 .
Hsu WL, Ma T. Rychlé a jednoduché algoritmy pro rozpoznávání grafů akordické srovnatelnosti a intervalových grafů // SIAM Journal on Computing. - 1999. - T. 28 , no. 3 . - doi : 10.1137/S0097539792224814 .
Ross M. McConnell, Fabien de Montgolfier. Modulární rozklad orientovaných grafů v lineárním čase // Diskrétní aplikovaná matematika. - 2005. - T. 145 , no. 2 . - doi : 10.1016/j.dam.2004.02.017 .
Ross M. McConnell, Jeremy P. Spinrad. Modulární rozklad a tranzitivní orientace // Diskrétní matematika . - 1999. - T. 201 . - doi : 10.1016/S0012-365X(98)00319-7 .
Rolf H. Möhring. Algoritmické aspekty grafů srovnatelnosti a intervalových grafů // Grafy a pořadí. — D. Reidel, 1985a.
Rolf H. Möhring. Algoritmické aspekty substituční dekompozice při optimalizaci přes vztahy, množinové systémy a booleovské funkce // Annals of Operations Research. — 1985b. - T. 4 . - doi : 10.1007/BF02022041 .
Charis Papadopoulos, Constantinos Voglis. Kreslení grafů pomocí modulárního rozkladu // Proc. 13. mezinárodní sympozium o grafové kresbě (GD'05) . - Springer-Verlag, 2005. - T. 3843. - (Poznámky z přednášek z informatiky). - doi : 10.1007/11618058_31 .
Bruce Reed. Zkosit oddíly v dokonalých grafech // Diskrétní aplikovaná matematika. - 2008. - T. 156 , č.p. 7 . - S. 1150-1156 . - doi : 10.1016/j.dam.2007.05.054 . Archivováno z originálu 19. září 2015.
Jeremy P Spinrad. Efektivní grafová znázornění. - American Mathematical Society, 2003. - (Monografie Fields Institute). — ISBN 0-8218-2815-0 .
Marc Tedder, Derek Corneil, Michel Habib, Christophe Paul. Jednodušší lineární modulární rozklad prostřednictvím rekurzivních faktorizačních permutací // Proc. 35. mezinárodní kolokvium o automatech, jazycích a programování (ICALP 2008) . - Springer-Verlag, 2008. - T. 5125. - (Poznámky z přednášek z informatiky). - doi : 10.1007/978-3-540-70575-8_52 .
Emad Zahedi, Jason Smith. Modulární dekompozice grafů a vlastnost zachovávající vzdálenost // Diskrétní aplikovaná matematika. - 2018. - Vydání. 7 .

Odkazy

Perl Implementace modulárního dekompozičního algoritmu
Implementace modulárního dekompozičního algoritmu v Javě
Implementace modulárního dekompozičního algoritmu v Julii