Lintasan dan sirkuit Hamilton

• Lintasan Hamilton ialah lintasan yang melalui tiap simpul didalam graf tepat satu kali

• Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul didalam graf tepat satu kali, kecuali simpul awal (juga mrpk simpul akhir) dilalui 2 kali
• Graf yang memiliki sirkuit Hamilton disebut graf Hamilton , sedangkan graf yang memiliki lintasan Hamilton disebut graf semi Hamilton

Contoh :

Graf Di samping memiliki lintasan Hamilton dengan lintasan :

b,c,d,e,f,g,a,b

dan Graf di samping juga memiliki sirkuit Hamilton karena di awali di simpul b dan berakhir di simpul b








Graf disamping memiliki lintasan Hamilton dengan lintasan :

a,b,c,d,e,i,f,g,h

Tapii graf disamping tidak memiliki sirkuit Hamilton.











Teorema Untuk Lintasan dan Sirkuit Hamilton

• Syarat cukup (bukan syarat perlu) supaya graf sederhana G dengan n buah simpul (n>=3) adalah graf Hamilton ialah jika derajad tiap simpul paling sedikit n/2
• Setiap graf lengkap adalah graf Hamilton
• Dalam graf l engkap dengan n buah simpul (n>=3) terdapat (n-1)! /2 buah sirkuit Hamilton
• Dalam graf lengkap G dengan jumlah simpul n>=3 dan n ganjil , terdapat (n-1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n>=4 , maka dalam G terdapat (n-2)/2 buah sirkuit Hamilton