Podziel wykres - Split graph

Wykres podzielony, podzielony na klikę i niezależny zbiór.

W teorii grafów , gałęzi matematyki, graf dzielony to graf, w którym wierzchołki można podzielić na klikę i niezależny zbiór . Dzielone wykresy zostały po raz pierwszy zbadane przez Földesa i Hammera  ( 1977a , 1977b ), a wprowadzone niezależnie przez Tyszkiewicza i Czerniaka ( 1979 ).

Podzielony wykres może mieć więcej niż jeden podział na klikę i niezależny zbiór; na przykład ścieżka a – b – c jest podzielonym grafem, którego wierzchołki można podzielić na trzy różne sposoby:

1. klika { a , b } i zbiór niezależny { c }
2. klika { b , c } i zbiór niezależny { a }
3. klika { b } i zbiór niezależny { a , c }

Grafy podzielone można scharakteryzować w kategoriach ich zabronionych podgrafów indukowanych : graf jest dzielony wtedy i tylko wtedy, gdy żaden podgraf indukowany nie jest cyklem czterech lub pięciu wierzchołków lub parą rozłącznych krawędzi (dopełnieniem 4-cyklu).

Związek z innymi rodzinami grafów

Z definicji podzielone wykresy są wyraźnie zamykane pod dopełnieniem . Inna charakterystyka grafów rozszczepionych dotyczy dopełnienia: są to grafy akordowe, których dopełnienia są również akordowe. Tak jak grafy akordowe są grafami przecięcia poddrzew drzew, grafy podzielone są grafami przecięcia różnych podgwiazd grafów gwiazd . Prawie wszystkie grafy akordowe są grafami podzielonymi; to znaczy, w granicy, gdy n idzie do nieskończoności, ułamek n- wierzchołkowych grafów akordowych, które są podzielone, zbliża się do jednego.

Ponieważ wykresy akordowe są doskonałe , tak samo są z wykresami dzielonymi. Te podwójne wykresy podzielone , rodzina wykresów pochodzących z wykresów rozdzielone przez podwojenie każdy wierzchołek (tak klika przychodzi do wywołania antimatching i niezależny zestaw przychodzi do wywołania dopasowanie), postać w widocznym miejscu jako jeden z pięciu podstawowych klas graf doskonały, z którego wszystkie inne można sformułować w dowodzie Chudnovsky'ego i in. (2006) z Strong graf doskonały twierdzenia .

Jeśli wykres jest zarówno wykresem podzielonym, jak i wykresem przedziałowym , jego uzupełnieniem jest zarówno wykres podzielony, jak i wykres porównywalności i na odwrót. Dzielone grafy porównywalności, a zatem również grafy podzielonego przedziału, można scharakteryzować za pomocą zestawu trzech zakazanych podgrafów indukowanych. Wykresy podzielone są dokładnie wykresami progowymi . Podzielone wykresy permutacji to dokładnie te wykresy przedziałów, które mają uzupełnienia wykresów przedziałów; są to wykresy permutacji permutacji połączonych skośnie . Dzielone wykresy mają kochromatyczną liczbę 2.

Problemy algorytmiczne

Niech G będzie grafem podzielonym, podzielonym na klikę C i niezależny zbiór I . Wtedy każda maksymalna klika w podzielonym grafie jest albo samym C , albo sąsiedztwem wierzchołka w I . W ten sposób łatwo jest zidentyfikować maksymalną klikę i komplementarnie maksymalny zbiór niezależny w podzielonym grafie. Na każdym wykresie dzielonym musi być prawdziwa jedna z trzech następujących możliwości:

1. Istnieje wierzchołek x się , że taka, że C ∪ { x } jest zakończona. W tym przypadku C ∪ { x } jest maksymalną kliką, a I jest zbiorem maksymalnie niezależnym.
2. Istnieje wierzchołek x na C w taki sposób, że ∪ { x } jest niezależna. W tym przypadku I ∪ { x } jest maksymalnym niezależnym zbiorem, a C jest maksymalną kliką.
3. C to maksymalna klika, a I to maksymalny niezależny zbiór. W tym przypadku G ma unikalny podział ( C , I ) na klikę i zbiór niezależny, C jest maksymalną kliką, a I jest maksymalnym niezależnym zbiorem.

Niektóre inne problemy optymalizacyjne, które są NP-zupełne w bardziej ogólnych rodzinach grafów, w tym kolorowanie grafów , są podobnie proste w przypadku podzielonych grafów. Znalezienie cyklu Hamiltona pozostaje NP-zupełne nawet dla grafów podzielonych, które są grafami silnie akordowymi . Wiadomo również, że problem minimalnego zbioru dominującego pozostaje NP-zupełny dla grafów podzielonych.

Sekwencje stopni

Jedną z niezwykłych właściwości podzielonych wykresów jest to, że można je rozpoznać wyłącznie na podstawie ich sekwencji stopni . Niech ciąg stopni grafu G będzie d ₁ ≥ d ₂ ≥ ... ≥ d _n , i niech m będzie największą wartością i taką, że d _i ≥ i - 1. Wtedy G jest grafem podzielonym wtedy i tylko wtedy, gdy

${\ Displaystyle \ suma _ {i = 1} ^ {m} d_ {i} = m (m-1) + \ suma _ {i = m + 1} ^ {n} d_ {i}.}$

Jeśli tak jest, to wierzchołki m o największych stopniach tworzą maksymalną klikę w G , a pozostałe wierzchołki stanowią zbiór niezależny.

Zliczanie podzielonych wykresów

Royle (2000) wykazał, że wykresy podziału n- wierzchołków z n odpowiadają jeden do jednego z pewnymi rodzinami Spernerów . Korzystając z tego faktu, wyznaczył wzór na liczbę nieizomorficznych grafów podziału na n wierzchołkach. Dla małych wartości n , zaczynając od n = 1, te liczby to

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (sekwencja A048194 w OEIS ).

Ten enumeratywny wynik udowodnili również wcześniej Tyszkiewicz i Czerniak (1990) .

Uwagi

Bibliografia

Dalsza lektura

• Rozdział o podzielonych wykresach pojawia się w książce Martina Charlesa Golumbica „Algorithmic Graph Theory and Perfect Graphs”.