Split (teoria grafów)

Wykres z dwoma nietrywialnymi silnymi podziałami (na górze) i jego rozszczepioną dekompozycją (na dole). Trzy wykresy ilorazowe to gwiazda (po lewej), wykres główny (w środku) i pełny wykres (po prawej).

Ten artykuł dotyczy cięć, które tworzą kompletne grafy dwudzielne. Aby zapoznać się z wykresami, które można podzielić na klikę i niezależny zestaw, zobacz wykres podzielony .

W teorii grafów podział grafu nieskierowanego to przekrój , którego zbiór przekrojów tworzy pełny graf dwudzielny . Graf jest liczbą pierwszą , jeśli nie ma podziałów. Podziały grafu można zebrać w strukturę przypominającą drzewo, zwaną dekompozycją podziału lub dekompozycją łączenia , którą można skonstruować w czasie liniowym. Dekompozycja ta została wykorzystana do szybkiego rozpoznawania wykresów kołowych i grafów dziedzicznych od odległości , jak również dla innych problemów w algorytmach grafowych.

Podziały i dekompozycje zostały po raz pierwszy wprowadzone przez Cunninghama (1982) , który również badał warianty tych samych pojęć dla grafów skierowanych .

Definicje

Cięcie grafu nieskierowanego to podział wierzchołków na dwa niepuste podzbiory, boki przekroju . Podzbiór krawędzi, które mają jeden punkt końcowy z każdej strony, nazywany jest zbiorem przekrojów. Gdy zbiór przekrojów tworzy kompletny graf dwudzielny , jego przekrój nazywamy podziałem. Zatem podział można opisać jako podział wierzchołków grafu na dwa podzbiory X i Y , tak że każdy sąsiad X w Y sąsiaduje z każdym sąsiadem Y w X .

Cięcie lub dzielenie jest trywialne, gdy jeden z jego dwóch boków ma tylko jeden wierzchołek; każde trywialne cięcie jest podziałem. Mówimy, że graf jest pierwszy (w odniesieniu do podziałów), jeśli nie ma nietrywialnych podziałów.

Mówi się, że dwa podziały przecinają się, jeśli każda strona jednego podziału ma niepuste przecięcie z każdym bokiem drugiego podziału. Rozłam nazywamy silnym, gdy nie przecina go żaden inny rozłam. W szczególnym przypadku każdy trywialny podział jest silny. Silne podziały grafu powodują powstanie struktury zwanej dekompozycją split lub dekompozycją łączenia grafu. Ten rozkład można przedstawić za pomocą drzewa którego liście odpowiadają danemu grafowi jeden do jednego i którego krawędzie odpowiadają silnym podziałom grafu, tak że podział liści utworzony przez usunięcie dowolnej krawędzi z drzewa jest taki sam jak podział wierzchołków podanych przez powiązany silny podział.

Każdy wewnętrzny węzeł i podzielonego drzewa dekompozycji grafu G jest powiązany z grafem Gi _, zwanym wykresem ilorazowym dla węzła i . Wykres ilorazowy można utworzyć, usuwając i z drzewa, tworząc podzbiory wierzchołków w G odpowiadające liściom w każdym z wynikowych poddrzew i zwijając każdy z tych zestawów wierzchołków w jeden wierzchołek. Każdy wykres ilorazowy ma jedną z trzech postaci: może to być wykres główny, wykres pełny lub gwiazda .

Wykres może mieć wykładniczo wiele różnych podziałów, ale wszystkie są reprezentowane w drzewie dekompozycji podziału, albo jako krawędź drzewa (w przypadku silnego podziału), albo jako dowolny podział pełnego wykresu lub wykresu ilorazu gwiazd (w przypadku podziału, który nie jest silny).

Przykłady

W pełnym grafie lub pełnym grafie dwudzielnym każde cięcie jest podziałem.

W grafie cyklu o długości cztery, podział wierzchołków określony przez 2-kolorowanie cyklu jest nietrywialnym podziałem, ale dla cykli o dowolnej dłuższej długości nie ma nietrywialnych podziałów.

Mostek grafu, który nie jest połączony dwoma krawędziami, odpowiada podziałowi, w którym każda strona podziału jest utworzona przez wierzchołki po jednej stronie mostka . Zestaw przekrojów podziału to tylko pojedyncza krawędź mostka, co jest szczególnym przypadkiem kompletnego podgrafu dwudzielnego. Podobnie, jeśli v jest punktem artykulacji grafu, który nie jest połączony z 2 wierzchołkami , to graf ma wiele podziałów, w których v a niektóre, ale nie wszystkie, składniki utworzone przez jego usunięcie znajdują się po jednej stronie, a pozostałe składniki znajdują się po drugiej stronie. W tych przykładach zestaw cięć podziału tworzy gwiazdę .

Algorytmy

Cunningham (1982) wykazał, że możliwe jest znalezienie rozkładu rozdzielonego w czasie wielomianowym . Po kolejnych udoskonaleniach algorytmu, czasu liniowego odkryli Dahlhaus (2000) oraz Charbit, de Montgolfier i Raffinot (2012) .

Aplikacje

Dekompozycja dzielona została zastosowana do rozpoznania kilku ważnych klas grafów:

• Graf dziedziczny odległości to graf, którego rozkład rozdzielony nie zawiera ilorazów pierwszych. Na podstawie tej charakterystyki możliwe jest wykorzystanie rozkładu rozdzielonego do rozpoznawania grafów dziedzicznych od odległości w czasie liniowym.
• Wykresy parzystości można rozpoznać w czasie liniowym jako wykresy, w których każdy podzielony iloraz jest albo pełny, albo dwudzielny .
• Wykres kołowy to wykres przecięcia rodziny akordów koła. Dany wykres jest wykresem kołowym wtedy i tylko wtedy, gdy każdy z ilorazów jego podzielonego rozkładu jest wykresem kołowym, więc sprawdzenie, czy wykres jest wykresem kołowym, można sprowadzić do tego samego problemu na wykresach pierwszego ilorazu wykresu. Co więcej, gdy graf kołowy jest liczbą pierwszą, struktura kombinatoryczna zbioru reprezentujących go akordów jest jednoznacznie określona, ​​co upraszcza zadanie rozpoznania tej struktury. Na podstawie tych pomysłów możliwe jest rozpoznawanie wykresów kołowych w czasie wielomianowym.

Rozkład dzielony został również wykorzystany do uproszczenia rozwiązania niektórych problemów, które są NP-trudne na dowolnych grafach:

• Jak zauważył już Cunningham (1982) , maksymalny niezależny zbiór dowolnego grafu można znaleźć za pomocą algorytmu programowania dynamicznego, przechodząc od dołu do góry jego podzielone drzewo dekompozycji. W każdym węźle wybieramy niezależny zbiór o maksymalnej wadze na jego wykresie ilorazowym, ważony rozmiarami niezależnych zestawów już obliczonych w węzłach potomnych.
• Chociaż inny algorytm podany przez Cunninghama (1982) jest wadliwy, podobne przechodzenie od dołu do góry może być użyte do obliczenia maksymalnej kliki wykresu poprzez połączenie obliczeń ważonych maksymalnych klik na jego wykresach ilorazowych.
• Rao (2008) przedstawia również algorytmy dla połączonych zbiorów dominujących , kompletnych zbiorów dominujących i kolorowania grafów .

Metody te mogą prowadzić do algorytmów czasu wielomianowego dla grafów, w których każdy wykres ilorazowy ma prostą strukturę, która umożliwia wydajne obliczenie jego podproblemu. Dotyczy to na przykład wykresów, w których każdy wykres ilorazowy ma stały rozmiar.