Lintasan dan Sirkuit Hamilton

Lintasan  dan  Sirkuit Hamilton

·       Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.

·  

     Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

·       Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.

 

Contoh.

Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1

        Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3

Sirkuit Euler pada graf (c)    : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1

Sirkuit Euler pada graf (d)    : a, c, f,  e, c, b, d, e, a, d, f, b, a

Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler