Pochyl partycję

Podział skośny wykresu akordowego . Po lewej stronie przegrody górna i dolna część są odłączone od siebie. Po prawej stronie podziału istnieją wszystkie możliwe krawędzie od góry do dołu, tworząc graf, którego dopełnienie jest rozłączne.

W teorii grafów podział skośny grafu to podział jego wierzchołków na dwa podzbiory, w taki sposób, że podgraf indukowany utworzony przez jeden z dwóch podzbiorów jest rozłączony , a podgraf indukowany utworzony przez drugi podzbiór jest dopełnieniem grafu rozłączonego . Podziały skośne odgrywają ważną rolę w teorii grafów doskonałych .

Definicja

Skośny podział wykresu to podział jego wierzchołków na dwa podzbiory $X] } jest odłączony$ Y $\ Displaystyle$$Y$$}$ , dla których indukowany podgraf $,$ a indukowany podgraf jest wykresu (współodłączonego Równoważnie skośny podział wykresu ${\ displaystyle G}$ można opisać przez podział wierzchołków na cztery podzbiory , $displaystyle B}$${$$\$ , $do {\ displaystyle$ i re $\ displaystyle D}$ , tak że sol {\ displaystyle nie ma krawędzi od do ${\ Displaystyle$$B} i takie$ że wszystkie możliwe krawędzie od do ${\ displaystyle C}$ re $\ displaystyle D}$ istnieć; dla takiego podziału indukowane podgrafy $D]}$$do ∪ re ]$ i wspólnie , więc możemy wziąć ${\ Displaystyle X = A \ kubek B}$${\ Displaystyle Y = C \ kubek D}$ Y .

Przykłady

Każdy wykres ścieżki z czterema lub więcej wierzchołkami ma podział skośny, w którym wspólnie rozłączony zbiór jest $jedną$ z wewnętrznych krawędzi ścieżki, a rozłączony zbiór składa się z wierzchołków na $X}$ po obu stronach tej krawędzi. Jednak nie jest możliwe, aby wykres cyklu o dowolnej długości miał podział skośny: bez względu na to, które podzbiory cyklu są wybrane jako zbiór $displaystyle$ zbiór komplementarny $Y}$$połączonych$$.$ komponentów, więc nie jest możliwe rozłączenie i wspólne rozłączenie

Jeśli graf ma podział skośny, to samo dotyczy jego dopełnienia . Na przykład uzupełnienia wykresów ścieżek mają podziały skośne, a uzupełnienia wykresów cykli nie.

Przypadki specjalne

Jeśli sam graf jest rozłączony, to z tylko trzema prostymi wyjątkami ( graf pusty , graf z jedną krawędzią i trzema wierzchołkami lub idealne dopasowanie czterech wierzchołków ) ma on podział skośny, w którym współodłączona strona podział składa się z punktów końcowych pojedynczej krawędzi, a odłączona strona składa się ze wszystkich pozostałych wierzchołków. Z tego samego powodu, jeśli dopełnienie grafu jest odłączone, to z odpowiednim zestawem trzech wyjątków musi mieć podział skośny.

Jeśli graf ma separator kliki (klikę, której usunięcie spowodowałoby rozłączenie pozostałych wierzchołków) z więcej niż jednym wierzchołkiem, to podział na klikę i pozostałe wierzchołki tworzy podział skośny. Zestaw fragmentów kliki z jednym wierzchołkiem jest punktem artykulacji ; jeśli taki wierzchołek istnieje, to z niewielką liczbą prostych wyjątków istnieje podział skośny, w którym współodłączona strona składa się z tego wierzchołka i jednego z jego sąsiadów.

Gwiazda wycinana na grafie to separator wierzchołków $,$ w którym jeden z wierzchołków separatora sąsiaduje ze wszystkimi pozostałymi Każdy separator kliki to zestaw gwiazd. Z konieczności graf z przekrojem gwiazdowym (z więcej niż jednym wierzchołkiem) ma podział skośny, w którym podgraf współrozłączony składa się z wierzchołków w zbiorze przekrojowym gwiazdy, a podgraf rozłączony składa się ze wszystkich pozostałych wierzchołków.

Moduł (lub zbiór jednorodny) jest nietrywialnym podzbiorem wierzchołków wierzchołków ${$ , że dla każdego wierzchołka $\ displaystyle H}$ który nie jest w $H}$ , $H. {$ \ albo $displaystyle$ ze wszystkimi wierzchołkami w $H}$ , albo z żadnym z nich. Jeśli wykres ma moduł $displaystyle$$H}$ a poza nim istnieją oba wierzchołki sąsiadujące ze wszystkimi wierzchołkami w $i$ wierzchołki nie sąsiadujące z żadnym z nich, to $jego$ zbiór gwiazd składający się z jednego wierzchołka w module wraz z sąsiedzi poza modułem. Z drugiej strony, jeśli istnieje moduł, w którym jeden z tych dwóch podzbiorów jest pusty, to graf jest rozłączony lub współrozłączony i ponownie (z trzema prostymi wyjątkami) ma zbiór skośny.

Historia

Podziały skośne zostały wprowadzone przez Chvátala (1985) w związku z doskonałymi grafami . Chvátal udowodnił, że minimalnie niedoskonały graf nie może mieć zbioru gwiazd. Mówiąc trywialnie, grafy rozłączne nie mogą być minimalnie niedoskonałe, a wiadomo było również, że grafy z separatorami klik lub modułami nie mogą być minimalnie niedoskonałe. Klaudiusz Berge we wczesnych latach sześćdziesiątych XX wieku przypuszczał, że grafy doskonałe są takie same jak grafy Berge'a, grafy bez indukowanego cyklu nieparzystego (o długości co najmniej pięciu) ani jego dopełnienia, oraz (ponieważ cykle i ich dopełnienia nie mają podziałów skośnych) nie ma minimalnego nie Graf -Berge może mieć partycję skośną. Zmotywowany tymi wynikami, Chvátal przypuszczał, że żaden minimalnie niedoskonały graf nie może mieć podziału skośnego. Kilku autorów udowodniło szczególne przypadki tej hipotezy, ale przez wiele lat pozostawała ona nierozwiązana.

Podziały skośne zyskały na znaczeniu, gdy zostały użyte przez Chudnovsky'ego i in. (2006) , aby udowodnić silne twierdzenie o doskonałym grafie , że wykresy Berge'a są rzeczywiście takie same jak doskonałe wykresy. Chudnowski i in. nie byli w stanie bezpośrednio udowodnić hipotezy Chvátala, ale zamiast tego udowodnili słabszy wynik, że minimalny kontrprzykład dla twierdzenia (jeśli istniał) nie może mieć zrównoważonego podziału skośnego, podziału skośnego, w którym każda indukowana ścieżka z punktami końcowymi po jednej stronie partycji i wierzchołkami wewnętrznymi po drugiej stronie ma parzystą długość. Wynik ten stanowił kluczowy lemat w ich dowodzie, a pełna wersja lematu Chvátala wynika z ich twierdzenia.

W teorii grafów strukturalnych

Podziały skośne stanowią jeden z kluczowych elementów dekompozycji strukturalnej doskonałych grafów używanych przez Chudnovsky'ego i in. (2006) jako część ich dowodu twierdzenia o silnym doskonałym grafie. Chudnowski i in. pokazał, że każdy graf doskonały albo należy do jednej z pięciu podstawowych klas grafów doskonałych, albo ma jeden z czterech typów rozkładu na prostsze grafy, z których jednym jest podział skośny.

Prostszy przykład rozkładu strukturalnego przy użyciu przegród skośnych podaje Seymour (2006) . Zauważa, że ​​każdy wykres porównywalności jest kompletny , dwudzielny lub ma podział skośny. Bo jeśli każdy element częściowo uporządkowanego zestawu jest elementem minimalnym lub maksymalnym, to odpowiedni wykres porównywalności jest dwudzielny. Jeśli zamówienie jest zamówieniem całkowitym , to odpowiedni wykres porównywalności jest kompletny. Jeśli żaden z tych dwóch przypadków nie zachodzi, ale każdy element, który nie jest ani minimalny, ani maksymalny, jest porównywalny ze wszystkimi innymi elementami, to albo podział na elementy minimalne i nieminimalne (jeśli jest więcej niż jeden element minimalny) albo podział na elementy elementy maksymalne i niemaksymalne (jeśli występuje więcej niż jeden element maksymalny) tworzą zbiór gwiazd. A w pozostałym przypadku istnieje element ${\ displaystyle x}$ częściowego porządku, który nie jest minimalny, nie maksymalny i nieporównywalny ze wszystkimi innymi elementami; w $i$$współodłączona$ strona składa się z elementów porównywalnych z samymi odłączonymi strona składa się z pozostałych elementów.

Grafy akordowe mają jeszcze prostszą dekompozycję podobnego typu: albo są kompletne, albo mają separator klik. Hayward (1985) wykazał analogicznie, że każdy spójny i współspójny słabo akordowy graf (graf bez cyklu indukowanego lub jego dopełnienia o długości większej niż cztery) z czterema lub większą liczbą wierzchołków ma przekrój gwiazdy lub jego dopełnienie, z którego wynika z lematu Chvátala, że ​​każdy taki graf jest doskonały.

Algorytmy i złożoność

Podział skośny danego grafu, jeśli istnieje, można znaleźć w czasie wielomianowym . Zostało to pierwotnie wykazane przez de Figueiredo i in. (2000) $, ale z niepraktycznie dużym$ działania gdzie $wierzchołków$ wejściowym. Kennedy & Reed (2008) poprawili czas działania do ${\ Displaystyle O (n ^ {4} m)}$ ; tutaj ${\ displaystyle m}$ to liczba krawędzi wejściowych.

Sprawdzanie, czy graf zawiera podział skośny, w którym jedna z części współrozłączonej strony jest niezależna, jest NP-zupełne . Testowanie, czy dany wykres zawiera zrównoważoną partycję skośną, jest również NP-zupełne w dowolnych grafach, ale może być rozwiązane w czasie wielomianowym na grafach doskonałych.

Notatki

• Czudnowski, Maria ; Robertson, Neil ; Seymour, Paweł ; Thomas, Robin (2006), „Twierdzenie o silnym grafie doskonałym” , Annals of Mathematics , 164 (1): 51–229, arXiv : math / 0212070 , doi : 10.4007/annals.2006.164.51 .
•   Chvátal, V. (1985), „Star-cutsets and perfect graphs”, Journal of Combinatorial Theory , Seria B, 39 (3): 189–199, doi : 10.1016/0095-8956 (85) 90049-8 , MR 0815391 .
•   Cornuéjols, G .; Reed, B. (1993), „Kompletne wieloczęściowe przekroje w minimalnych niedoskonałych grafach”, Journal of Combinatorial Theory , Seria B, 59 (2): 191–198, doi : 10.1006/jctb.1993.1065 , MR 1244930 .
•   Dantas, Simone; de Figueiredo, Celina MH; Klein, Sulamita; Gravier, Sylvain; Reed, Bruce A. (2004), „Problem stabilnej partycji skośnej”, Discrete Applied Mathematics , 143 (1–3): 17–22, doi : 10.1016/j.dam.2004.01.001 , MR 2087864 .
•   de Figueiredo, Celina MH; Klein, Sulamita; Kohayakawa, Yoshiharu ; Reed, Bruce A. (2000), „Efektywne znajdowanie przegród skośnych”, Journal of Algorithms , 37 (2): 505–521, doi : 10.1006/jagm.1999.1122 , MR 1788847 .
•   Hayward, Ryan B. (1985), „Słabo triangulowane wykresy”, Journal of Combinatorial Theory , Seria B, 39 (3): 200–208, doi : 10.1016/0095-8956 (85) 90050-4 , MR 0815392 .
•   Kennedy, William S.; Reed, Bruce (2008), „Rozpoznawanie szybkich skosów”, Computational Geometry and Graph Theory: International Conference, KyotoCGGT 2007, Kioto, Japonia, 11–15 czerwca 2007, Revised Selected Papers, Lecture Notes in Computer Science , tom. 4535, Berlin: Springer, s. 101–107, doi : 10.1007/978-3-540-89550-3_11 , MR 2672388 .
• Lovász, László (1972), „Normal hypergraphs and perfect graph conjecture”, Discrete Mathematics , 2 (3): 253–267, doi : 10.1016/0012-365X (72) 90006-4 .
•   Reed, Bruce (2008), „Podziały skośne w doskonałych grafach” (PDF) , Discrete Applied Mathematics , 156 (7): 1150–1156, doi : 10.1016/j.dam.2007.05.054 , MR 2404228 .
•   Roussel, F.; Rubio, P. (2001), „O podziałach skośnych w minimalnych niedoskonałych grafach”, Journal of Combinatorial Theory , Seria B, 83 (2): 171–190, doi : 10.1006/jctb.2001.2044 , MR 1866394 .
•   Seymour, Paul (2006), „Jak znaleziono dowód hipotezy silnego doskonałego wykresu” (PDF) , Gazette des Mathématiciens (109): 69–83, MR 2245898 .
•   Trotignon, Nicolas (2008), „Dekompozycja wykresów Berge'a i wykrywanie zrównoważonych partycji skośnych” (PDF) , Journal of Combinatorial Theory , Seria B, 98 (1): 173–225, arXiv : 1309,0680 , doi : 10,1016/j.jctb. 2007.07.004 , MR 2368032 .