Teoria dei grafi , grafo hamiltoniano
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
un caro saluto e visto che posto a pasqua un augurio di buona pasqua a tutti
Risposte
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[nota]Grafo completo: un grafo si dice completo se è presente un arco tra ogni coppia di vertici[/nota] con almeno tre vertici è hamiltoniano".
Spero di esserti stato d'aiuto.
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[nota]Grafo completo: un grafo si dice completo se è presente un arco tra ogni coppia di vertici[/nota] con almeno tre vertici è hamiltoniano".
Spero di esserti stato d'aiuto.
"onlyReferee":Necessaria? Vuoi dire che ogni grafo hamiltoniano è completo? Questo non è vero.
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".
No, vuol dire, come c'è scritto nel teorema, che se un grafo è completo ed ha almeno tre vertici allora è hamiltoniano. E' diverso...
Sì ma tu hai scritto "condizione necessaria e sufficiente"
"wikipedia":Questa frase su wikipedia è molto ambigua e andrebbe rimossa. Confronta con la versione inglese.
Esiste inoltre un teorema che fornisce una condizione necessaria e sufficiente per una classe di grafi: i grafi completi con almeno tre vertici.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo