Twierdzenie Orego

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Twierdzenie Orego – twierdzenie podające warunek wystarczający na to, aby graf miał cykl Hamiltona. Zostało ono sformułowane w roku 1961 przez norweskiego matematyka Øysteina Orego.

Treść twierdzenia

Jeżeli w grafie prostym ${\displaystyle G}$ o n wierzchołkach, ${\displaystyle n>2}$ zachodzi następująca nierówność:

${\displaystyle \deg(v)+\deg(u)\geqslant n}$

dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków ${\displaystyle u}$ i ${\displaystyle v}$ (tj. takich, że ${\displaystyle \{v,u\}\notin E(G)}$), to graf ${\displaystyle G}$ posiada cykl Hamiltona.

Wersja twierdzenia z drogą Hamiltona

Jeżeli w grafie prostym ${\displaystyle G}$ o n wierzchołkach, ${\displaystyle n>2}$ zachodzi następująca nierówność:

${\displaystyle \deg(v)+\deg(u)\geqslant n-1}$

dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków ${\displaystyle u}$ i ${\displaystyle v}$ (tj. takich, że ${\displaystyle \{v,u\}\notin E(G)}$), to graf ${\displaystyle G}$ posiada drogę Hamiltona.

Dowód twierdzenia

Dowód nie wprost. Przypuśćmy, że twierdzenie jest fałszywe, czyli dla pewnej liczby ${\displaystyle n}$ istnieje kontrprzykład ${\displaystyle G}$ – graf, który spełnia założenie twierdzenia, ale nie jest Hamiltonowski. Spośród wszystkich takich grafów rozpatrzmy te, które mają najmniejszą liczbę wierzchołków, a spośród nich (grafów) taki, dla którego wartość ${\displaystyle |E(G)|}$ jest maksymalna. Jest to podgraf pełnego grafu hamiltonowskiego ${\displaystyle K_{n}.}$ Dodanie do ${\displaystyle G}$ krawędzi z grafu ${\displaystyle K_{n}}$ daje w wyniku graf, który nadal spełnia założenia twierdzenia i który ma więcej niż ${\displaystyle |E(G)|}$ krawędzi, a więc ze względu na wybór grafu ${\displaystyle G}$ tak powstały graf będzie miał cykl Hamiltona. To znaczy, że ${\displaystyle G}$ musi mieć (przynajmniej) drogę Hamiltona, określoną przez pewien ciąg wierzchołków, ${\displaystyle v_{1},v_{2},\dots ,v_{n}.}$ Ponieważ ${\displaystyle G}$ nie ma cyklu Hamiltona, to nie istnieje krawędź łącząca ${\displaystyle v_{1}\ i\ v_{n}.}$ Z kolei z założenia wiemy, że:

${\displaystyle \deg(v_{1})\ +\deg(v_{n})\geqslant n.}$

Można teraz zdefiniować podzbiory zbioru ${\displaystyle \{2,3,\dots ,n\}}$ takie, że:

${\displaystyle S_{1}\ =\ \{i:\ \{v_{1},v_{i}\}\in E(G)\}}$

i

${\displaystyle S_{n}\ =\{i:\{v_{i-1},v_{n}\}\in E(G)\},}$

wtedy:

${\displaystyle |S_{1}|\ =\deg(v_{1})}$ i ${\displaystyle |S_{n}|\ =\deg(v_{n}).}$

Ponieważ:

${\displaystyle |S_{1}|+|S_{n}|\geqslant n}$

i zbiór

${\displaystyle S_{1}\cup S_{n}}$

ma co najwyżej ${\displaystyle n-1}$ elementów, a więc zbiór ${\displaystyle S_{1}\cap S_{n}}$ musi być niepusty. Istnieje więc liczba ${\displaystyle i,}$ dla której istnieją krawędzie ${\displaystyle \{v_{1},v_{i}\}\ i\ \{v_{i-1},v_{n}\}.}$ Wtedy droga:

${\displaystyle v_{1},\dots ,v_{i-1},v_{n},\dots ,v_{i},v_{1}}$

jest cyklem Hamilotona w grafie ${\displaystyle G,}$ sprzeczność. QED.

Zobacz też

• twierdzenie Diraca
• twierdzenie o liczbie krawędzi (graf hamiltonowski)
• twierdzenie Bondy’ego-Chvátala

Bibliografia

• Robin James Wilson, Marek Kubale: Wprowadzenie do teorii grafów. Warszawa: Państwowe Wydawnictwo Naukowe, 1985, s. 53. ISBN 83-01-05247-3.