Ores sætning er et resultat i grafteori , bevist i 1960 af den norske matematiker Oistin Ore . Sætningen giver en tilstrækkelig betingelse for, at en graf kan være Hamiltonsk , i det væsentlige angiver, at en graf med "et tilstrækkeligt stort antal kanter" skal indeholde en Hamiltonsk cyklus . Især betragter sætningen summen af grader af par af ikke-tilstødende hjørner - hvis hvert sådant par summeres til mindst det samlede antal hjørner i en graf, så er grafen Hamiltonsk.
Lad G være en (endelig og enkel) graf med n ≥ 3 hjørner. Betegn med deg v graden af v i G , det vil sige antallet af kanter , der falder ind på v . Ore's sætning siger, at hvis
grader v + grader w ≥ n for ethvert par af ikke-tilstødende hjørner v og w på grafen G , (*)så er G Hamiltonsk .
Påstanden svarer til at sige, at enhver ikke-hamiltonsk graf G overtræder betingelse (*). Lad G være en ikke-hamiltonsk graf med n ≥ 3 hjørner. Lad grafen H dannes ud fra G ved at tilføje kanter, én efter én, der ikke danner en Hamiltonsk cyklus, mens det er muligt at tilføje sådanne kanter. Betragt hvilke som helst to ikke-tilstødende hjørner x og y på grafen H . Tilføjelse af en kant xy til H skaber mindst én Hamiltonsk cyklus, og andre kanter end xy i den cyklus skal danne en Hamiltonsk bane v 1 v 2 ... v n i H med x = v 1 og y = v n . For hvert indeks i i området 2 ≤ i ≤ n skal du overveje to mulige kanter i H fra v 1 til v i og fra v i − 1 til v n . Højst en af disse kanter kan være til stede i H , for ellers ville cyklussen v 1 v 2 ... v i − 1 v n v n − 1 ... v i v 1 være Hamiltonsk. Det samlede antal kanter, der falder ind på v 1 eller v n , overstiger således ikke antallet af mulige i , som er lig med n − 1 . Derfor opfylder H ikke betingelsen (*), som kræver, at det samlede antal kanter ( deg v 1 + deg v n ) er større end eller lig med n . Da graderne af toppunkterne i G ikke overstiger graderne i H , så opfylder G heller ikke kravet (*).
Palmer [1] beskriver følgende simple algoritme til at konstruere en Hamiltonsk cyklus i en graf, der opfylder Ore-betingelsen.
Hvert trin øger antallet af på hinanden følgende tilstødende par med et eller to par (afhængigt af om v j og v j + 1 allerede er nabostillede), således at algoritmens ydre sløjfe maksimalt kan køre n gange før den går i stykker, hvor n er antallet af toppunkter på denne graf. Af årsager svarende til dem, der er givet i beviset for sætningen, skal indekset j eksistere, ellers har de ikke-tilstødende hjørner v i og v i + 1 for lille en samlet grad. Søgningen efter i og j med efterfølgende inversion af en del af løkken kan udføres på O( n ) tid. Algoritmens samlede køretid er således O( n 2 ).
Ore's sætning er en generalisering af Dirac 's sætning , som siger, at hvis hvert toppunkt har grad mindst n /2 , så er grafen Hamiltonsk. Det er klart, at hvis grafen opfylder Dirac-betingelsen, vil summen af graderne af par af hjørner være mindst n .
Til gengæld er Ores teorem blevet generaliseret til Bondi-Chwatala-sætningen . Du kan definere en graflukning ved at tilføje, for hvert par af ikke-tilstødende hjørner med en sumgrad på mindst n , en kant, der forbinder disse knudepunkter. Hvis en graf opfylder betingelsen for Ores sætning, er dens lukning en komplet graf . Bondy-Chwatal-sætningen siger, at en graf er Hamiltonsk, hvis og kun hvis dens lukning er en Hamiltonsk graf. Da hele grafen er Hamiltonsk, følger Ores sætning umiddelbart af denne sætning som en konsekvens.
Woodall [2] fandt en version af Ores sætning, der gælder for rettede grafer . Antag, at en digraf G har den egenskab, at der for to vilkårlige spidser u og v enten eksisterer en bue fra u til v , eller at ud-graden af u plus in-graden af v er mindst lige så mange som antallet af spidser i G . Derefter, ved Woodalls sætning, indeholder G en orienteret Hamilton-cyklus. Ores sætning kan udledes af Woodalls sætning ved at erstatte hver kant med et par rettede buer. En nært beslægtet Meinel-sætning [3] siger, at en stærkt forbundet n -vertex- digraf med den egenskab, at for alle ikke-tilstødende hjørner u og v skal det samlede antal kanter, der falder ind på u eller v , være mindst 2n − 1, skal være Hamiltonsk.
Ores sætning kan styrkes ved at stille et strengere krav end at være Hamiltonsk, som en konsekvens af betingelsen for toppunktsgrader i sætningen. Især enhver graf, der opfylder betingelserne i Ores sætning, er enten en regulær komplet todelt graf eller en pancyklisk graf [4] .