biblio toscana

La Torre di Hanoi (anche conosciuta come Torre di Lucas dal nome del suo inventore) è un rompicapo matematico composto da tre paletti e un certo numero di dischi di grandezza decrescente, che possono essere infilati in uno qualsiasi dei paletti. Il gioco inizia con tutti i dischi incolonnati su un paletto in ordine decrescente, in modo da formare un cono. Lo scopo del gioco è portare tutti i dischi su un paletto diverso, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo.

Un rompicapo è un passatempo che consiste in un problema o un enigma che mette alla prova l'ingegno di chi è chiamato a risolverlo. Esistono numerosi diversi tipi di rompicapo, che richiedono per la soluzione attitudini diverse (per esempio, al ragionamento induttivo o al ragionamento deduttivo). I vari tipi di soluzioni possono richiedere la strutturazione di una forma o la creazione di un determinato ordine. I rompicapo esistono da migliaia di anni; uno dei più antichi e noti è il tangram.

Nel campo matematico della teoria dei grafi, un cammino in un grafo (orientato o non orientato) è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta. Determinare se questo cammino esista è un problema NP-completo. In termini rigorosi, la determinazione di un cammino hamiltoniano è la ricerca di una permutazione ( p 0 , p 1 , . . . , p n − 1 ) {\displaystyle (p_{0},p_{1},...,p_{n-1})} dei nodi tale che ( p i , p i + 1 ) ∈ E {\displaystyle (p_{i},p_{i+1})\in E} per ogni 0 ≤ i ≤ n − 2 {\displaystyle 0\leq \ i\leq \ n-2} dove con E si intende l'insieme di archi del Grafo. Si ha un ciclo hamiltoniano quando in un cammino hamiltoniano esiste un arco che collega l'ultimo vertice con il primo, realizzando così un ciclo che visita tutti i vertici per poi ritornare al punto di partenza. Un grafo che contenga almeno un ciclo hamiltoniano viene detto grafo hamiltoniano. Questi particolari cammini hanno preso il nome da William Rowan Hamilton che inventò un gioco da tavolo, il puzzle di Hamilton o icosian game, che consisteva nel trovare un cammino chiuso sul bordo di un dodecaedro.