Teorema di Ore

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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.

Enunciato[modifica | modifica wikitesto]

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.

Dimostrazione[modifica | modifica wikitesto]

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 .

Corollari[modifica | modifica wikitesto]

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.

Bibliografia[modifica | modifica wikitesto]