[BASE Cinque - Appunti di Matematica ricreativa]

Cammini nei grafi

Osservate la figura qui sotto. E' formata da 12 segmenti e 8 vertici (indicati con cerchietti).

figura

Esercizio 1. Sapreste disegnare la figura con un solo tratto di penna, senza mai staccare la penna dal foglio e percorrendo ogni segmento una sola volta?
Una difficoltà in più: ad ogni incrocio dovete cambiare direzione.

Se ci riuscite, avete fatto un cammino euleriano (da Leonard Euler).

Definizione. Un cammino euleriano sopra un grafo è un cammino che passa per tutti i suoi archi una e una volta sola.

Esercizio 2. Sapreste tracciare un percorso, seguendo i lati della figura, che passi per tutti i vertici esattamente una volta? Il percorso non deve necessariamente passare per tutti i lati.

Se ci riuscite, avete fatto un cammino hamiltoniano (da William Hamilton)

Definizione. Un cammino hamiltoniano sopra un grafo è un cammino che tocca tutti i suoi vertici una e una volta sola.