Modulární rozklad - Modular decomposition

V teorii grafů je modulární rozklad rozklad grafu na podmnožiny vrcholů nazývané moduly. Modul je zobecněním připojené komponenty grafu. Na rozdíl od připojených komponent však může být jeden modul správnou podmnožinou jiného. Moduly proto vedou k rekurzivnímu (hierarchickému) rozkladu grafu namísto pouhého oddílu.

Existují varianty modulárního rozkladu pro neorientované grafy a směrované grafy . Pro každý neorientovaný graf je tento rozklad jedinečný.

Tento pojem lze zobecnit na jiné struktury (například směrované grafy) a je užitečný při navrhování efektivních algoritmů pro rozpoznávání některých tříd grafů, pro hledání tranzitivní orientace grafů srovnatelnosti , pro optimalizační problémy grafů a pro kreslení grafů .

Moduly

Jelikož byl pojem modulů v mnoha oblastech znovu objeven, byly moduly také nazývány autonomní sady , homogenní sady , intervaly a partitivní sady . Snad nejstarší zmínka o nich a první popis modulárních kvocientů a rozkladu grafu, který z nich vznikl, se objevil v ( Gallai 1967).

Modul grafu je zobecnění připojeného zařízení . Připojená komponenta má tu vlastnost, že je množinou vrcholů, takže každý člen je nesousedí každého vrcholu, ve kterém není . (Jedná se o spojení připojených komponent právě tehdy, má-li tuto vlastnost.) Obecněji je modulem, pokud pro každý vrchol buďto každý člen je nesousedí nebo každý člen je sousedem . ${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle X}$${\ Displaystyle v \ not \ v X}$${\ displaystyle X}$${\ displaystyle v}$${\ displaystyle X}$${\ displaystyle v}$

Ekvivalentně je modul, pokud mají všichni členové stejné množiny sousedů mezi vrcholy, které nejsou v . ${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle X}$

Na rozdíl od připojených komponent jsou moduly grafu stejné jako moduly jeho doplňku a moduly mohou být „vnořeny“: jeden modul může být správnou podmnožinou jiného. Všimněte si, že množina vrcholů grafu je modul, stejně jako jeho jednoprvkové podmnožiny a prázdná množina; nazývají se triviální moduly . Graf může, ale nemusí mít další moduly. Graf se nazývá primární, pokud jsou všechny jeho moduly triviální. ${\ displaystyle V}$

Navzdory těmto rozdílům si moduly zachovávají požadovanou vlastnost připojených komponent, která spočívá v tom, že mnoho vlastností subgrafu indukovaných připojenou komponentou je nezávislých na zbytku grafu. Podobný jev platí také pro podgrafy indukované moduly. ${\ Displaystyle G [X]}$ ${\ displaystyle X}$

Moduly grafu mají proto velký algoritmický význam. Sada vnořených modulů, jejichž příkladem je modulární dekompozice, může být použita k vedení rekurzivního řešení mnoha kombinatorických problémů na grafech, jako je rozpoznávání a tranzitivně orientovaná srovnatelnost grafů , rozpoznávání a nalézání permutačních reprezentací permutačních grafů , rozpoznávání, zda graf je cograf a nalezení certifikátu odpovědi na otázku, rozpoznávání intervalových grafů a hledání intervalových reprezentací pro ně, definování grafů dědičnosti vzdálenosti (Spinrad, 2003) a pro kreslení grafů (Papadopoulos, 2006). Hrají důležitou roli v Lovaszově oslavovaném důkazu věty o dokonalém grafu (Golumbic, 1980).

Pro rozpoznávání grafů dědičných na vzdálenost a kruhových grafů je zvláště užitečná další generalizace modulárního rozkladu, nazývaná rozdělený rozklad (Spinrad, 2003).

Abychom se vyhnuli možnosti nejednoznačnosti ve výše uvedených definicích, uvádíme následující formální definice modulů. . je modul of jestliže: ${\ displaystyle G = (V, E)}$${\ displaystyle M \ subseteq V}$${\ displaystyle G}$

• vrcholy nelze rozlišit žádným vrcholem v , tj . buď sousedí s oběma a nebo ani sousedí s ani s .${\ displaystyle M}$${\ displaystyle V \ zpětné lomítko M}$${\ Displaystyle \ forall u, v \ in M, \ forall x \ in V \ zpětné lomítko M}$${\ displaystyle x}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle x}$${\ displaystyle u}$${\ displaystyle v}$
• vrcholy mají stejnou sadu vnějších sousedů, tj .${\ displaystyle M}$${\ Displaystyle \ forall u, v \ in M, N (u) \ setminus M = N (v) \ setminus M}$

${\ displaystyle \ emptyset}$, a všechny singletony pro jsou moduly a nazývají se triviální moduly . Graf je primární, pokud jsou všechny jeho moduly triviální. Připojené komponenty grafu nebo jeho doplňkového grafu jsou také moduly . ${\ displaystyle V}$ ${\ displaystyle \ {v \}}$${\ displaystyle v \ v V}$${\ displaystyle G}$${\ displaystyle G}$

${\ displaystyle M}$je silný modul grafu, pokud nepřekrývá žádný jiný modul z : modulu , buď nebo nebo . ${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle \ forall M '}$${\ displaystyle G}$${\ Displaystyle M \ cap M '= \ emptyset}$${\ displaystyle M \ subseteq M '}$${\ Displaystyle M '\ subseteq M}$

Modulární kvocienty a faktory

Pokud a jsou disjunktní moduly, pak je snadné vidět, že buď každý člen je sousedem každého prvku , nebo žádný člen není sousedící s žádným členem . Vztah mezi dvěma nesouvislými moduly je tedy přilehlý nebo nesousedící . Mezi těmito dvěma extrémy nemůže existovat žádný mezilehlý vztah. ${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle X}$${\ displaystyle Y}$

Z tohoto důvodu je modulární příčky z , kde každá třída oddíl je modul jsou obzvláště zajímavé. Předpokládejme, že jde o modulární oddíl. Protože třídy oddílů jsou disjunktní, jejich sousedství tvoří nový graf, kvocientový graf , jehož vrcholy jsou členy . To znamená, že každý vrchol je modulem G a přilehlosti těchto modulů jsou okraje . ${\ displaystyle V}$${\ displaystyle P}$ ${\ displaystyle G/P}$${\ displaystyle P}$${\ displaystyle G/P}$${\ displaystyle 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í přepážkou. V pravém horním diagramu hrany mezi těmito sadami zobrazují kvocient daný tímto oddílem, zatímco hrany uvnitř sad zobrazují odpovídající faktory.

Oddíly a jsou triviální modulární oddíly . je pouze graf s jedním vrcholem, zatímco . Předpokládejme, že je netriviální modul. Potom a jednoprvkové podmnožiny jsou netriviální modulární oddíl . Existence jakýchkoli netriviálních modulů tedy znamená existenci netriviálních modulárních oddílů. Obecně mnoho nebo všichni členové skupiny mohou být netriviální moduly. ${\ displaystyle \ {V \}}$${\ displaystyle \ {\ {x \} | x \ v V \}}$${\ displaystyle G/\ {V \}}$${\ Displaystyle G/\ {\ {x \} | x \ v V \} = G}$${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle V \ zpětné lomítko X}$${\ displaystyle V}$${\ displaystyle P}$

Pokud je netriviální modulární oddíl, pak je kompaktní reprezentací všech hran, které mají koncové body v různých třídách oddílů . Pro každou třídu oddílů v se podgraf vyvolaný pomocí nazývá faktor a poskytuje reprezentaci všech hran s oběma koncovými body v . Okraje lze proto rekonstruovat pouze s ohledem na kvocientový graf a jeho faktory. Termín primární graf pochází ze skutečnosti, že primární graf má pouze triviální kvocienty a faktory. ${\ displaystyle P}$${\ displaystyle G/P}$${\ displaystyle P}$${\ displaystyle X}$${\ displaystyle P}$${\ Displaystyle G [X]}$${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle G}$${\ displaystyle G/P}$

Když je faktorem modulárního kvocientu , je možné, že jej lze rekurzivně rozložit na faktory a kvocienty. Každá úroveň rekurze vede ke vzniku kvocientu. Jako základní případ má graf pouze jeden vrchol. Kolektivně lze rekonstruovat induktivně rekonstrukcí faktorů zdola nahoru, převracením kroků rozkladu kombinací faktorů s kvocientem na každé úrovni. ${\ Displaystyle G [X]}$${\ displaystyle G/P}$${\ Displaystyle G [X]}$${\ displaystyle G}$

Na obrázku níže je takový rekurzivní rozklad reprezentován stromem, který zobrazuje jeden způsob rekurzivně se rozkládajících faktorů počátečního modulárního oddílu na menší modulární oddíly.

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

Modulární rozklad

Naštěstí existuje takový rekurzivní rozklad grafu, který implicitně představuje všechny způsoby jeho rozkladu; toto je modulární rozklad. Sám je to způsob rekurzivního rozložení grafu na kvocienty, ale zahrnuje všechny ostatní. Rozklad zobrazený na obrázku níže je tento speciální rozklad pro daný graf.

Graf, jeho kvocient, kde „pytle“ vrcholů grafu odpovídají dětem kořene modulárního rozkladného stromu, a jeho úplný modulární rozkladný strom: uzly řady jsou označeny „s“, paralelní uzly „//“ a primární uzly "p".

Následuje porozumění modulárnímu rozkladu:

If is a module is and is a subset of${\ displaystyle X}$${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle X}$ , then is a module of , if and only if it is a module of . ${\ displaystyle Y}$${\ displaystyle G}$${\ Displaystyle G [X]}$

V (Gallai, 1967) definoval Gallai rekurzivně modulární rozklad na grafu s množinou vrcholů , a to následovně: ${\ displaystyle V}$

1. Jako základní případ, pokud má pouze jeden vrchol, je jeho modulární dekompozice jediným uzlem stromu.${\ displaystyle G}$
2. Gallai ukázal, že pokud je připojen, a tak je jeho doplněk, pak maximální moduly, které jsou vlastními podmnožinami, jsou jeho oddíly . Jsou tedy modulární přepážkou. Kvocient, který definují, je primární. Kořen stromu je označen jako hlavní uzel a tyto moduly jsou přiřazeny jako podřízené položky . Protože jsou maximální, každý modul, který dosud není reprezentován, je obsažen v podřízeném souboru . Na každé dítě z , nahrazující s modulární rozkladu stromu dává zastoupení všech modulů , podle klíčového pozorování výše.${\ displaystyle G}$${\ displaystyle V}$${\ displaystyle V}$${\ displaystyle V}$${\ displaystyle X}$${\ displaystyle V}$${\ displaystyle X}$${\ displaystyle V}$${\ displaystyle X}$${\ Displaystyle G [X]}$${\ displaystyle G}$
3. Pokud je odpojen, je připojen jeho doplněk. Každé spojení připojených komponent je modulem . Všechny ostatní moduly jsou podmnožinami jedné připojené komponenty. To představuje všechny moduly, s výjimkou podmnožin připojených komponent. Pro každou komponentu nahrazení modulárním stromem rozkladu poskytuje reprezentaci všech modulů klíčovým pozorováním výše. Kořen stromu je označen jako paralelní uzel a je připojen na místo jako podřízený kořen. Podíl definovaný dětmi je doplňkem kompletního grafu.${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle X}$${\ displaystyle X}$${\ Displaystyle G [X]}$${\ displaystyle G}$${\ displaystyle X}$
4. Pokud je komplement z odpojen, je připojen. Podstromy, které jsou podřízenými, jsou definovány způsobem, který je symetrický s případem, kdy je odpojen, protože moduly grafu jsou stejné jako moduly jeho doplňku. Kořen stromu je označen jako sériový uzel a kvocient definovaný dětmi je úplný graf.${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle V}$${\ displaystyle G}$

Výsledný strom má jako základní sadu jednoprvkové sady vrcholů , a to díky základnímu případu. Sada vrcholů je modulem právě tehdy, je -li to uzel stromu nebo spojení podřízených řadového nebo paralelního uzlu. To implicitně dává všechny modulární oddíly . V tomto smyslu modulární strom rozkladu „zahrnuje“ všechny ostatní způsoby rekurzivního rozkladu na kvocienty. ${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle G}$${\ displaystyle V}$${\ displaystyle G}$

Algoritmické problémy

Datová struktura pro reprezentaci modulárního dekompozičního stromu by měla podporovat operaci, která vstupuje do uzlu a vrací množinu vrcholů, které daný uzel představuje. Zřejmým způsobem, jak toho dosáhnout, je přiřadit každému uzlu seznam vrcholů , které představuje. Vzhledem k ukazateli na uzel by tato struktura mohla v čase vrátit množinu vrcholů , které představuje . Tato datová struktura by však v nejhorším případě vyžadovala místo. ${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle {\ mathcal {O}} (k)}$${\ displaystyle \ Theta (n^{2})}$

Znázornění modulárního rozkladu${\ displaystyle {\ mathcal {O}} (n)}$

Kosmická alternativou, která odpovídá tomuto výkonu se dosáhne tím, že reprezentuje modulární stromu rozkladu za použití jakékoli standardní datovou strukturu kořeny strom a označení každý list s vrcholem , který představuje. Sada reprezentovaná vnitřním uzlem je dána sadou popisků jejích listových potomků. Je dobře známo, že jakýkoli kořenový strom s listy má nejvíce vnitřních uzlů. Lze použít hloubkové vyhledávání začínající na hlášení etiket potomků listí v čase. ${\ 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)}$

Modulární dekompozice, rozšířená o kvocient na potomcích každého vnitřního uzlu, poskytuje úplnou reprezentaci .${\ displaystyle G}$

Každý uzel je sada vrcholů, a pokud je interní uzel, sada podřízených je oddíl, kde každá třída oddílu je modul. Indukují tedy kvocient v . Vrcholy tohoto kvocientu jsou prvky , takže jej lze reprezentovat instalací hran mezi podřízené objekty . If a are two members of and and , then and are mentioned in if and only if and are relationships in this quotient. Pro jakýkoli pár vrcholů je to určeno kvocientem u dětí s nejméně společným předkem a v modulárním rozkladném stromu. Modulární rozklad, takto označený kvocienty, proto poskytuje úplnou reprezentaci . ${\ 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 \ v Y}$${\ displaystyle v \ v Z}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle Z}$${\ displaystyle \ {u, v \}}$${\ displaystyle G}$${\ displaystyle \ {u \}}$${\ displaystyle \ {v \}}$${\ displaystyle G}$

Mnoho kombinatorických problémů lze vyřešit vyřešením problému samostatně na každém z těchto kvocientů. Například je graf srovnatelnosti právě tehdy, pokud je každý z těchto kvocientů grafem srovnatelnosti (Gallai, 67; Möhring, 85). Abychom zjistili, zda je graf srovnatelným grafem, stačí zjistit, zda je každý z kvocientů. Ve skutečnosti k nalezení tranzitivní orientace grafu srovnatelnosti stačí tranzitivně orientovat každý z těchto podílů jeho modulárního rozkladu (Gallai, 67; Möhring, 85). Podobný jev platí pro permutační grafy (McConnell a Spinrad '94), intervalové grafy (Hsu a Ma '99), dokonalé grafy a další třídy grafů. Některé důležité problémy kombinatorické optimalizace na grafech lze vyřešit pomocí podobné strategie (Möhring, 85). ${\ displaystyle G}$${\ displaystyle G}$

Cografy jsou grafy, které mají ve svém modulárním rozkladném stromu pouze paralelní nebo sériové uzly.

První polynomiální algoritmus pro výpočet modulárního rozkladného stromu grafu byl publikován v roce 1972 (James, Stanton & Cowan 1972) a nyní jsou k dispozici lineární algoritmy (McConnell & Spinrad 1999, Tedder et al. 2007, Cournier & Habib 1994).

Zobecnění

Modulární rozklad směrovaných grafů lze provádět v lineárním čase ( McConnell & de Montgolfier 2005 ).

S malým počtem jednoduchých výjimek má každý graf s netriviálním modulárním rozkladem také šikmou oblast ( Reed 2008 ).

Reference

• 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). „Rozklad grafu pro neorientované grafy“. Proč. 3. Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972) . Floridská atlantická univerzita . s. 281–290. MR  0351909 .
• Golumbic, Martin C. (1980). Algoritmická teorie grafů a dokonalé grafy . Akademický tisk. ISBN 0-444-51530-5.
• Hsu, WL; Ma, T. (1999). „Rychlé a jednoduché algoritmy pro rozpoznávání grafů akordické srovnatelnosti a intervalových grafů“. SIAM Journal o Computing . 28 (3): 1004–1020. CiteSeerX  10.1.1.104.4647 . doi : 10,1137/S0097539792224814 .
• McConnell, Ross M .; de Montgolfier, Fabien (2005). „Lineární časový modulární rozklad směrovaných grafů“ . Diskrétní aplikovaná matematika . 145 (2): 198–209. doi : 10.1016/j.dam.2004.02.017 .
• McConnell, Ross M .; Spinrad, Jeremy P. (1999). „Modulární rozklad a tranzitivní orientace“ (PDF) . Diskrétní matematika . 201 (1–3): 189–241. doi : 10,1016/S0012-365X (98) 00319-7 . MR  1687819 .
• Möhring, Rolf H. (1985). I. Rival (ed.). „Algoritmické aspekty grafů srovnatelnosti a intervalových grafů“. Grafy a pořadí . D. Reidel: 41–101. doi : 10,1007/978-94-009-5315-4_2 . ISBN 978-94-010-8848-0.
• Möhring, Rolf H. (1985). „Algoritmické aspekty substitučního dekompozice při optimalizaci vztahů, množinových systémů a booleovských funkcí“. Annals of Operations Research . 4 : 195–225. doi : 10,1007/BF02022041 . S2CID  119982014 .
• Papadopoulos, Charis; Voglis, Constantinos (2005). „Kreslení grafů pomocí modulárního rozkladu“ (PDF) . Proč. 13. mezinárodní sympozium o kreslení grafů (GD'05) . Přednášky z informatiky. 3843 . Springer-Verlag. s. 343–354. doi : 10.1007/11618058_31 . MR  2229205 .
• Reed, Bruce (2008). „Zkosit oddíly v dokonalých grafech“ (PDF) . Diskrétní aplikovaná matematika . 156 (7): 1150–1156. doi : 10.1016/j.dam.2007.05.054 . MR  2404228 . Archivováno z originálu (PDF) dne 2015-09-19 . Citováno 2012-08-13 .
• Spinrad, Jeremy P. (2003). Efektivní grafická znázornění . Monografie Fields Institute. Americká matematická společnost. ISBN 0-8218-2815-0.
• Tedder, Marc; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008). „Jednodušší lineární časový modulární rozklad prostřednictvím rekurzivních faktorizačních permutací“. Proč. 35. mezinárodní kolokvium o automatech, jazycích a programování (ICALP 2008) . Přednášky z informatiky. 5125 . Springer-Verlag. s. 634–645. arXiv : 0710.3901 . doi : 10,1007/978-3-540-70575-8_52 .
• Zahedi, Emad; Smith, Jason (31. července 2019). „Modulární rozklad grafů a vlastnost zachovávající vzdálenost“ . Diskrétní aplikovaná matematika . 265 (7): 192–198. arXiv : 1805.09853 . Bibcode : 2018arXiv180509853Z . doi : 10.1016/j.dam.2019.03.019 .

externí odkazy

• Perl realizace modulárního algoritmu rozkladu
• Implementace modulárního dekompozičního algoritmu v Javě
• Implementace Julia modulárního dekompozičního algoritmu