Šikmá přepážka

Šikmé rozdělení grafu je rozdělení jeho vrcholů do dvou podmnožin ve formě odpojeného generovaného podgrafu a doplňku ; hraje důležitou roli v dokonalé teorii grafů .

Definice

Šikmé rozdělení grafu je rozdělení vrcholů grafu na dvě podmnožiny a , pro které je vygenerovaný podgraf odpojen a vygenerovaný podgraf je doplňkem nespojeného grafu (dále jen „souvislý“). . Ekvivalentně šikmé rozdělení grafu lze popsat jako rozdělení vrcholů grafu do čtyř podmnožin , , a , ve kterých nejsou žádné hrany od do , ale existují všechny možné hrany od do . Pro takový oddíl jsou vygenerované podgrafy jak odpojené, tak spolupropojené, takže můžeme vzít a . $G$ $X$ $Y$ $G[X]$ $G[Y]$ $G$ $G$ $A$ $B$ $C$ $D$ $A$ $B$ $C$ $D$ $G[A\cup B]$ $G[C\cup D]$ $X=A\cup B$ $Y=C\cup D$

Příklady

Jakákoli cesta se čtyřmi nebo více vrcholy má zkosený oddíl, ve kterém je společně odpojená množina jednou z vnitřních hran cesty a odpojená množina se skládá z obou vrcholů této hrany. Není však možné, aby cykly jakékoli délky měly šikmý oddíl - bez ohledu na to, jaké podmnožiny cyklů jsou vybrány jako množina , doplněk množiny bude mít stejný počet připojených komponent, takže je nemožné rozložit a být spoluodpojený. $Y$ $X$ $X$ $Y$ $X$ $Y$

Pokud má graf šikmý oddíl, má takový oddíl a jeho doplněk . Například doplňky cesty mají zkosené oddíly, ale doplňky cyklů nikoli.

Zvláštní příležitosti

Pokud je graf rozpojen, pak má kromě tří jednoduchých případů (prázdný graf, graf s jednou hranou a třemi vrcholy nebo dokonalé párování na čtyřech vrcholech) šikmou přepážku, ve které je spoluodpojená strana oddíl se skládá z koncových bodů jedné hrany a odpojená strana se skládá ze všech ostatních vrcholů. Ze stejného důvodu, je-li doplněk grafu rozpojený, pak kromě odpovídající množiny tří případů musí mít zkosený oddíl [1] .

Pokud má graf oddělovač kliky (klika, jejíž odstranění způsobí odpojení zbývajících vrcholů) s více než jedním vrcholem, rozdělení na kliku a zbývající vrcholy vytvoří šikmý oddíl. Úsek kliky s jedním vrcholem je závěs . Pokud takový vrchol existuje, pak, až na několik jednoduchých výjimek, existuje šikmý oddíl, ve kterém se společně odpojená strana skládá z tohoto vrcholu a jednoho z jeho sousedů [1] .

Hvězdicový úsek v grafu je oddělovač vrcholů , ve kterém jeden z vrcholů sousedí se všemi ostatními vrcholy oddělovače. Jakýkoli oddělovač kliknutí je oddíl s hvězdičkou. Graf s hvězdnou sekcí (s více než jedním vrcholem) má nezbytně šikmou část, ve které se společně nespojený podgraf skládá z vrcholů hvězdné sekce a odpojený podgraf se skládá ze všech zbývajících vrcholů [1] . $G$

Modul (nebo homogenní množina) je netriviální podmnožina vrcholů grafu , takže pro jakýkoli vrchol , který nepatří do , buď sousedí se všemi vrcholy v , nebo žádný z nich. Pokud má graf modul a mimo něj jsou vrcholy sousedící se všemi vrcholy a ostatní vrcholy mimo něj nesousedí s žádným vrcholem z , pak má hvězdicový úsek skládající se z jednoho vrcholu v modulu spolu s jeho sousedy mimo modul. Na druhou stranu, pokud existuje modul, ve kterém je jedna z těchto dvou podmnožin prázdná, pak je graf rozpojený nebo spolurozpojený a opět (kromě tří jednoduchých případů) má zešikmený řez [1] . $H$ $G$ $proti$ $H$ $proti$ $H$ $G$ $H$ $H$ $H$ $G$

Historie

Šikmé oddíly zavedl Khvatal [2] v souvislosti s dokonalými grafy . Chvátal dokázal, že minimálně nedokonalý graf nemůže mít hvězdicový řez. Je jasné, že odpojené grafy nemohou být minimálně nedokonalé a také bylo známo, že grafy s klikovými oddělovači nebo moduly nemohou být minimálně nedokonalé [3] . Claudy Berge na počátku 60. let předpokládal, že dokonalé grafy musí být stejné jako Bergeovy grafy, grafy bez generovaného lichého cyklu (o délce pět nebo více) nebo jeho doplňku a (protože cykly a jejich doplňky nemají šikmé oddíly) žádný graf. to není minimální Bergeův graf může mít zešikmený oddíl. Chvátal se zájmem o tyto výsledky předpokládal, že žádný minimálně nedokonalý graf nemůže mít zkosený oddíl. Někteří autoři prokázali zvláštní případy této domněnky, která však zůstala dlouho nevyřešena [4] .

Šikmé oddíly získaly zvláštní důležitost, když je použili Chudnovskaya, Robertson, Seymour a Thomas [5] k prokázání silné věty o dokonalém grafu , že Bergeovy grafy jsou stejné jako dokonalé grafy. Chudnovskaya a její skupina nebyly schopny přímo dokázat Khvatalovu domněnku, ale prokázaly slabší výsledek, že minimální protipříklad k větě (pokud by existoval) by musel mít vyvážený šikmý oddíl, ve kterém by každá vygenerovaná cesta s koncem na jedné straně přepážky a vnitřních vrcholů na druhé straně má sudou délku. Tento výsledek se stal klíčovým lemmatem v jejich důkazu a plná verze Chvatalova lemmatu vyplývá z jejich věty [6] .

V teorii strukturních grafů

Šikmé oddíly tvoří klíčovou součást strukturálního rozkladu dokonalých grafů, který byl použit Chudnovskou, Robertsonem, Seymourem a Thomasem [5] jako součást důkazu silné věty o dokonalém grafu. Chudnovskaya et al ukázali, že jakýkoli dokonalý graf patří buď do pěti základních tříd dokonalých grafů, nebo má jeden ze čtyř typů rozkladu na jednodušší grafy, přičemž jedním z těchto rozkladů je rozklad zešikmený.

Jednoduchý příklad strukturálního rozkladu pomocí šikmých přepážek uvedl Seymour [6] . Všiml si, že jakýkoli graf srovnatelnosti je úplný nebo bipartitní nebo má zkosený oddíl. Pokud je jakýkoli prvek částečně uspořádané množiny buď minimálním prvkem , nebo maximálním prvkem, pak je odpovídající graf srovnatelnosti bipartitní. Pokud je objednávka dokončena , pak je odpovídající graf srovnatelnosti kompletní. Pokud nenastane žádný z těchto případů, ale jakýkoli prvek, který není ani minimální, ani maximální, je srovnatelný se všemi ostatními prvky, pak buď rozdělení na minimální a neminimální prvky (pokud existuje více než jeden minimální prvek), nebo rozdělení na maximální a nemaximální prvky (pokud je více než jeden maximální prvek) tvoří hvězdnou sekci. Ve zbývajícím případě se jedná o prvek dílčího řádu, který není ani minimální, ani maximální a není srovnatelný se všemi ostatními prvky. V tomto případě se jedná o šikmou přepážku (doplněk hvězdicové sekce), ve které se společně odpojená strana skládá z prvků srovnatelných s (bez sebe sama ), a odpojená strana se skládá ze zbývajících prvků. $X$ $X$ $X$

Chordální grafy mají ještě jednodušší rozklady podobného druhu — jsou buď úplné, nebo mají klikový oddělovač. Hayward [7] podobně ukázal, že každý souvislý a souvislý slabý tětivový graf (graf s vygenerovaným cyklem délky větší než čtyři nebo jeho doplněk) se čtyřmi a více vrcholy má hvězdicový řez nebo jeho doplněk, odkud podle Chvatalova lemmatu , z toho vyplývá, že každý takový graf je dokonalý.

Algoritmy a složitost

Šikmé rozdělení daného grafu, pokud existuje, lze nalézt v polynomiálním čase . To původně ukázali Figueiredo, Klein, Kohayakawa a Reid [8] , ale s velmi dlouhou dobou běhu , kde je počet vrcholů ve vstupním grafu. Kennedy a Reid [9] zlepšili provozní dobu na . Zde je počet hran. $O(n^{101})$ $n$ $O(n^{4}m)$ $m$

Problém kontroly, zda graf obsahuje šikmý oddíl, ve kterém je jedna z částí spoluodpojené strany nezávislá, je NP-úplný problém [10] . Kontrola, zda daný graf obsahuje vyvážený skew oddíl, je také NP-úplná pro libovolné grafy, ale problém lze vyřešit v polynomiálním čase pro dokonalé grafy [11] .

Poznámky

↑ 1 2 3 4 Reed, 2008 .
↑ Chvátal, 1985 .
↑ Reed (2008 ). Neexistenci modulů v minimálních nedokonalých grafech použil Lovas Lovász (1972 ) ve svém důkazu slabé věty o dokonalém grafu .
↑ Viz Cornuéjols, Reed (1993 ) pro případ, kdy se odpojená strana přepážky skládá z několika částí, a Roussel, Rubio (2001 ) pro případ, kdy jedna ze dvou částí společně odpojené strany je nezávislý.
↑ 1 2 Chudnovsky, Robertson, Seymour, Thomas, 2006 .
↑ 12 Seymour , 2006 .
↑ Hayward, 1985 .
↑ de Figueiredo, Klein, Kohayakawa, Reed, 2000 .
↑ Kennedy, Reed, 2008 .
↑ Dantas, de Figueiredo, Klein, Gravier, Reed, 2004 .
↑ Trotignon, 2008 .

Literatura

Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Věta o silném dokonalém grafu // Annals of Mathematics . - 2006. - T. 164 , č. 1 . — S. 51–229 . doi : 10.4007 / anals.2006.164.51 . - arXiv : math/0212070 .
Chvátal V. Hvězdné množiny a dokonalé grafy // Journal of Combinatorial Theory . - 1985. - T. 39 , no. 3 . — S. 189–199 . - doi : 10.1016/0095-8956(85)90049-8 .
Gerard Cornuejols, Bruce Reed. Kompletní vícedílné řezy v minimálních nedokonalých grafech // Journal of Combinatorial Theory . - 1993. - T. 59 , no. 2 . — S. 191–198 . - doi : 10.1006/jctb.1993.1065 .
Simone Dantas, Celina MH de Figueiredo, Sulamita Klein, Sylvain Gravier, Bruce Reed. Problém stabilního zkoseného oddílu // Diskrétní aplikovaná matematika. - 2004. - T. 143 , č. 1-3 . — S. 17–22 . - doi : 10.1016/j.dam.2004.01.001 .
Celina MH de Figueiredo, Sulamita Klein, Yoshiharu Kohayakawa, Bruce Reed. Efektivní nalezení šikmých oddílů // Journal of Algorithms. - 2000. - T. 37 , no. 2 . — S. 505–521 . - doi : 10.1006/jagm.1999.1122 .
Ryan B. Hayward. Slabě triangulované grafy // Journal of Combinatorial Theory . - 1985. - T. 39 , no. 3 . — S. 200–208 . - doi : 10.1016/0095-8956(85)90050-4 .
William S. Kennedy, Bruce Reed. Rychlé rozpoznávání diskových oddílů // Computational Geometry and Graph Theory: International Conference, KyotoCGGT 2007, Kjóto, Japonsko, 11.–15. června 2007, Revised Selected Papers. - Berlín: Springer, 2008. - T. 4535. - S. 101-107. — ( Poznámky k přednáškám z informatiky ). - doi : 10.1007/978-3-540-89550-3_11 .
László Lovasz . Normální hypergrafy a domněnka dokonalého grafu // Diskrétní matematika . - 1972. - svazek 2 , č. 3 . — S. 253–267 . - doi : 10.1016/0012-365X(72)90006-4 .
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.
Roussel F., Rubio P. O zkosených oddílech v minimálních nedokonalých grafech // Journal of Combinatorial Theory . - 2001. - T. 83 , no. 2 . — S. 171–190 . - doi : 10.1006/jctb.2001.2044 .
Paul Seymour. Jak byl nalezen důkaz silného dohadu o dokonalém grafu // Gazette des Mathématiciens. - 2006. - Vydání. 109 . — s. 69–83 .
Nicholas Trotignon. Rozkládání Bergeových grafů a detekce vyvážených šikmých oddílů // Journal of Combinatorial Theory . - 2008. - T. 98 , č.p. 1 . — S. 173–225 . - doi : 10.1016/j.jctb.2007.07.004 . .