Ores teorem är ett resultat inom grafteorin , bevisat 1960 av den norske matematikern Oistin Ore . Satsen ger ett tillräckligt villkor för att en graf ska vara Hamiltonsk , i huvudsak anger att en graf med "ett tillräckligt stort antal kanter" måste innehålla en Hamiltonsk cykel . Särskilt betraktar satsen summan av grader av par av icke-angränsande hörn - om varje sådant par summerar till åtminstone det totala antalet hörn i en graf, då är grafen Hamiltonian.
Låt G vara en (ändlig och enkel) graf med n ≥ 3 hörn. Beteckna med deg v graden av v i G , det vill säga antalet kanter som faller in på v . Ores teorem säger att om
deg v + deg w ≥ n för vilket par som helst av icke intilliggande hörn v och w i grafen G , (*)då är G Hamiltonian .
Påståendet motsvarar att säga att alla icke-hamiltonska grafer G bryter mot villkor (*). Låt G vara en icke-hamiltonsk graf med n ≥ 3 hörn. Låt grafen H bildas av G genom att lägga till kanter, en efter en, som inte bildar en Hamiltonsk cykel, medan det är möjligt att lägga till sådana kanter. Betrakta vilka två icke närliggande hörn x och y i grafen H . Att lägga till en kant xy till H skapar minst en Hamiltonsk cykel, och andra kanter än xy i den cykeln måste bilda en Hamiltonsk bana v 1 v 2 ... v n i H med x = v 1 och y = v n . För varje index i i intervallet 2 ≤ i ≤ n , betrakta två möjliga kanter i H från v 1 till v i och från v i− 1 till v n . Som mest kan en av dessa kanter förekomma i H , för annars skulle cykeln v 1 v 2 ... v i − 1 v n v n − 1 ... v i v 1 vara Hamiltonsk. Det totala antalet kanter som faller in på v 1 eller v n överstiger alltså inte antalet möjliga i , vilket är lika med n − 1 . Därför uppfyller H inte villkoret (*), vilket kräver att det totala antalet kanter ( deg v 1 + deg v n ) är större än eller lika med n . Eftersom graderna på G - punkten inte överstiger graderna i H , så uppfyller G inte heller kravet (*).
Palmer [1] beskriver följande enkla algoritm för att konstruera en Hamiltonsk cykel i en graf som uppfyller malmvillkoret.
Varje steg ökar antalet på varandra följande angränsande par med ett eller två par (beroende på om v j och v j + 1 redan är intilliggande), så att den yttre slingan av algoritmen kan köras maximalt n gånger innan den går sönder, där n är antalet hörn i denna graf. Av skäl som liknar de som ges i beviset för satsen måste index j existera, annars har de icke intilliggande hörnen v i och v i + 1 för liten totalgrad. Sökningen efter i och j med efterföljande invertering av en del av slingan kan göras på O( n ) tid. Således är den totala körtiden för algoritmen O( n2 ) .
Ores sats är en generalisering av Diracs sats , som säger att om varje vertex har graden minst n /2 , så är grafen Hamiltonsk. Det är tydligt att om grafen uppfyller Dirac-villkoret kommer summan av graderna av hörnpar att vara minst n .
I sin tur har Ores teorem generaliserats till Bondy-Chwatala-satsen . Du kan definiera en grafstängning genom att lägga till, för varje par av icke-angränsande hörn med en summagrad på minst n , en kant som förbinder dessa hörn. Om en graf uppfyller villkoret för Ores sats, är dess stängning en komplett graf . Bondy-Chwatals sats säger att en graf är Hamiltonsk om och endast om dess stängning är en Hamiltonsk graf. Eftersom hela grafen är Hamiltonsk, följer Ores sats omedelbart från denna sats som en följd.
Woodall [2] hittade en version av Ores teorem som gäller riktade grafer . Antag att en digraf G har egenskapen att det för två valfria hörn u och v antingen finns en båge från u till v , eller att utgraden av u plus in-graden av v är minst lika många som antalet hörn i G . Sedan, enligt Woodalls teorem, innehåller G en orienterad Hamiltonsk cykel. Ores sats kan härledas från Woodalls sats genom att ersätta varje kant med ett par riktade bågar. En nära besläktad Meinel-sats [3] säger att en starkt sammankopplad n -vertex-digraf med egenskapen att för alla icke-angränsande hörn u och v det totala antalet kanter som faller in på u eller v är minst 2n − 1 måste vara Hamiltonska.
Ores sats kan förstärkas genom att ställa ett strängare krav än att vara Hamiltonian, som en konsekvens av villkoret för vertexgrader i satsen. I synnerhet är varje graf som uppfyller villkoren för Ores sats antingen en vanlig komplett tvådelad graf eller en pancyklisk graf [4] .