GRAPH HAMILTON

A.    PENGERTIAN

Definisi:

Misalkan G adalah sebuah Graph, sebuah sikel di G yang memuat semua titik di G disebut SIKEL HAMILTON, Jika G memuat semua sikel Hamilton maka G disebut GRAPH HAMILTON

Contoh:

   

Graph Hamilton              Bukan Graph Hamilton

Pada graph G terdapat sikel hamilton yaitu sikel (V₁,V₂,V₃,V₄,V₅,V₁).  Jadi Graph G adalah GRAPH HAMILTON

Sedangkan

Pada Graph H, Kita tidak bisa  membuat sikel yang memuat titik di Graph H.  Jadi Graph H BUKAN GRAPH HAMILTON    

GRAPH  MAKSIMAL NON  HAMILTON

Graph sederhana G disebut graph maksimal non hamilton jika G non hamilton dan penambahan sebuah sisi sebarang yang menghubungkan 2 titik yang tidak berhubungan langsung di G menghasilkan graph baru yang Hamilton.

B.    LINTASAN DAN SIRKUIT HAMILTON

-       Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graph tepat satu kali.