Teorema lui Ore este un rezultat în teoria grafurilor , demonstrată în 1960 de matematicianul norvegian Oistin Ore . Teorema oferă o condiție suficientă pentru ca un grafic să fie hamiltonian , afirmând în esență că un grafic cu „un număr suficient de mare de muchii” trebuie să conțină un ciclu hamiltonian . În special, teorema ia în considerare sumele de grade ale perechilor de vârfuri neadiacente - dacă fiecare astfel de pereche adună cel puțin numărul total de vârfuri dintr-un grafic, atunci graficul este hamiltonian.
Fie G un grafic (finit și simplu) cu n ≥ 3 vârfuri. Se notează cu gradul v gradul lui v în G , adică numărul de muchii incidente la v . Teorema lui Ore afirmă că dacă
deg v + deg w ≥ n pentru orice pereche de vârfuri neadiacente v și w ale graficului G , (*)atunci G este hamiltonian .
Afirmația este echivalentă cu a spune că orice graf non-Hamiltonian G încalcă condiția (*). Fie G un graf non-Hamiltonian cu n ≥ 3 vârfuri. Să se formeze graficul H din G prin adăugarea muchiilor, una câte una, care nu formează un ciclu hamiltonian, în timp ce este posibil să se adauge astfel de muchii. Considerăm oricare două vârfuri neadiacente x și y ale graficului H . Adăugarea unei muchii xy la H creează cel puțin un ciclu hamiltonian și alte muchii decât xy în acel ciclu trebuie să formeze o cale hamiltoniană v 1 v 2 ... v n în H cu x = v 1 și y = v n . Pentru fiecare indice i din intervalul 2 ≤ i ≤ n , se consideră două muchii posibile în H de la v 1 la v i și de la v i − 1 la v n . Cel mult una dintre aceste muchii poate fi prezentă în H , deoarece altfel ciclul v 1 v 2 ... v i − 1 v n v n − 1 ... v i v 1 ar fi hamiltonian. Astfel, numărul total de muchii incidente la v 1 sau v n nu depășește numărul de i posibil , care este egal cu n − 1 . Prin urmare, H nu îndeplinește condiția (*), care cere ca numărul total de muchii ( deg v 1 + deg v n ) să fie mai mare sau egal cu n . Deoarece gradele vârfurilor lui G nu depășesc gradele din H , atunci și G nu îndeplinește cerința (*).
Palmer [1] descrie următorul algoritm simplu pentru construirea unui ciclu hamiltonian într-un grafic care satisface condiția Ore.
Fiecare pas crește numărul de perechi adiacente consecutive cu una sau două perechi (în funcție de faptul că v j și v j + 1 sunt deja adiacente), astfel încât bucla exterioară a algoritmului să poată rula de maximum n ori înainte de a se rupe, unde n este numărul de vârfuri ale acestui grafic. Din motive similare celor date în demonstrarea teoremei, indicele j trebuie să existe, altfel vârfurile neadiacente v i și v i + 1 au un grad total prea mic. Căutarea pentru i și j cu inversarea ulterioară a unei părți a buclei se poate face în timp O( n ). Astfel, timpul total de rulare al algoritmului este O( n 2 ).
Teorema lui Ore este o generalizare a teoremei lui Dirac , care afirmă că dacă fiecare vârf are gradul cel puțin n /2 , atunci graficul este hamiltonian. Este clar că dacă graficul satisface condiția Dirac, suma gradelor perechilor de vârfuri va fi cel puțin n .
La rândul său, teorema lui Ore a fost generalizată la teorema Bondi-Chwatala . Puteți defini o închidere de grafic adăugând, pentru fiecare pereche de vârfuri neadiacente cu un grad de sumă de cel puțin n , o muchie care leagă aceste vârfuri. Dacă un grafic satisface condiția teoremei lui Ore, închiderea sa este un grafic complet . Teorema Bondy-Chwatal afirmă că un graf este hamiltonian dacă și numai dacă închiderea lui este un graf hamiltonian. Deoarece graficul complet este hamiltonian, teorema lui Ore decurge imediat din această teoremă ca corolar.
Woodall [2] a găsit o versiune a teoremei lui Ore care se aplică graficelor direcționate . Să presupunem că un digraf G are proprietatea că pentru oricare două vârfuri u și v , fie există un arc de la u la v , fie gradul în afara lui u plus gradul în interior al lui v este cel puțin atât cât numărul de vârfuri din G . Apoi, după teorema lui Woodall, G conține un ciclu hamiltonian orientat. Teorema lui Ore poate fi derivată din teorema lui Woodall prin înlocuirea fiecărei muchii cu o pereche de arce direcționate. O teoremă Meinel strâns înrudită [3] afirmă că un digraf n -vertex puternic conectat cu proprietatea că pentru orice vârfuri neadiacente u și v numărul total de muchii incidente la u sau v este cel puțin 2n − 1 trebuie să fie hamiltonian.
Teorema lui Ore poate fi întărită dând o cerință mai strictă decât a fi hamiltoniană, ca o consecință a condiției pentru gradele de vârf din teoremă. În special, orice graf care îndeplinește condițiile teoremei lui Ore este fie un graf bipartit complet regulat , fie un graf panciclic [4] .