Wykres wierzchołka

Wykres wierzchołkowy. Podgraf przez usunięcie czerwonego wierzchołka jest planarny .

W teorii grafów , gałęzi matematyki, wykres wierzchołkowy to wykres , który można uczynić planarnym przez usunięcie pojedynczego wierzchołka . Usunięty wierzchołek nazywamy wierzchołkiem grafu. Jest to wierzchołek , a nie wierzchołek , ponieważ wykres wierzchołka może mieć więcej niż jeden wierzchołek; na przykład w grafach minimalnych nieplanarnych K ₅ lub K _3,3 każdy wierzchołek jest wierzchołkiem. Grafy wierzchołkowe obejmują grafy, które same są planarne, w którym to przypadku ponownie każdy wierzchołek jest wierzchołkiem. Graf zerowy jest również liczony jako wykres wierzchołkowy, mimo że nie ma żadnego wierzchołka do usunięcia.

Grafy wierzchołkowe są zamknięte w ramach operacji przyjmowania nieletnich i odgrywają rolę w kilku innych aspektach teorii mniejszych grafów: osadzanie bez powiązań , hipoteza Hadwigera , grafy redukowalne YΔY oraz relacje między szerokością drzewa a średnicą grafu .

Charakterystyka i rozpoznawanie

Grafy wierzchołkowe są zamknięte w ramach operacji brania drugorzędnych : skrócenie dowolnej krawędzi lub usunięcie dowolnej krawędzi lub wierzchołka prowadzi do innego wykresu wierzchołkowego. Bo jeśli G jest wykresem wierzchołkowym z wierzchołkiem v , to każde skrócenie lub usunięcie, które nie obejmuje v , zachowuje płaskość pozostałego grafu, podobnie jak każde usunięcie krawędzi incydentnej z v . Jeśli krawędź padająca na v zostanie skrócona, wpływ na pozostały wykres jest równoważny usunięciu drugiego punktu końcowego krawędzi. A jeśli v zostanie usunięte, jako wierzchołek można wybrać dowolny inny wierzchołek.

Zgodnie z twierdzeniem Robertsona-Seymoura , ponieważ tworzą one zamkniętą rodzinę grafów, grafy wierzchołkowe mają zabronioną charakterystykę grafów . Istnieje tylko skończenie wiele grafów, które nie są ani grafami wierzchołkowymi, ani nie mają innego wykresu niewierzchołkowego jako drugorzędnego. Grafy te są zabronione ze względu na właściwość bycia wykresem wierzchołkowym. Każdy inny graf G jest grafem wierzchołkowym wtedy i tylko wtedy, gdy żadna z zabronionych drugorzędnych nie jest grafem drugorzędnym G . Te zakazane grafy drugorzędne obejmują siedem grafów rodziny Petersenów , trzy rozłączne grafy utworzone z rozłącznych związków dwóch z K ₅ i K _3,3 oraz wiele innych grafów. Jednak ich pełny opis pozostaje nieznany.

Pomimo tego, że cały zestaw zabronionych nieletnich pozostaje nieznany, można sprawdzić, czy dany wykres jest wierzchołkiem, a jeśli tak, to znaleźć wierzchołek dla grafu w czasie liniowym . Mówiąc bardziej ogólnie, dla dowolnej ustalonej stałej k można rozpoznać w czasie liniowym grafy k -wierzchołkowe , w których usunięcie pewnego starannie wybranego zestawu co najwyżej k wierzchołków prowadzi do grafu planarnego. Jeśli k jest zmienną, problem jest NP-zupełny .

Liczba chromatyczna

Każdy wykres wierzchołkowy ma liczbę chromatyczną co najwyżej pięć: bazowy wykres planarny wymaga co najwyżej czterech kolorów zgodnie z twierdzeniem o czterech kolorach , a pozostały wierzchołek potrzebuje co najwyżej jednego dodatkowego koloru. Robertson, Seymour i Thomas (1993a) wykorzystali ten fakt w swoim dowodzie przypadku k = 6 hipotezy Hadwigera , stwierdzając, że każdy graf 6-chromatyczny ma kompletny graf K ₆ jako drugorzędny: wykazali, że każdy minimalny kontrprzykład do przypuszczenie musiałoby być wykresem wierzchołkowym, ale ponieważ nie ma 6-chromatycznych wykresów wierzchołkowych, taki kontrprzykład nie może istnieć.

Nierozwiązany problem z matematyki :

K ₆ 6 bez mniejszych wierzchołków spójnych z wierzchołkami jest grafem wierzchołkowym?

(więcej nierozwiązanych problemów z matematyki)

Jørgensen (1994) przypuszczał, że każdy graf połączony z 6 wierzchołkami , który nie ma K ₆ jako drugorzędnego, musi być grafem wierzchołkowym. Gdyby to zostało udowodnione, wynik Robertsona – Seymoura – Thomasa dotyczący hipotezy Hadwigera byłby natychmiastową konsekwencją. Hipoteza Jørgensena pozostaje niesprawdzona. Jeśli jednak jest fałszywa, ma tylko skończenie wiele kontrprzykładów.

Lokalna szerokość drzewa

Rodzina grafów F ma ograniczoną lokalną szerokość drzewa , jeśli wykresy w F są zgodne z funkcjonalną zależnością między średnicą a szerokością drzewa : istnieje funkcja f taka, że ​​szerokość drzewa wykresu średnica- d w F wynosi co najwyżej f ( d ) . Wykresy wierzchołków nie mają ograniczonej lokalnej szerokości drzewa: wykresy wierzchołków utworzone przez połączenie wierzchołka wierzchołka z każdym wierzchołkiem wykresu siatki n × n mają szerokość drzewa n i średnicę 2, więc szerokość drzewa nie jest ograniczona funkcją średnicy dla tych wykresów . Jednak grafy wierzchołkowe są ściśle powiązane z ograniczoną lokalną szerokością drzewa: rodziny grafów F z zamkniętymi pomniejszymi grafami, które mają ograniczoną lokalną szerokość drzewa, są dokładnie tymi rodzinami, które mają wykres wierzchołkowy jako jeden z zabronionych drugorzędnych. Zamknięta rodzina grafów z wierzchołkiem jako jednym z zabronionych drugorzędnych jest znana jako bez wierzchołka-mniejszego . Za pomocą tej terminologii związek między grafami wierzchołkowymi a lokalną szerokością drzewa można ponownie przedstawić jako fakt, że rodziny grafów bez mniejszych wierzchołków są takie same, jak rodziny grafów mniejszych i zamkniętych z ograniczoną lokalną szerokością drzewa.

Koncepcja ograniczonej lokalnej szerokości drzewa stanowi podstawę teorii dwuwymiarowości i pozwala na dokładne rozwiązanie wielu problemów algorytmicznych na grafach bez wierzchołków mniejszych za pomocą algorytmu czasu wielomianowego lub algorytmu o stałych parametrach , lub przybliżenie za pomocą schemat aproksymacji w czasie wielomianowym . Rodziny grafów bez wierzchołków mniejszych są zgodne ze wzmocnioną wersją twierdzenia o strukturze grafów , co prowadzi do dodatkowych algorytmów aproksymacji do kolorowania grafów i problemu komiwojażera . Jednak niektóre z tych wyników można również rozszerzyć na dowolne rodziny grafów mniejszych-zamkniętych za pomocą twierdzeń strukturalnych odnoszących je do grafów bez wierzchołków mniejszych.

Osadzenia

Jeśli G jest grafem wierzchołkowym z wierzchołkiem v , a τ jest minimalną liczbą ścian potrzebnych do pokrycia wszystkich sąsiadów v w planarnym osadzeniu G \ { v }, to G można osadzić na dwuwymiarowej powierzchni rodzaju τ – 1 : po prostu dodaj tę liczbę mostków do płaskiego osadzania, łącząc ze sobą wszystkie ściany, w które v musi być połączone. Na przykład dodanie pojedynczego wierzchołka do grafu planarnego (wykresu z τ = 1 ) daje graf planarny. Kiedy G \ { v } jest 3-spójny, jego granica mieści się w stałym współczynniku optymalnym: każde osadzenie powierzchniowe G wymaga rodzaju co najmniej τ / 160 . Jednak określenie optymalnego rodzaju osadzania powierzchni wykresu wierzchołkowego jest NP-trudne .

Używając drzew SPQR do zakodowania możliwych osadzeń płaskiej części grafu wierzchołkowego, możliwe jest obliczenie rysunku grafu w płaszczyźnie, w której jedyne przecięcia obejmują wierzchołek, minimalizując całkowitą liczbę przecięć, w wielomianach czas. Jeśli jednak dozwolone są dowolne przecięcia, minimalizacja liczby przecięć staje się NP-trudna, nawet w szczególnym przypadku grafów wierzchołkowych utworzonych przez dodanie pojedynczej krawędzi do wykresu planarnego.

Wykresy wierzchołkowe można również osadzać bez powiązań w przestrzeni trójwymiarowej: można je osadzać w taki sposób, że każdy cykl na wykresie jest granicą dysku, którego nie przecina żadna inna cecha wykresu. Rysunek tego typu można uzyskać, rysując płaską część wykresu na płaszczyźnie, umieszczając wierzchołek nad płaszczyzną i łącząc wierzchołek prostymi krawędziami z każdym z sąsiadów. Grafy, które można osadzać bez powiązań, tworzą zamkniętą rodzinę nieletnich z siedmioma grafami z rodziny Petersena jako ich minimalnymi zabronionymi nieletnimi; dlatego te wykresy są również zabronione jako drugorzędne dla wykresów wierzchołków. Istnieją jednak wykresy, które można osadzić bez powiązań, które nie są wykresami wierzchołkowymi.

Redukowalność YΔY

Przykład Robertsona wykresu wierzchołkowego nieredukowalnego YΔY.

Spójny graf jest redukowalny w YΔY, jeśli można go zredukować do pojedynczego wierzchołka za pomocą sekwencji kroków, z których każdy jest transformacją Δ-Y lub Y-Δ , usunięciem pętli własnej lub wielokrotnym sąsiedztwem, usunięciem wierzchołek z jednym sąsiadem oraz zastąpienie wierzchołka stopnia drugiego i dwóch sąsiednich krawędzi pojedynczą krawędzią.

Podobnie jak grafy wierzchołkowe i grafy bez linków, które można osadzić, grafy redukowalne YΔY są zamknięte pod mniejszymi grafami. I, podobnie jak grafy bez linków, które można osadzić, grafy redukowalne YΔY mają siedem grafów z rodziny Petersena jako zabronione drugorzędne, co nasuwa pytanie, czy są to jedyne zabronione nieletnie wykresy i czy grafy redukowalne YΔY są takie same jak bezpołączeniowe osadzone wykresy. Jednak Neil Robertson podał przykład wykresu wierzchołkowego, który nie jest redukowalny w YΔY. Ponieważ każdy wykres wierzchołkowy można osadzić bez powiązań, pokazuje to, że istnieją grafy, które można osadzić bez powiązań, ale nie można ich zredukować do YΔY, a zatem istnieją dodatkowe zabronione drugorzędne dla grafów redukowalnych do YΔY.

Wykres wierzchołkowy Robertsona pokazano na rysunku. Można to uzyskać, łącząc wierzchołek z każdym z wierzchołków trzeciego stopnia dwunastościanu rombowego lub łącząc dwa diametralnie przeciwległe wierzchołki czterowymiarowego wykresu hipersześcianu . Ponieważ wykres dwunastościanu rombowego jest płaski, wykres Robertsona jest wykresem wierzchołkowym. Jest to wykres bez trójkątów o minimalnym stopniu czwartym, więc nie można go zmienić żadną redukcją YΔY.

Grafy prawie planarne

Drabina Möbiusa z 16 wierzchołkami , przykład prawie planarnego wykresu.

Jeśli graf jest wykresem wierzchołkowym, niekoniecznie musi mieć unikalny wierzchołek. Na przykład w grafach mniejszych-minimalnych niepłaskich K ₅ i K _3,3 dowolny wierzchołek można wybrać jako wierzchołek. Wagner ( 1967 , 1970 ) zdefiniował graf prawie planarny jako nieplanarny graf wierzchołkowy z tą właściwością, że wszystkie wierzchołki mogą być wierzchołkami grafu; zatem K ₅ i K _3,3 są prawie płaskie. Dokonał klasyfikacji tych grafów na cztery podzbiory, z których jeden składa się z grafów, które (podobnie jak drabiny Möbiusa ) można osadzić na pasku Möbiusa w taki sposób, że pojedyncza krawędź paska pokrywa się z cyklem Hamiltona wykres. Przed dowodem twierdzenia o czterech kolorach udowodnił, że każdy prawie płaski graf można pokolorować co najwyżej czterema kolorami, z wyjątkiem wykresów utworzonych z wykresu kołowego z nieparzystym cyklem zewnętrznym przez zastąpienie wierzchołka piasty dwoma sąsiednimi wierzchołkami, które wymagają pięciu kolorów. Dodatkowo udowodnił, że z jednym wyjątkiem ( wykres dopełnienia sześcianu z ośmioma wierzchołkami ) każdy prawie planarny graf ma osadzenie na płaszczyźnie rzutowej .

Jednak wyrażenie „prawie planarny wykres” jest bardzo niejednoznaczne: było również używane w odniesieniu do wykresów wierzchołkowych, wykresów utworzonych przez dodanie jednej krawędzi do wykresu planarnego oraz wykresów utworzonych z płaskiego wykresu osadzonego przez zastąpienie ograniczonej liczby ścian przez „wiry” o ograniczonej szerokości ścieżki , a także dla innych mniej precyzyjnie zdefiniowanych zestawów grafów.

Powiązane klasy grafów

Mówimy, że graf abstrakcyjny jest n -wierzchołkiem, jeśli można go uczynić planarnym, usuwając n lub mniej wierzchołków. Graf o 1 wierzchołku jest również nazywany wierzchołkiem.

Według Liptona i in. (2018) graf jest wierzchołkiem krawędzi , jeśli na wykresie jest jakaś krawędź, którą można usunąć, aby wykres był płaski. Graf jest wierzchołkiem skróconym , jeśli istnieje krawędź grafu, którą można skrócić, aby uzyskać planarność grafu.

Zobacz też

• Piramida wielościenna , 4-wymiarowy polytope, którego wierzchołki i krawędzie tworzą wykres wierzchołkowy, z wierzchołkiem przylegającym do każdego wierzchołka grafu wielościennego

Notatki

• Abraham, Ittaj; Gavoille, Cyril (2006), „Lokalizacja obiektu za pomocą separatorów ścieżek”, Proc. 25. Sympozjum ACM na temat zasad przetwarzania rozproszonego (PODC '06) , s. 188–197, doi : 10.1145/1146381.1146411 .
• archidiakon, Dan ; Bonnington, CPC Paul (2004), „Przeszkody w osadzeniu wykresów sześciennych na powierzchni wrzeciona”, Journal of Combinatorial Theory , Seria B , 91 (2): 229–252, doi : 10.1016/j.jctb.2004.02.001 .
• Cabello, Sergio; Mohar, Bojan (2010), „Dodanie jednej krawędzi do grafów planarnych utrudnia przekraczanie liczby”, Proc. 26th ACM Symposium on Computational Geometry (SoCG '10) (PDF) , s. 68–76, doi : 10.1145/1810959.1810972 , zarchiwizowane z oryginału (PDF) w dniu 14.03.2012 , pobrane 2010-08-02 .
• Chimani, Markus; Gutwenger, Carsten; Mutzel, Petra ; Wolf, Christian (2009), „Wstawianie wierzchołka do płaskiego wykresu”, Proc. 20. Sympozjum ACM-SIAM na temat algorytmów dyskretnych (SODA '09) , s. 375–383 .
• Demaine, Erik D .; Hajiaghayi, Mohammad Taghi (2004), „Średnica i szerokość drzewa w rodzinach mniejszych grafów zamkniętych, powtórka” , Algorithmica , 40 (3): 211–215, doi : 10.1007 / s00453-004-1106-1 .
• Demaine, Erik D .; Hajiaghayi, Mohammad Taghi (2005), „Dwuwymiarowość: nowe połączenia między algorytmami FPT a PTAS”, Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA '05) , s. 590–601, zarchiwizowane z oryginału w dniu 2018-12-11 , pobrane 2010-08-02 .
• Demaine, Erik D .; Hadiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2009), „Algorytmy aproksymacji za pomocą wyników strukturalnych dla grafów bez wierzchołka mniejszego” (PDF) , Proc. 36. Międzynarodowe Kolokwium Automaty, Języki i Programowanie (ICALP '09) , Notatki z wykładów z informatyki, tom. 5555, Springer-Verlag, s. 316–327, doi : 10.1007/978-3-642-02927-1_27 .
• Eppstein, David (2000), „Średnica i szerokość drzewa w rodzinach mniejszych grafów zamkniętych”, Algorithmica , 27 (3): 275–291, arXiv : math.CO/9907126 , doi : 10.1007/s004530010020 .
• Frick, Markus; Grohe, Martin (2001), „Decydowanie o właściwościach pierwszego rzędu struktur rozkładających się lokalnie na drzewach”, Journal of the ACM , 48 (6): 1184–1206, arXiv : cs / 0004007 , doi : 10.1145/504794.504798 .
• Grohe, Martin (2003), „Lokalna szerokość drzewa, wykluczone drugorzędne i algorytmy aproksymacji”, Combinatorica , 23 (4): 613–632, arXiv : math.CO/0001128 , doi : 10.1007/s00493-003-0037- 9 .
• Gupta, A.; Impagliazzo, R. (1991), "Computing Planar Intertwines" , Proc. 32. Sympozjum IEEE na temat podstaw informatyki (FOCS '91) , IEEE Computer Society, s. 802–811, doi : 10.1109/SFCS.1991.185452 .
• Jørgensen, Leif K. (1994), „Skurcze do K ₈ ”, Journal of Graph Theory , 18 (5): 431–448, doi : 10.1002/jgt.3190180502 . Cytowane przez Robertsona, Seymoura i Thomasa ( 1993a , 1993c ).
• Kawarabayashi, Ken-ichi (2009), „Planarność umożliwiająca kilka wierzchołków błędów w czasie liniowym” (PDF) , Proc. 50. Sympozjum IEEE na temat podstaw informatyki (FOCS '09) , IEEE Computer Society, s. 639–648, doi : 10.1109/FOCS.2009.45 .
• Kawarabayashi, Ken-ichi ; Norine, Serguei; Tomasz Robin ; Wollan, Paul (2012), nieletni w dużych 6 $wykresach$ połączonych , arXiv : , Bibcode : 2012arXiv1203,2192K .
• Lewis, John M.; Yannakakis , Mihalis ( 1980 ) _ _ _ 4 .
• Lipton, Maks; Mackall, Eoin; Mattman, Thomas W.; Pierce, Mike; Robinson, Samanta; Tomasz, Jeremy; Weinschelbaum, Ilan (2018), „Sześć wariacji na temat: wykresy prawie planarne”, Involve, A Journal of Mathematics , 11 (3): 413–448, arXiv : 1608.01973 , doi : 10.2140/involve.2018.11.413 .
• Mohar, Bojan (2001), „Pokrycia twarzy i problem z rodzajem wykresów wierzchołków” (PDF) , Journal of Combinatorial Theory, Series B , 82 (1): 102–117, doi : 10.1006/jctb.2000.2026 , zarchiwizowane z oryginał (PDF) w dniu 22.09.2017 , pobrano 2010-08-02 .
• Pierce, Mike (2014), Wyszukiwanie i klasyfikowanie skończonego zestawu mniejszych i minimalnych grafów bez wierzchołka (PDF) , praca dyplomowa z wyróżnieniem, California State University, Chico .
• Robertson, Neil ; Seymour, Paweł ; Thomas, Robin (1993a), „Przypuszczenie Hadwigera dla grafów wolnych od K ₆ ” (PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007 / BF01202354 .
•   Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993b), „Bezpołączeniowe osadzenie wykresów w przestrzeni 3”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , MR 1164063 .
• Robertson, Neil ; Seymour, Paweł ; Thomas, Robin (1993c), „Ankieta osadzeń bez linków”, w: Robertson, Neil ; Seymour, Paul (red.), Teoria struktury grafów: Proc. Wspólna letnia konferencja naukowa AMS – IMS – SIAM na temat mniejszych wykresów (PDF) , współczesna matematyka, tom. 147, Amerykańskie Towarzystwo Matematyczne, s. 125–136 .
• Truemper, Klaus (1992), Matroid Decomposition (PDF) , Academic Press, s. 100–101 .
• Wagner, Klaus (1967), „Fastplättbare Graphen”, Journal of Combinatorial Theory (w języku niemieckim), 3 (4): 326–365, doi : 10.1016 / S0021-9800 (67) 80103-0 .
• Wagner, Klaus (1970), „Zum basisproblem der nicht in die projektive ebene einbettbaren graphen, I”, Journal of Combinatorial Theory (w języku niemieckim), 9 (1): 27–43, doi : 10.1016 / S0021-9800 (70) 80052-7 .