Twierdzenie Fleischnera

Graf połączony z dwoma wierzchołkami, jego kwadrat i cykl Hamiltona w kwadracie

W teorii grafów , gałęzi matematyki, twierdzenie Fleischnera daje warunek wystarczający, aby graf zawierał cykl Hamiltona . Stwierdza, że jeśli $jest$ $z$ połączonym 2 wierzchołkami to kwadrat jest hamiltonowski. Jej nazwa pochodzi od Herberta Fleischnera , który opublikował swój dowód w 1974 roku.

Definicje i stwierdzenie

Wykres nieskierowany jest $hamiltonowski,$ jeśli zawiera cykl który dotyka każdego z jego wierzchołków dokładnie raz. Jest połączony w 2 wierzchołki, jeśli nie ma wierzchołka przegubowego, wierzchołka, którego usunięcie spowodowałoby rozłączenie pozostałego wykresu. Nie każdy graf połączony z 2 wierzchołkami jest hamiltonowski; kontrprzykłady obejmują wykres Petersena i pełny wykres dwudzielny ${\ Displaystyle K_ {2,3}}$ .

Kwadrat z $}$ $wykres$ , który ma ten sam zestaw wierzchołków co $i$ w którym dwa wierzchołki sąsiadują ze sobą wtedy i tylko wtedy, gdy mają sol { odległość co najwyżej dwa w ${\ displaystyle G}$ . Twierdzenie Fleischnera stwierdza, że kwadrat skończonego wykresu połączonego z 2 wierzchołkami z co najmniej trzema wierzchołkami musi zawsze być hamiltonowski. Równoważnie, wierzchołki każdego wykresu połączonego z 2 wierzchołkami można ułożyć w cykliczny porządek $, tak$ sąsiednie wierzchołki w tej kolejności znajdują się w odległości co najwyżej dwóch od siebie w ${\ displaystyle G}$ .

Rozszerzenia

W twierdzeniu Fleischnera możliwe jest ograniczenie cyklu Hamiltona w taki sposób, że dla danych wierzchołków i $w$ { \ displaystyle $}$ ${2}$ sol ${\ displaystyle G$ $dwie$ krawędzie ${$ z i jedną krawędź incydentu z $displaystyle$ $}$ . $.$ $więcej$ jeśli i $sąsiadują$ ze sobą w $to$ są to trzy różne

Oprócz posiadania cyklu Hamiltona, kwadrat wykresu połączonego z 2 wierzchołkami $musi$ być również spójny Hamiltona (co oznacza, że ma ścieżkę Hamiltona zaczynającą się i kończącą w dowolnych wyznaczonych wierzchołkach) i 1-hamiltonowski. (co oznacza, że jeśli jakikolwiek wierzchołek zostanie usunięty, pozostały wykres nadal ma cykl Hamiltona). Musi to być również wierzchołek pancykliczny , co oznacza $,$ że dla każdego wierzchołka każdej liczby $całkowitej$ z ${\ Displaystyle 3 \ równoważnik k \ równoważnik | V (G)}$ istnieje cykl o długości $k}$ k $displaystyle$ .

Jeśli graf $wierzchołkami$ , to jego kwadrat może, ale nie musi, mieć cykl Hamiltona, a określenie, czy go ma, jest NP-zupełne .

$może$ mieć cyklu Hamiltona, ponieważ każdy cykl jest skończony, ale Carsten Thomassen udowodnił, że jeśli jest nieskończonym lokalnie skończonym grafem połączonym z 2 wierzchołkami z jednym , to ${\ displaystyle G ^ {2}}$ koniecznie ma podwójnie nieskończoną ścieżkę Hamiltona. $jest lokalnie$ bardziej ogólnie, jeśli $skończony ,$ z 2 wierzchołkami i ma dowolną liczbę końców, to koło Hamiltona. W zwartej przestrzeni topologicznej utworzonej przez postrzeganie wykresu jako uproszczonego kompleksu i dodanie dodatkowego punktu w nieskończoności do każdego z jego końców, koło Hamiltona jest definiowane jako podprzestrzeń, która jest homeomorficzna z kołem euklidesowym i obejmuje każdy wierzchołek.

Algorytmy

Cykl Hamiltona w kwadracie wykresu połączonego z $2$ można znaleźć w czasie liniowym, poprawiając pierwsze algorytmiczne rozwiązanie Lau czasu działania ${\ Displaystyle O (n ^ {2})}$ . Twierdzenie Fleischnera można wykorzystać do zapewnienia przybliżenia 2 do problemu komiwojażera z wąskim gardłem w przestrzeniach metrycznych .

Historia

Dowód twierdzenia Fleischnera został ogłoszony przez Herberta Fleischnera w 1971 roku i opublikowany przez niego w 1974 roku, rozwiązując hipotezę Crispina Nasha-Williamsa z 1966 roku , również dokonaną niezależnie przez LW Beineke i Michaela D. Plummera . W swojej recenzji artykułu Fleischnera Nash-Williams napisał, że rozwiązał on „dobrze znany problem, który przez kilka lat pokonywał pomysłowość innych teoretyków grafów”.

Oryginalny dowód Fleischnera był skomplikowany. Václav Chvátal w pracy, w której wynalazł $wykresu$ , zauważył $;$ że kwadrat wykresu połączonego z wierzchołkami jest z konieczności -twardy przypuszczał , że grafy 2-twarde są hamiltonowskie, z czego wynikałby kolejny dowód twierdzenia Fleischnera. Później odkryto kontrprzykłady dla tego przypuszczenia, ale możliwość, że skończona granica wytrzymałości może implikować hamiltoniczność, pozostaje ważnym otwartym problemem w teorii grafów. Prostszy dowód zarówno twierdzenia Fleischnera, jak i jego rozszerzeń przez Chartranda i in. (1974) , podał Říha (1991) , a inny uproszczony dowód twierdzenia podał Georgakopoulos (2009a) .

Notatki

Podstawowe źródła

Alstrup, Stefan; Georgakopoulos, Agelos; Rotenberg, Ewa; Thomassen, Carsten (2018), „A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time”, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , s. 1645–1649, doi : 10.1137/ 1.9781611975031.107 , ISBN 978-1-61197-503-1
Bauer, D.; Broersma, HJ; Veldman, HJ (2000), „Nie każdy wykres 2-twardy jest hamiltonianem” , Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), Discrete Applied Mathematics , 99 (1–3): 317–321, doi : 10.1016/S0166-218X(99)00141-9 , MR 1743840 .
Bondy, JA (1971), „Wykresy pancykliczne”, Proceedings of the Second Louisiana Conference on Combinatoryics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971) , Baton Rouge, Louisiana: Louisiana State University, s. 167-172, MR 0325458 .
Chartrand, G .; Hobbs, Artur M .; Jung, Ha; Kapoor, SF; Nash-Williams, C. St. JA (1974), „Kwadrat bloku jest połączony hamiltonicznie”, Journal of Combinatorial Theory , Seria B, 16 (3): 290–292, doi : 10.1016 / 0095-8956 (74 )90075-6 , MR 0345865 .
Chvátal, Václav (1973), „Twarde wykresy i obwody hamiltonowskie”, Matematyka dyskretna , 5 (3): 215–228, doi : 10.1016/0012-365X (73) 90138-6 , MR 0316301 .
Fleischner, Herbert (1974), „Kwadrat każdego wykresu dwóch połączonych jest hamiltonianem”, Journal of Combinatorial Theory , Seria B, 16 : 29–34, doi : 10.1016/0095-8956 (74) 90091-4 , MR 0332573 .
Fleischner, H. (1976), „W kwadracie grafów, hamiltoniczność i pancykliczność, powiązanie hamiltonowskie i panpowiązanie są pojęciami równoważnymi”, Monatshefte für Mathematik , 82 (2): 125–149, doi : 10.1007 / BF01305995 , MR 0427135 .
Georgakopoulos, Agelos (2009a), „Krótki dowód twierdzenia Fleischnera”, Matematyka dyskretna , 309 (23–24): 6632–6634, doi : 10.1016/j.disc.2009.06.024 , MR 2558627 .
Georgakopoulos, Agelos (2009b), „Nieskończone cykle Hamiltona w kwadratach grafów lokalnie skończonych”, Advances in Mathematics , 220 (3): 670–705, doi : 10.1016 / j.aim.2008.09.014 , MR 2483226 .
Hobbs, Arthur M. (1976), „Kwadrat bloku to wierzchołek pancykliczny”, Journal of Combinatorial Theory , Seria B, 20 (1): 1–4, doi : 10,1016 / 0095-8956 (76) 90061-7 , MR 0416980 .
Hochbaum, Dorit S .; Shmoys, David B. (1986), „Ujednolicone podejście do algorytmów aproksymacji problemów wąskich gardeł” , Journal of the ACM , Nowy Jork, NY, USA: ACM, 33 (3): 533–550, doi : 10.1145/5925.5933 .
Lau, HT (1980), Znalezienie cyklu Hamiltona w kwadracie bloku. , doktor praca magisterska, Montreal: Uniwersytet McGill . Cytowane przez Hochbauma i Shmoysa (1986) .
Muttel, Janina; Rautenbach, Dieter (2012), „Krótki dowód wszechstronnej wersji twierdzenia Fleischnera”, Discrete Mathematics , 313 (19): 1929–1933, doi : 10.1016/j.disc.2012.07.032 .
Parker, R. Garey; Rardin, Ronald L. (1984), „Gwarantowana heurystyka wydajności dla problemu komiwojażera z wąskim gardłem”, Operations Research Letters , 2 (6): 269–272, doi : 10.1016/0167-6377 (84) 90077-4 .
Říha, Stanislav (1991), „Nowy dowód twierdzenia Fleischnera”, Journal of Combinatorial Theory , Seria B, 52 (1): 117–123, doi : 10.1016 / 0095-8956 (91) 90098-5 , MR 1109427 .
Thomassen, Carsten (1978), „Hamiltonowskie ścieżki w kwadratach nieskończonych lokalnie skończonych bloków”, w: Bollobás, B. (red.), Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , Annals of Discrete Matematyka, tom. 3, Elsevier, s. 269–277 , doi : 10.1016/S0167-5060(08)70512-0 , ISBN 978-0-7204-0843-0 , MR 0499125 .
Underground, Polly (1978), „Na wykresach z kwadratami Hamiltona”, Discrete Mathematics , 21 (3): 323, doi : 10.1016/0012-365X (78) 90164-4 , MR 0522906 .

Drugorzędne źródła

Bondy, JA (1995), „Podstawowa teoria grafów: ścieżki i obwody”, Podręcznik kombinatoryki , tom. 1, 2 , Amsterdam: Elsevier, s. 3–110, MR 1373656 .
Chartrand, Gary ; Leśniak, Linda; Zhang, Ping (2010), Graphs & Digraphs (wyd. 5), CRC Press, s. 139, ISBN 9781439826270 .
Diestel, Reinhard (2012), „10. Cykle Hamiltona”, Graph Theory (PDF) (poprawione 4. wydanie elektroniczne)