Twierdzenie Rudy
Twierdzenie Ore'a jest wynikiem teorii grafów udowodnionym w 1960 roku przez norweskiego matematyka Øysteina Ore'a . Daje warunek wystarczający, aby graf był hamiltonowski , zasadniczo stwierdzając, że graf z wystarczającą liczbą krawędzi musi zawierać cykl Hamiltona . W szczególności twierdzenie uwzględnia sumę stopni par niesąsiadujących ze sobą wierzchołków : jeśli każda taka para ma sumę co najmniej równą całkowitej liczbie wierzchołków na wykresie, wówczas graf jest hamiltonowski.
Formalne oświadczenie
Niech G będzie grafem (skończonym i prostym) o n ≥ 3 wierzchołkach. Przez deg v oznaczamy stopień wierzchołka v w G , tj. liczbę krawędzi padających w G do v . Następnie twierdzenie Ore'a stwierdza, że jeśli
-
(∗)
wówczas G jest hamiltonianem .
Dowód
Równoważne jest pokazanie, że każdy niehamiltonowski graf G nie spełnia warunku (∗) . Odpowiednio, niech G będzie grafem na n ≥ 3 wierzchołkach, który nie jest hamiltonowski, i niech H zostanie utworzony z G poprzez dodawanie po jednej krawędzi, która nie tworzy cyklu hamiltonowskiego, dopóki nie będzie można dodać więcej krawędzi. Niech x i y będą dowolnymi dwoma niesąsiadującymi wierzchołkami w H . Następnie dodając krawędź xy do H utworzyłby co najmniej jeden nowy cykl Hamiltona, a krawędzie inne niż xy w takim cyklu muszą tworzyć ścieżkę Hamiltona v 1 v 2 ... v n w H z x = v 1 i y = v n . Dla każdego indeksu i w zakresie 2 ≤ i ≤ n rozważ dwie możliwe krawędzie w H od v 1 do v ja i od v ja - 1 do v n . Co najwyżej jedna z tych dwóch krawędzi może występować w H , gdyż w przeciwnym razie cykl v 1 v 2 ... v i - 1 v n v n - 1 ... v i byłby cyklem Hamiltona. Zatem całkowita liczba krawędzi przypadających na v 1 lub v n jest co najwyżej równa liczbie wyborów i , czyli n - 1 . Dlatego H nie spełnia własności (∗) , która wymaga, aby całkowita liczba krawędzi ( deg v 1 + deg v n ) była większa lub równa n . Ponieważ stopnie wierzchołków w G są co najwyżej równe stopniom w H , wynika z tego, że G również nie spełnia własności (∗) .
Algorytm
Palmer (1997) opisuje następujący prosty algorytm konstruowania cyklu Hamiltona na grafie spełniającym warunek Ore'a.
- Ułóż wierzchołki w dowolny sposób w cykl, ignorując przylegania na grafie.
- Chociaż cykl zawiera dwa kolejne wierzchołki v i oraz vi : + 1 , które na grafie nie sąsiadują ze sobą, wykonaj dwa poniższe kroki
- Wyszukaj indeks j taki, że cztery wierzchołki v i , v i + 1 , v j i v j + 1 są różne i takie, że graf zawiera krawędzie od v i do v j i od v j + 1 do v ja + 1
- Odwróć część cyklu pomiędzy v i + 1 a v j (włącznie).
Każdy krok zwiększa liczbę kolejnych par w cyklu, które sąsiadują ze sobą na wykresie, o jedną lub dwie pary (w zależności od tego, czy v j i v j + 1 już sąsiadują), więc zewnętrzna pętla może wystąpić najwyżej n razy przed zakończeniem algorytmu, gdzie n jest liczbą wierzchołków danego grafu. Argumentem podobnym do tego w dowodzie twierdzenia musi istnieć pożądany indeks j , w przeciwnym razie nieprzylegające wierzchołki v i oraz v i + 1 miałby zbyt mały stopień łączny. Znalezienie i i j oraz odwrócenie części cyklu można dokonać w czasie O( n ). Zatem całkowity czas działania algorytmu wynosi O( n 2 ), co odpowiada liczbie krawędzi na grafie wejściowym.
Powiązane wyniki
Twierdzenie Ore'a jest uogólnieniem twierdzenia Diraca , że gdy każdy wierzchołek ma stopień co najmniej n /2 , graf jest hamiltonowski. Bo jeśli graf spełnia warunek Diraca, to oczywiście każda para wierzchołków ma stopnie dodawane do co najmniej n .
Z kolei twierdzenie Ore'a jest uogólnione przez twierdzenie Bondy'ego-Chvátala . Można zdefiniować operację domknięcia na grafie, w której, ilekroć dwa nieprzylegające wierzchołki mają stopnie sumujące się do co najmniej n , dodaje się łączącą je krawędź; jeżeli wykres spełnia warunki twierdzenia Ore’a, to jego domknięcie jest grafem pełnym . Twierdzenie Bondy’ego – Chvátala stwierdza, że wykres jest hamiltonowski wtedy i tylko wtedy, gdy jego zamknięcie jest hamiltonowskie; ponieważ pełny wykres jest hamiltonowski, twierdzenie Ore'a jest natychmiastową konsekwencją.
Woodall (1972) znalazł wersję twierdzenia Ore'a, która ma zastosowanie do grafów skierowanych . Załóżmy, że dwuznak G ma tę właściwość, że dla każdych dwóch wierzchołków u i v istnieje albo krawędź od u do v , albo stopień zewnętrzny u plus stopień v jest równy lub większy od liczby wierzchołków w G . Następnie, zgodnie z twierdzeniem Woodalla, G zawiera skierowany cykl Hamiltona. Twierdzenie Ore'a można uzyskać od Woodalla, zastępując każdą krawędź danego nieskierowanego wykresu parą skierowanych krawędzi. Ściśle powiązane twierdzenie Meyniela (1973) stwierdza, że n -wierzchołek silnie powiązany digraf z własnością, że dla każdych dwóch nieprzylegających wierzchołków u i v , całkowita liczba krawędzi przypadających na u lub v wynosi co najmniej 2 n - 1 musi być Hamiltonem.
Twierdzenie Ore'a można również wzmocnić, aby uzyskać silniejszy wniosek niż hamiltoniczność, w wyniku warunku stopnia w twierdzeniu. W szczególności każdy graf spełniający warunki twierdzenia Ore'a jest albo regularnym pełnym grafem dwudzielnym , albo jest pancykliczny ( Bondy 1971 ).
- Bondy, JA (1971), „Pancykliczne wykresy I”, Journal of Combinatorial Theory, Series B , 11 (1): 80–84, doi : 10.1016/0095-8956(71)90016-5 .
- Meyniel, M. (1973), „Une warunku suffisante d'existence d'un obwodu hamiltonien dans un graphe orienté”, Journal of Combinatorial Theory, Series B (po francusku), 14 (2): 137–147, doi : 10.1016 /0095-8956(73)90057-9 .
- Ruda, Ø. (1960), „Notatka o obwodach Hamiltona”, American Mathematical Monthly , 67 (1): 55, doi : 10.2307/2308928 , JSTOR 2308928 .
- Palmer, EM (1997), „Ukryty algorytm twierdzenia Ore'a o cyklach Hamiltona”, Computers & Mathematics with Applications , 34 (11): 113–119, doi : 10.1016/S0898-1221(97)00225-3 , MR 1486890 .
- Woodall, DR (1972), „Wystarczające warunki dla obwodów na wykresach”, Proceedings of the London Mathematical Society , Third Series, 24 : 739–755, doi : 10.1112/plms/s3-24.4.739 , MR 0318000 .