Cominciamo col numerare i vertici in modo da capire di quale foro si parla, così otteniamo la Figura 1, poi ridisegniamo tale figura in modo da ricavarne il grafo planare della Figura 2.
- Starburst.png (32.78 KiB) Visto 44731 volte
Da essa troviamo facilmente tutti i cammini chiusi (detti anche CIRCUITI, o CICLI):
A = (2,7) (7,3) (3,5) (5,2)
B = (2,7) (7,3) (3,6) (6,1) (1,4) (4,8) (8,2)
C = (2,5) (5,3) (3,7) (7,2)
D = (2,5) (5,3) (3,6) (6,1) (1,4) (4,8) (8,2)
E = (3,5) (5,2) (2,7) (7,3)
F = (3,5) (5,2) (2,8) (8,4) (4,1) (1,6) (6,3)
G = (3,7) (7,2) (2,5) (5,3)
H = (3,7) (7,2) (2,8) (8,4) (4,1) (1,6) (6,3).
Il ciclo F è uguale al ciclo D percorso al contrario.
Il ciclo H è uguale al ciclo B percorso al contrario.
Il grafo non è quasi-hamiltoniano perché se manca uno qualsiasi dei vertici dell'insieme V={1, 2, 3, 4} non esiste un cammino che tocchi i 7 vertici rimanenti.
Diciamo che se un grafo G di n vertici ha un ciclo hamiltoniano che li tocca tutti eliminare un vertice lascerebbe n-1 cammini hamiltoniani, allora G sarebbe quasi-hamiltoniano solo se è anche hamiltoniano.
