Teoria dei grafi , grafo hamiltoniano

[fire7777777]

salve ragazzi ho un dubbio riguardo a questi grafi, se per i grafi euleriani so che lo sono perchè il grado dei nodi è sempre pari, per gli hamiltoniani como posso saperlo che lo sono? ho studiato Ora e Dirak ma non ho capito se quando si verificano i loro enunciati il grafo semrpe è hamiltoniano perchè se sono leggi che a volte si compiono e a volte no indipendentemente se il grafo è hamiltoniano allora a che cosa servono?

un caro saluto e visto che posto a pasqua un augurio di buona pasqua a tutti

[onlyReferee]

Ciao fire7777777
I teoremi di Ora e Dirak forniscono condizioni sufficienti ma non necessarie affinché un grafo sia hamiltoniano. Questo significa che possono tranquillamente esistere grafi che non rispettano tali condizioni ma sono ugualmente hamiltoniani. I teoremi ci assicurano semplicemente che al verificarsi di tali condizioni siamo sicuri di avere un grafo hamiltoniano. Per questo motivo si possono trovare normalissimi esempi di grafi hamiltoniani che non rispettano le condizioni presenti nei teoremi. Uno di questi, molto semplice, è un grafo con tre vertici, due dei quali hanno grado uno ed il terzo grado due.
Diverso è invece il teorema seguente, il quale fornisce una condizione necessaria e sufficiente per affermare che un dato grafo è hamiltoniano: "un grafo completo¹ con almeno tre vertici è hamiltoniano".
Spero di esserti stato d'aiuto.

---

Note

1. Grafo completo: un grafo si dice completo se è presente un arco tra ogni coppia di vertici ↑

[Martino]

Diverso è invece il teorema seguente, il quale fornisce una condizione necessaria e sufficiente per affermare che un dato grafo è hamiltoniano: "un grafo completo con almeno tre vertici è hamiltoniano".

Necessaria? Vuoi dire che ogni grafo hamiltoniano è completo? Questo non è vero.

[onlyReferee]

No, vuol dire, come c'è scritto nel teorema, che se un grafo è completo ed ha almeno tre vertici allora è hamiltoniano. E' diverso...

[Martino]

Sì ma tu hai scritto "condizione necessaria e sufficiente"

[onlyReferee]

http://it.wikipedia.org/wiki/Cammino_hamiltoniano

[Martino]

Esiste inoltre un teorema che fornisce una condizione necessaria e sufficiente per una classe di grafi: i grafi completi con almeno tre vertici.

Questa frase su wikipedia è molto ambigua e andrebbe rimossa. Confronta con la versione inglese.