Ore tétele a gráfelmélet eredménye , amelyet 1960-ban Oistin Ore norvég matematikus bizonyított . A tétel elegendő feltételt ad ahhoz, hogy egy gráf Hamilton -féle legyen , lényegében kimondva, hogy egy "elég nagy számú élű" gráfnak tartalmaznia kell egy Hamilton-ciklust . A tétel különösen a nem szomszédos csúcsok párjainak fokozatainak összegét veszi figyelembe – ha minden ilyen pár összeadja legalább a gráf csúcsainak teljes számát, akkor a gráf Hamilton-féle.
Legyen G egy (véges és egyszerű) gráf, amelynek n ≥ 3 csúcsa van. Jelölje deg v -vel a v fokát G - ben, azaz a v - re eső élek számát . Ore tétele kimondja, hogy ha
deg v + deg w ≥ n a G gráf nem szomszédos v és w csúcsainak bármely párjára , (*)akkor G hamiltoni . _
Az állítás egyenértékű azzal, hogy bármely nem Hamilton-gráf G megsérti a (*) feltételt. Legyen G egy nem Hamilton-gráf, amelynek n ≥ 3 csúcsa van. Legyen a H gráf G - ből olyan élek egyenkénti hozzáadásával, amelyek nem alkotnak Hamilton-ciklust, miközben lehetséges ilyen élek összeadása. Tekintsük a H gráf bármely két nem szomszédos x és y csúcsát . Ha hozzáadunk egy xy élt H -hez, akkor legalább egy Hamilton-ciklust hozunk létre, és a ciklusban lévő xy - tól eltérő éleknek v 1 v 2 ... v n Hamilton - pályát kell alkotniuk H -ben, ahol x = v 1 és y = v n . Minden i indexhez a 2 ≤ i ≤ n tartományban vegyünk két lehetséges élt H - ban v 1 -től v i -ig és v i - 1 -től v n -ig . Ezen élek közül legfeljebb egy lehet jelen H -ban, mert különben a v 1 v 2 ... v i − 1 v n v n − 1 ... v i v 1 ciklus Hamilton-féle lenne. Így a v 1 -re vagy v n -re eső élek teljes száma nem haladja meg a lehetséges i számát , amely egyenlő n − 1 -gyel . Ezért H nem teljesíti a (*) feltételt, amely megköveteli, hogy az élek teljes száma ( deg v 1 + deg v n ) legyen nagyobb vagy egyenlő, mint n . Mivel G csúcsainak fokai nem haladják meg a H -beli fokokat , ezért G sem felel meg a (*) követelménynek.
Palmer [1] a következő egyszerű algoritmust írja le egy Hamilton-ciklus felépítésére olyan gráfban, amely kielégíti az Ore feltételt.
Minden lépés egy vagy két párral növeli az egymást követő szomszédos párok számát (attól függően, hogy v j és v j + 1 már szomszédos-e), így az algoritmus külső ciklusa maximum n -szer futhat le, mielőtt megszakadna, ahol n ennek a gráfnak a számcsúcsai. A tételbizonyításban megadottakhoz hasonló okokból a j indexnek léteznie kell, különben a nem szomszédos v i és v i + 1 csúcsok összesített foka túl kicsi. Az i és j keresése a hurok egy részének ezt követő megfordításával O( n ) idő alatt elvégezhető. Így az algoritmus teljes futási ideje O( n 2 ).
Az Ore-tétel a Dirac -tétel általánosítása , amely kimondja, hogy ha minden csúcsnak legalább n /2 foka van , akkor a gráf Hamilton-féle. Nyilvánvaló, hogy ha a gráf teljesíti a Dirac-feltételt, akkor a csúcspárok fokszámainak összege legalább n lesz .
Az Ore-tételt viszont a Bondy-Chwatala tételre általánosították . A gráflezárást úgy határozhatja meg, hogy minden legalább n összegű nem szomszédos csúcspárhoz hozzáad egy élt, amely összeköti ezeket a csúcsokat. Ha egy gráf teljesíti az Ore-tétel feltételét, akkor a bezárása egy teljes gráf . A Bondy-Chwatal tétel kimondja, hogy egy gráf akkor és csak akkor Hamilton-gráf, ha a lezárása egy Hamilton-gráf. Mivel a teljes gráf Hamilton-féle, ebből a tételből közvetlenül következik az Ore-tétel, mint következmény.
Woodall [2] megtalálta Ore tételének egy olyan változatát, amely az irányított gráfokra vonatkozik . Tegyük fel, hogy egy G digráfnak megvan az a tulajdonsága, hogy bármely két u és v csúcsra vagy létezik u -tól v -ig ívelt ív , vagy u külső foka plusz v bemeneti foka legalább annyi, mint ahány csúcs G . Ekkor Woodall tétele szerint G tartalmaz egy orientált Hamilton-ciklust. Az Ore tétele levezethető Woodall tételéből, ha minden élt egy pár irányított ívre cserélünk. Egy szorosan összefüggő Meinel-tétel [3] kimondja, hogy egy erősen összefüggő n -csúcs digráfnak azzal a tulajdonsággal, hogy bármely nem szomszédos u és v csúcs esetén az u -ra vagy v - re eső összes élek száma legalább 2n − 1, Hamilton-félenek kell lennie.
Az Érc tétele megerősíthető, ha a tételben szereplő csúcsfokok feltételéből adunk szigorúbb követelményt, mint a Hamilton-féle. Konkrétan minden gráf, amely teljesíti az Ore-tétel feltételeit, vagy szabályos teljes kétrészes gráf , vagy panciklikus gráf [4] .