XKCD: Hamiltoniano

LEGANERD 040183

Il problema con la formulazione hamiltoniana è che è bidirezionale.

L’algoritmo di routing è alla base dei protocolli di instradamento nelle reti di calcolatori. Queste sono generalizzabili come grafi -dei quali avevamo accennato qualcosa nella prima puntata di questa rubrica- e quindi gli algoritmi che gestiscono l’instradamento dei pacchetti di dati (ovvero la spedizione dei byte da un computer all’altro lungo un percorso) sono di solito derivati tramite la teoria dei grafi.
Si parla di cammino hamiltoniano quando si trova un percorso che passi per tutti i vertici una e una sola volta, se questo percorso è chiuso, ovvero se inizia e finisce dallo stesso nodo, si dice che esso è un ‘ciclo hamiltoniano’.

Vignetta originale su XKCD.