Wykres uzupełniający - Complement graph

Wykres Petersen (po lewej) i jego wykres dopełniacza (po prawej).

W teorii wykres The dopełniacza lub odwrotny grafu G jest wykresem H w tych samych wierzchołki tak, że dwa różne wierzchołki H przylegają wtedy i tylko wtedy, gdy nie są one obok siebie w G . Oznacza to, że aby wygenerować dopełnienie grafu, należy wypełnić wszystkie brakujące krawędzie wymagane do utworzenia pełnego grafu i usunąć wszystkie krawędzie, które były wcześniej.

Dopełnienie nie jest dopełnieniem zbioru grafu; uzupełniane są tylko krawędzie.

Definicja

Niech G  = ( V ,  E ) będzie prostym grafem i niech K składa się ze wszystkich dwuelementowych podzbiorów V . Następnie H  = ( V ,  K  \  e ) jest dopełnieniem G , gdzie K  \  e jest względem dopełniacza z e w K . Na skierowanych wykresów , uzupełnienie może być określona w ten sam sposób, jako skierowany na tym samym wykresie zbiór wierzchołków stosując zbiór wszystkich elementów 2- uporządkowane pary z V na miejscu zbioru k we wzorze powyżej. Jeśli chodzi o macierz sąsiedztwa A grafu, jeśli Q jest macierzą sąsiedztwa całego grafu o tej samej liczbie wierzchołków (tzn. wszystkie wpisy są jednością z wyjątkiem wpisów przekątnych, które są zerami), to macierz sąsiedztwa dopełnienia A to kontrola jakości .

Dopełnienie nie jest zdefiniowane dla multigrafów . W grafach, które dopuszczają pętle własne (ale nie wielokrotne sąsiedztwo) dopełnienie G można zdefiniować, dodając pętlę własną do każdego wierzchołka, który nie ma go w G , i w inny sposób używając tego samego wzoru jak powyżej. Ta operacja różni się jednak od tej dla prostych grafów, ponieważ zastosowanie jej do grafu bez samopętli dałoby graf z samopętlami na wszystkich wierzchołkach.

Zastosowania i przykłady

Kilka koncepcji teorii grafów jest powiązanych ze sobą poprzez komplementację:

• Dopełnieniem grafu bez krawędzi jest graf zupełny i na odwrót.
• Dowolny podwykres indukowany wykresu dopełnienia wykresu G jest uzupełnieniem odpowiedniego podwykresu indukowanego w G .
• Niezależny zestaw na wykresie jest klika na wykresie dopełniacza i vice versa. Jest to szczególny przypadek poprzednich dwóch własności, ponieważ niezależny zbiór jest bezkrawędziowym podgrafem indukowanym, a klika jest kompletnym podgrafem indukowanym.
• Grupa automorfizmu grafu jest grupą automorfizmu jego dopełnienia.
• Dopełnieniem każdego grafu bez trójkątów jest graf bez pazurów , chociaż odwrotność nie jest prawdziwa.

Wykresy samouzupełniające się i klasy grafów

Ścieżka z czterema wierzchołkami jest samouzupełniająca się.

Graf samodopełniający to wykres, który jest izomorficzny z własnym dopełniacza. Przykłady obejmują wykres ścieżki z czterema wierzchołkami i wykres cyklu z pięcioma wierzchołkami . Nie jest znana charakterystyka grafów samouzupełniających się.

Kilka klas grafów jest samouzupełniających się w tym sensie, że uzupełnieniem dowolnego grafu w jednej z tych klas jest inny graf w tej samej klasie.

• Grafy doskonałe to takie, w których dla każdego indukowanego podgrafu liczba chromatyczna jest równa wielkości maksymalnej kliki. Fakt, że dopełnieniem idealnego wykresie jest również idealny jest idealny wykres twierdzenie z László Lovász .
• Kografy są definiowane jako grafy, które można zbudować z pojedynczych wierzchołków za pomocą operacji sumowania rozłącznego i dopełniania. Tworzą one samouzupełniającą się rodzinę grafów: uzupełnieniem dowolnego kografu jest inny, inny kograf. W przypadku kografów o więcej niż jednym wierzchołku, dokładnie jeden graf w każdej komplementarnej parze jest połączony, a jedną równoważną definicją kografów jest to, że każdy z ich połączonych indukowanych podgrafów ma rozłączne dopełnienie. Inną, samouzupełniającą się definicją jest to, że są to grafy bez indukowanego podgrafu w postaci ścieżki o czterech wierzchołkach.
• Inną samouzupełniającą się klasą grafów jest klasa grafów podzielonych , czyli grafów, w których wierzchołki można podzielić na klikę i niezależny zbiór. Ten sam podział daje niezależny zbiór i klikę w grafie dopełnienia.
• Te wykresy progowe są wykresy utworzone przez wielokrotne dodanie albo niezależne jeden wierzchołek (bez sąsiadów) lub uniwersalne wierzchołek (przylegającą do wszystkich wcześniej dodanej wierzchołków). Te dwie operacje są komplementarne i generują samouzupełniającą się klasę grafów.

Aspekty algorytmiczne

W analizie algorytmów na grafach ważne jest rozróżnienie między grafem a jego dopełnieniem, ponieważ graf rzadki (o małej liczbie krawędzi w porównaniu z liczbą par wierzchołków) nie będzie miał w zasadzie dopełnienia rzadkiego , a więc algorytm, który zajmuje czas proporcjonalny do liczby krawędzi na danym grafie, może zająć znacznie więcej czasu, jeśli ten sam algorytm zostanie uruchomiony na jawnej reprezentacji grafu dopełnienia. Dlatego naukowcy zbadali algorytmy, które wykonują standardowe obliczenia grafowe na dopełnieniu grafu wejściowego, używając niejawnej reprezentacji grafu , która nie wymaga jawnej konstrukcji grafu dopełnienia. W szczególności możliwe jest symulowanie przeszukiwania w głąb lub wszerz na grafie dopełnienia w czasie, który jest liniowy względem rozmiaru danego grafu, nawet jeśli graf dopełnienia może mieć znacznie większy rozmiar . Możliwe jest również wykorzystanie tych symulacji do obliczenia innych właściwości dotyczących łączności grafu dopełnienia.

Bibliografia