Cograph - Cograph

v teorie grafů, a cographnebo doplňkově redukovatelný grafnebo P4-bezplatný graf, je graf které lze vygenerovat z grafu s jedním vrcholem K.1 podle doplňování a disjunktní unie. To znamená, že rodina cographs je nejmenší třída grafů, která zahrnuje K.1 a je uzavřen doplňováním a disjunktním sjednocením.
Cographs byly objeveny nezávisle několika autory od 70. let; časné reference zahrnují Jung (1978), Lerchs (1971), Seinsche (1974), a Sumner (1974). Byli také povoláni D * -grafy,[1] dědičné Daceyovy grafy (po související práci Jamese C. Daceyho mladšího dne ortomodulární mřížky ),[2] a 2paritní grafy.[3]Mají jednoduchý strukturální rozklad zahrnující disjunktní unie a doplňkový graf operace, které lze výstižně reprezentovat označeným stromem a které se používají algoritmicky k efektivnímu řešení mnoha problémů, jako je hledání maximální klika které jsou obtížnější pro obecnější třídy grafů.
Zvláštní případy sgrafů zahrnují kompletní grafy, kompletní bipartitní grafy, shlukové grafy, a prahové grafy. Cographs jsou zase speciální případy vzdálenostně dědičné grafy, permutační grafy, srovnatelné grafy, a perfektní grafy.
Definice
Rekurzivní konstrukce
Jakýkoli graf může být sestrojen podle následujících pravidel:
- jakýkoli jednotlivý vrcholný graf je cograph;
- -li je cograph, tak je také doplňkový graf ;
- -li a jsou cographs, tak je jejich disjunktní unie .
Grafy lze definovat jako grafy, které lze pomocí těchto operací vytvořit, počínaje grafy s jedním vrcholem.[4]Alternativně můžete místo operace komplementu použít operaci spojení, která sestává z vytvoření disjunktního spojení a potom přidáním hrany mezi každou dvojicí vrcholu z a vrchol z .
Další charakterizace
Lze uvést několik alternativních charakterizací grafů. Mezi nimi:
- Cograph je graf, který neobsahuje cesta P4 na 4 vrcholech (a tedy o délce 3) jako indukovaný podgraf. To znamená, že graf je cograph právě tehdy, pokud pro jakékoli čtyři vrcholy , pokud a jsou okraje grafu, pak alespoň jeden z nebo je také hrana.[4]
- Cograph je graf, jehož všechny indukované podgrafy mají tu vlastnost, že jakýkoli maximální klika protíná všechny maximální nezávislá množina v jediném vrcholu.
- Cograph je graf, ve kterém má každý netriviální indukovaný podgraf alespoň dva vrcholy se stejnými sousedstvími.
- Cograph je graf, ve kterém má každý připojený indukovaný podgraf odpojený doplněk.
- Cograph je graf, jehož všechny jsou spojeny indukované podgrafy mít průměr maximálně 2.
- Cograph je graf, ve kterém každý připojená součást je vzdálenost-dědičný graf s průměrem nejvýše 2.
- Cograph je graf s šířka kliky maximálně 2.[5]
- Cograph je a srovnávací graf a sériově paralelní dílčí řád.[1]
- Cograph je a permutační graf a oddělitelná permutace.[6]
- Cograph je graf, jehož všechny jsou minimální akordické dokončení jsou triviálně dokonalé grafy.[7]
- Cograph je a dědičně dobře vybarvený graf, graf takový, že každý chamtivé zbarvení každého indukovaného podgrafu používá optimální počet barev.[8]
- Graf je grafem právě tehdy, je-li každý vrchol grafu a dokonalý pořádek, protože mít ne P4 znamená, že v jakémkoli vrcholném pořadí nebude existovat žádná překážka dokonalému řádu.
Cotrees

A cotree je strom, ve kterém jsou vnitřní uzly označeny čísly 0 a 1. Každý cotree T definuje cograph G s listy T jako vrcholy a ve kterých podstrom zakořenil v každém uzlu T odpovídá indukovaný podgraf v G definovaná sadou listů sestupujících z tohoto uzlu:
- Podstrom skládající se z jednoho listového uzlu odpovídá indukovanému podgrafu s jediným vrcholem.
- Podstrom zakořeněný v uzlu označeném 0 odpovídá sjednocení podgrafů definovaných dětmi tohoto uzlu.
- Podstrom zakořeněný v uzlu označeném 1 odpovídá připojit se podgrafů definovaných dětmi tohoto uzlu; to znamená, že vytvoříme unii a přidáme hranu mezi každé dva vrcholy odpovídající listím v různých podstromech. Alternativně lze spojení sady grafů zobrazit jako vytvořené doplněním každého grafu, vytvořením spojení doplňků a následným doplněním výsledného spojení.
Ekvivalentní způsob popisu grafu vytvořeného z kotré je, že dva vrcholy jsou spojeny hranou právě tehdy, když nejnižší společný předek odpovídajících listů je označeno 1. Naopak každý graf může být tímto způsobem znázorněn kotré. Pokud požadujeme, aby se popisky na kterékoli kořenové cestě tohoto stromu střídaly mezi 0 a 1, je toto znázornění jedinečné.[4]
Výpočtové vlastnosti
Cographs mohou být rozpoznány v lineárním čase, a reprezentace coree vytvořena pomocí modulární rozklad,[9] upřesnění oddílu,[10] LexBFS ,[11] nebo dělený rozklad.[12] Po sestavení reprezentace cotree lze vyřešit mnoho známých problémů s grafy pomocí jednoduchých výpočtů zdola nahoru na cotree.
Například najít maximální klika v grafu vypočítat v pořadí zdola nahoru maximální kliku v každém podgrafu představovanou podstromem kotré. Pro uzel označený 0 je maximální klika maximum mezi kliky vypočítanými pro podřízené uzly. Pro uzel označený 1 je maximální klika sjednocení kliky vypočítané pro podřízené uzly a má velikost rovnou součtu velikostí kliky dětí. Takže střídavým maximalizováním a sčítáním hodnot uložených v každém uzlu kotree můžeme vypočítat maximální velikost kliky a střídavým maximalizováním a převzetím unií můžeme sestavit samotnou maximální kliku. Podobné výpočty stromu zdola nahoru umožňují maximální nezávislá sada, vrchol zbarvení číslo, maximální krytí kliky a Hamiltonicity (to je existence a Hamiltonovský cyklus ), které se mají vypočítat v lineárním čase z kotreeho zobrazení grafu.[4] Protože cographs mají ohraničenou šířku kliky, Courcelleova věta lze použít k testování jakékoli vlastnosti v monadickém druhém řádu logika grafů (MSO1) na grafech v lineárním čase.[13]
Problém testování, zda daný graf je k vrcholy pryč a / nebo t Okraje od cograph je fixovatelný parametr.[14] Rozhodování, zda může být graf k-edge-deleted to a cograph can be resolve in O.*(2.415k) čas,[15] a k-edge-edited to a cograph in O*(4.612k).[16] Pokud lze největší odstraněný podgraf grafu najít odstraněním k vrcholy z grafu, lze je najít v O*(3.30k) čas.[15]
Dva grafy jsou izomorfní právě tehdy, jsou-li jejich kotle (v kanonické formě bez dvou sousedních vrcholů se stejným štítkem) izomorfní. Kvůli této ekvivalenci lze v lineárním čase určit, zda jsou dva grafy izomorfní, a to tak, že zkonstruujeme jejich kotlety a použijeme test lineárního izomorfismu pro značené stromy.[4]
Li H je indukovaný podgraf cograph G, pak H je sám cograph; pohovka pro H mohou být vytvořeny odstraněním některých listů z kotle pro G a poté potlačit uzly, které mají pouze jedno dítě. Vyplývá to z Kruskalova věta o stromu že vztah být indukovaným podgrafem je a dobře kvazi-objednávání na grafech.[17] Pokud tedy podrodina cographů (např rovinný cographs) je uzavřen za indukovaných operací podgrafu, poté má konečný počet zakázané indukované podgrafy. Výpočtově to znamená, že testování členství v takové podrodině lze provádět v lineárním čase pomocí výpočtu zdola nahoru na souřadnici daného grafu k otestování, zda obsahuje některý z těchto zakázaných podgrafů. Pokud jsou však velikosti dvou grafů různé, testování, zda je jeden z nich indukovaným podgrafem druhého, je NP-kompletní.[18]
Cographs hrají klíčovou roli v algoritmech pro rozpoznávání funkce jen pro čtení.[19]
Výčet
Počet připojených grafů s n vrcholy, pro n = 1, 2, 3, ..., je:
Pro n > 1 existuje stejný počet odpojených grafů, protože u každého grafu přesně jeden z nich doplňkový graf je připojen.
Související rodiny grafů
Podtřídy
Každý kompletní graf K.n je cograph, s cotree skládající se z jednoho 1-uzlu a n listy. Podobně každý kompletní bipartitní graf K.A,b je zloděj. Jeho cotree je zakořeněný v 1-uzlu, který má dvě děti s 0 uzly, jedno s A listové děti a jeden s b listové děti Turánův graf mohou být vytvořeny spojením rodiny stejně velkých nezávislých sad; jedná se tedy také o graf, s kotré zakořeněným v 1-uzlu, který má pro každou nezávislou množinu podřízený 0-uzel.
Každý prahový graf je také cograph. Prahový graf lze vytvořit opakovaným přidáváním jednoho vrcholu, připojeného buď ke všem předchozím vrcholům, nebo k žádnému z nich; každá taková operace je jednou z disjunktních spojovacích nebo spojovacích operací, pomocí kterých může být vytvořena kotle.[20]
Supertřídy
Charakterizace grafů vlastností, kterou každá klika a maximální nezávislá množina mají neprázdnou křižovatku, je silnější verzí definující vlastnosti silně dokonalé grafy, ve kterém každý indukovaný podgraf obsahuje nezávislou množinu, která protíná všechny maximální kliky. V grafu protíná každá maximální nezávislá množina všechny maximální kliky. Každý cograph je tedy silně dokonalý.[21]
Skutečnost, že cographs jsou P4- zdarma znamená, že jsou dokonale objednat. Ve skutečnosti je každý vrcholový řád cografu dokonalým řádem, což dále znamená, že maximální nalezení kliky a minimální zbarvení lze najít v lineárním čase s jakýmkoli chamtivým zbarvením a bez nutnosti rozkladu kotle.
Každý cograph je vzdálenost-dědičný graf, což znamená, že každý indukovaná cesta v cograph je a nejkratší cesta. Tyto cographs lze charakterizovat mezi vzdálenost-dědičné grafy jako mající průměr dva v každé připojené složce. Každý cograph je také srovnávací graf a sériově paralelní dílčí řád, získané nahrazením disjunktního spojení a operací spojení, pomocí kterých byl cograph sestaven disjunktním spojením a pořadový součet operace s částečnými objednávkami. Protože silně dokonalé grafy, dokonale uspořádatelné grafy, grafy dědičnosti vzdálenosti a grafy srovnatelnosti jsou vše perfektní grafy, cographs jsou také perfektní.[20]
Poznámky
- ^ A b Jung (1978).
- ^ Sumner (1974).
- ^ Burlet & Uhry (1984).
- ^ A b C d E Corneil, Lerchs & Stewart Burlingham (1981).
- ^ Courcelle & Olariu (2000).
- ^ Bose, Buss & Lubiw (1998).
- ^ Parra & Scheffler (1997).
- ^ Christen & Selkow (1979).
- ^ Corneil, Perl a Stewart (1985).
- ^ Habib & Paul (2005).
- ^ Bretscher a kol. (2008).
- ^ Gioan & Paul (2012).
- ^ Courcelle, Makowsky & Rotics (2000).
- ^ Cai (1996).
- ^ A b Nastos & Gao (2010).
- ^ Liu a kol. (2012).
- ^ Damaschke (1990).
- ^ Damaschke (1991).
- ^ Golumbic & Gurvich (2011).
- ^ A b Brandstädt, Le & Spinrad (1999).
- ^ Berge a Duchet (1984).
Reference
- Berge, C.; Duchet, P. (1984), "Silně dokonalé grafy", Témata o dokonalých grafechMatematická studia v Severním Holandsku, 88, Amsterdam: Severní Holandsko, str. 57–61, doi:10.1016 / S0304-0208 (08) 72922-0, PAN 0778749.
- Bose, Prosenjit; Buss, Jonathan; Lubiw, Anna (1998), "Porovnávání vzorů pro permutace", Dopisy o zpracování informací, 65 (5): 277–283, doi:10.1016 / S0020-0190 (97) 00209-3, PAN 1620935.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999), Třídy grafů: PrůzkumMonografie SIAM o diskrétní matematice a aplikacích, ISBN 978-0-89871-432-6.
- Burlet, M .; Uhry, J. P. (1984), „Parity Graphs“, Témata o dokonalých grafech, Annals of Discrete Mathematics, 21, str. 253–277.
- Bretscher, A .; Corneil, D. G.; Habib, M .; Paul, C. (2008), „Simple Linear Time LexBFS Cograph Recognition Algorithm“, SIAM Journal on Discrete Mathematics, 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016, doi:10.1137/060664690.
- Cai, L. (1996), „Opravitelnost parametrů s problémy s modifikací grafů pro dědičné vlastnosti“, Dopisy o zpracování informací, 58 (4): 171–176, doi:10.1016/0020-0190(96)00050-6.
- Christen, Claude A .; Selkow, Stanley M. (1979), „Některé dokonalé barevné vlastnosti grafů“, Journal of Combinatorial Theory, Řada B, 27 (1): 49–59, doi:10.1016/0095-8956(79)90067-4, PAN 0539075.
- Corneil, D. G.; Lerchs, H .; Stewart Burlingham, L. (1981), "Doplňte redukovatelné grafy", Diskrétní aplikovaná matematika, 3 (3): 163–174, doi:10.1016 / 0166-218X (81) 90013-5, PAN 0619603.
- Corneil, D. G.; Perl, Y .; Stewart, L. K. (1985), „Algoritmus lineárního rozpoznávání grafů“, SIAM Journal on Computing, 14 (4): 926–934, doi:10.1137/0214065, PAN 0807891.
- Courcelle, B .; Makowsky, J. A .; Rotics, U. (2000), „Problémy s optimalizací lineárního času na grafech ohraničené šířky kliky“, Teorie výpočetních systémů, 33 (2): 125–150, doi:10,1007 / s002249910009, PAN 1739644, S2CID 15402031, Zbl 1009.68102.
- Courcelle, B.; Olariu, S. (2000), "Horní hranice k šířce kliky grafů", Diskrétní aplikovaná matematika, 101 (1–3): 77–144, doi:10.1016 / S0166-218X (99) 00184-5, PAN 1743732.
- Damaschke, Peter (1990), „Indukované podgrafy a dobře kvazi-objednávání“, Journal of Graph Theory, 14 (4): 427–435, doi:10,1002 / jgt.3190140406, PAN 1067237.
- Damaschke, Peter (1991), „Induced subraph isomorphism for cographs is NP-complete“, v Möhring, Rolf H. (ed.), Graficko-teoretické koncepty v informatice: 16. mezinárodní workshop WG '90 Berlín, Německo, 20. – 22. Června 1990, sborník, Přednášky v informatice, 484, Springer-Verlag, str. 72–78, doi:10.1007/3-540-53832-1_32.
- Gioan, Emeric; Paul, Christophe (2012), „Split decomposition and graph-labeled trees :harakterizace a plně dynamické algoritmy pro zcela rozložitelné grafy“, Diskrétní aplikovaná matematika, 160 (6): 708–733, arXiv:0810.1823, doi:10.1016 / j.dam.2011.05.007, PAN 2901084, S2CID 6528410.
- Golumbic, Martin C.; Gurvich, Vladimir (2011), "Funkce jednorázového čtení" (PDF)v Crama, Yves; Hammer, Peter L. (eds.), Booleovské funkceEncyklopedie matematiky a její aplikace, 142, Cambridge University Press, Cambridge, str. 519–560, doi:10.1017 / CBO9780511852008, ISBN 978-0-521-84751-3, PAN 2742439.
- Habib, Michel; Paul, Christophe (2005), „Jednoduchý lineární časový algoritmus pro rozpoznání cographů“ (PDF), Diskrétní aplikovaná matematika, 145 (2): 183–197, doi:10.1016 / j.dam.2004.01.011, PAN 2113140.
- Jung, H. A. (1978), „O třídě posetů a odpovídajících grafech srovnatelnosti“, Journal of Combinatorial Theory, Řada B, 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, PAN 0491356.
- Lerchs, H. (1971), Na kliky a jádra, Tech. Report, Dept. of Comp. Sci., Univ. z Toronta.
- Liu, Yunlong Liu; Wang, Jianxin; Guo, Jiong; Chen, Jianer (2012), „Složitost a parametrizované algoritmy pro editaci Cograph“, Teoretická informatika, 461: 45–54, doi:10.1016 / j.tcs.2011.11.040.
- Nastos, James; Gao, Yong (2010), „Nová strategie větvení problémů s parametrizovanými grafy“, Přednášky z informatiky, 6509: 332–346, arXiv:1006.3020, Bibcode:2010LNCS.6509..332N, doi:10.1007/978-3-642-17461-2_27, ISBN 978-3-642-17460-5.
- Parra, Andreas; Scheffler, Petra (1997), „Charakterizace a algoritmické aplikace vložení chordálního grafu“, 4. díl Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1995), Diskrétní aplikovaná matematika, 79 (1–3): 171–188, doi:10.1016 / S0166-218X (97) 00041-3, PAN 1478250.
- Seinsche, D. (1974), "O majetku třídy n-barevné grafy ", Journal of Combinatorial Theory, Řada B, 16 (2): 191–193, doi:10.1016 / 0095-8956 (74) 90063-X, PAN 0337679.
- Sumner, D. P. (1974), „Dacey graphs“, Journal of the Australian Mathematical Society, 18 (4): 492–502, doi:10.1017 / S1446788700029232, PAN 0382082.