Š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ů .
Š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 .
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ý.
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.
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] .
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] .
Š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] .
Š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ů.
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ý.
Š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.
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] .