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ů .
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 .
Ekvivalentně je modul, pokud mají všechny členy stejnou sadu sousedů mezi vrcholy, které nejsou v .
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í.
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.
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:
, 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 .
je silný grafový modul , pokud (částečně) nepřekrývá žádný jiný grafový modul — grafový modul je buď , nebo , nebo .
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.
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 .
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.
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.
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.
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é.
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 , pak je modul právě tehdy, když je modulem .
Gallai [4] definoval modulární rozklad rekurzivně na grafu s mnoha vrcholy takto:
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čí.
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ěť .
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 .
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 .
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] .
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] .
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] .