Twierdzenie Orego

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 $G$ o n wierzchołkach, $n>2$ zachodzi następująca nierówność:

$\mathrm{deg}(v)+\mathrm{deg}(u)⩾n$

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

Wersja twierdzenia z drogą Hamiltona

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

$\mathrm{deg}(v)+\mathrm{deg}(u)⩾n-1$

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

Dowód twierdzenia

Dowód nie wprost. Przypuśćmy, że twierdzenie jest fałszywe, czyli dla pewnej liczby $n$ istnieje kontrprzykład $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ść $|E(G)|$ jest maksymalna. Jest to podgraf pełnego grafu hamiltonowskiego $K_n.$ Dodanie do $G$ krawędzi z grafu $K_n$ daje w wyniku graf, który nadal spełnia założenia twierdzenia i który ma więcej niż $|E(G)|$ krawędzi, a więc ze względu na wybór grafu $G$ tak powstały graf będzie miał cykl Hamiltona. To znaczy, że $G$ musi mieć (przynajmniej) drogę Hamiltona, określoną przez pewien ciąg wierzchołków, $v_1,v_2,\dots ,v_n.$ Ponieważ $G$ nie ma cyklu Hamiltona, to nie istnieje krawędź łącząca $v_{1}i{v}_n.$ Z kolei z założenia wiemy, że:

$\mathrm{deg}(v_1)+\mathrm{deg}(v_n)⩾n.$

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

$S_1=\{i:\{v_1,v_i\}\in E(G)\}$

i

$S_n=\{i:\{v_{i-1},v_n\}\in E(G)\},$

wtedy:

$|S_1|=\mathrm{deg}(v_1)$ i $|S_n|=\mathrm{deg}(v_n).$

Ponieważ:

$|S_1|+|S_n|⩾n$

i zbiór

$S_1\cup S_n$

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

$v_1,\dots ,v_{i-1},v_n,\dots ,v_i,v_1$

jest cyklem Hamilotona w grafie $G,$ sprzeczność. QED.

Zobacz też

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

Bibliografia

• Szablon:Cytuj książkę