Teorema di Ore

Il teorema di Ore è un teorema della teoria dei grafi provato nel 1960 dal matematico Norvegese Øystein Ore. Fornisce una condizione sufficiente, ma non necessaria, affinché un grafo sia Hamiltoniano, affermando che un grafo che contiene un sufficiente numero di archi, comparati al numero di vertici, deve contenere un ciclo Hamiltoniano. Esso è inoltre una generalizzazione del teorema di Dirac e a sua volta viene generalizzato dal teorema di Bondy-Chvátal.

EnunciatoModifica

Sia   un grafo semplice con un numero finito di vertici  . Sia   il grado del vertice  , ossia il numero di archi incidenti su  . Allora il teorema di Ore stabilisce che, presi due vertici   e   non adiacenti, se vale   allora   è Hamiltoniano.

DimostrazioneModifica

Usando il teorema di Bondy-Chvátal, la dimostrazione è immediata.

Una possibile dimostrazione diretta è invece la seguente:

Basterà dimostrare che se il grafo non è Hamiltoniano allora la condizione data dal teorema di Ore viene violata. Sia quindi   un grafo privo di cicli hamiltoniani e sia   il grafo ottenuto da   aggiungendo archi fin quando l'aggiunta di un altro arco produrrebbe un ciclo hamiltoniano. Poiché l'aggiunta di un solo arco creerebbe un ciclo hamiltoniano allora necessariamente   possiede un cammino hamiltoniano  , dove gli  vertici sono stati ordinati in modo tale che l'arco la cui aggiunta creerebbe il ciclo sia  , che risultano essere quindi due vertici non adiacenti sia in   che in   . Per ogni   consideriamo l'arco  . Se questo arco esiste, ossia se   fa parte dell'insieme dei vicini di  , allora necessariamente non deve esistere l'arco   poiché tale arco produrrebbe un ciclo hamiltoniano in   che per ipotesi ne è privo. Infatti un possibile ciclo sarebbe  . In conclusione solo uno degli archi  ,   può esistere. Essendo le possibili scelte di   pari a   e per ogni   possiamo aggiungere (al più)   ai vicini di   escludendo però   ai vicini di   e viceversa, abbiamo che necessariamente  . Dunque non viene soddisfatta la condizione posta dal teorema di Ore. Poiché il grado dei vertici in   è minore o al più uguale a quello di  , la condizione del teorema di Ore non viene soddisfatta nemmeno in  .

CorollariModifica

Un corollario del teorema di Ore è il teorema di Dirac che afferma che se per ogni vertice   di un grafo   di   vertici, vale   allora   possiede un ciclo hamiltoniano. È immediato vedere che se vale tale relazione per ogni vertice essa vale anche per due vertici   e   non adiacenti e in particolare si ha  . La condizione di Ore è quindi soddisfatta.

BibliografiaModifica