Oreův teorém je výsledkem teorie grafů , kterou v roce 1960 dokázal norský matematik Oistin Ore . Věta poskytuje dostatečnou podmínku pro to, aby byl graf hamiltonovský , v podstatě říká, že graf s „dostatečně velkým počtem hran“ musí obsahovat hamiltonovský cyklus . Zejména teorém uvažuje součty stupňů párů nesousedících vrcholů — pokud každý takový pár sčítá alespoň celkový počet vrcholů v grafu, pak je graf hamiltonovský.
Nechť G je (konečný a jednoduchý) graf s n ≥ 3 vrcholy. Označme stupněm v stupeň v v G , tj. počet hran dopadajících na v . Oreova věta říká, že pokud
stupeň v + stupeň w ≥ n pro libovolnou dvojici nesousedících vrcholů v a w grafu G , (*)pak G je hamiltonián .
Tvrzení je ekvivalentní tvrzení, že jakýkoli nehamiltonovský graf G porušuje podmínku (*). Nechť G je nehamiltonovský graf s n ≥ 3 vrcholy. Nechť graf H vznikne z G přidáním hran, jedné po druhé, které netvoří hamiltonovský cyklus, přičemž je možné takové hrany sčítat. Uvažujme libovolné dva nesousedící vrcholy x a y grafu H . Přidání hrany xy k H vytvoří alespoň jeden hamiltonovský cyklus a hrany jiné než xy v tomto cyklu musí vytvořit hamiltonovskou cestu v 1 v 2 ... v n v H s x = v 1 a y = v n . Pro každý index i v rozsahu 2 ≤ i ≤ n uvažujme dvě možné hrany v H od v 1 do v i a od v i − 1 do v n . V H může být přítomna maximálně jedna z těchto hran , protože jinak by byl cyklus v 1 v 2 ... v i − 1 v n v n − 1 ... v i v 1 hamiltonovský. Celkový počet hran dopadajících na v 1 nebo v n tedy nepřesahuje počet možných i , který se rovná n − 1 . Proto H nesplňuje podmínku (*), která vyžaduje, aby celkový počet hran ( deg v 1 + deg v n ) byl větší nebo roven n . Protože stupně vrcholů G nepřesahují stupně v H , pak G také nesplňuje požadavek (*).
Palmer [1] popisuje následující jednoduchý algoritmus pro konstrukci hamiltonovského cyklu v grafu, který splňuje podmínku Rudy.
Každý krok zvyšuje počet po sobě jdoucích sousedních párů o jeden nebo dva páry (v závislosti na tom, zda vj a vj + 1 již sousedí ), takže vnější smyčka algoritmu může běžet maximálně nkrát , než se zlomí, kde n je počet vrcholů tohoto grafu. Z důvodů podobných těm, které jsou uvedeny v důkazu věty, musí index j existovat, jinak mají nesousedící vrcholy v i a v i + 1 příliš malý celkový stupeň. Hledání i a j s následnou inverzí části smyčky lze provést v čase O( n ). Celková doba běhu algoritmu je tedy O( n 2 ).
Oreův teorém je zobecněním Diracovy věty , která říká, že pokud má každý vrchol stupeň alespoň n /2 , pak je graf hamiltonovský. Je jasné, že pokud graf splní Diracovu podmínku, bude součet stupňů dvojic vrcholů alespoň n .
Oreův teorém byl zobecněn na Bondiho-Chwatalův teorém . Uzavření grafu můžete definovat přidáním hrany spojující tyto vrcholy pro každou dvojici nesousedících vrcholů se součtem alespoň n . Pokud graf splňuje podmínku Oreovy věty, je jeho uzavřením úplný graf . Bondy-Chwatalova věta říká, že graf je hamiltonovský právě tehdy, když jeho uzávěr je hamiltonovský graf. Protože celý graf je hamiltonovský, Oreova věta z této věty okamžitě vyplývá jako důsledek.
Woodall [2] našel verzi Oreovy věty, která platí pro orientované grafy . Předpokládejme, že digraf G má tu vlastnost, že pro libovolné dva vrcholy u a v existuje buď oblouk od u do v , nebo vnější stupeň u plus stupeň v je alespoň tolik jako počet vrcholů v G . Potom podle Woodallovy věty G obsahuje orientovaný hamiltonovský cyklus. Oreův teorém lze odvodit z Woodallovy věty nahrazením každé hrany dvojicí směrovaných oblouků. Úzce související Meinelova věta [3] říká, že silně propojený n -vrcholový digraf s vlastností, že pro všechny nesousedící vrcholy uav je celkový počet hran incidentních s u nebo v alespoň 2n − 1, musí být hamiltonovský.
Oreova věta může být posílena zadáním přísnějšího požadavku, než je hamiltonovský, jako důsledek podmínky pro vrcholové stupně ve větě. Zejména každý graf, který splňuje podmínky Oreovy věty, je buď pravidelný úplný bipartitní graf nebo pancyklický graf [4] .