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.

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

-    Graph yang memiliki sirkuit Hamilton dinamakan graph Hamilton, sedangkan graph yang hanya memiliki lintasan Hamilton disebut graph semi-Hamilton.

Contoh: 
 
              (a)                              (b)                             (c
 a.       Graph yang memiliki lintasan Hamilton (3, 2, 1, 4)
 b.      Graph yang memiliki sirkuit Hamilton (1, 2, 3, 4, 1)
 c.       Graph yang tidak memiliki lintasan maupun sirkuit Hamilton

C.     TEOREMA

-        Setiap graph lengkap adalah Graph Hamilton.

-       Di dalam graph lengkap G dengan n buah simpul (n ≥ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.

-    Jika G graph simple terhubung dengan vertex sebanyak n, dimana n ≥ 3, maka G mempunyai sirkuit Hamilton jika derajat setiap vertex paling sedikit n/2

-    Syarat cukup (jadi bukan syarat perlu) supaya graph sederhana G dengan (n ≥ 3) buah simpul adalah graph Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) ≥ n/2 untuk setiap simpul v di  G).

- Di dalam graph lengkap G dengan n buah 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 di dalam G terdapat (n - 2)/2 buah sirkuit Hamilton yang saling lepas.