RESUME TEORI GRAF

GRAF EULER DAN GRAF HAMILTON

OLEH:

NUR WAHIDAH ABDURRAUF

(H12113034)

JURUSAN MATEMATIKA

PRODI STATISTIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS HASANUDDIN

2015

A. Eulerian Graf

Graf yang memuat sirkuit euler.

Lintasan euler

Lintasan pada graf G dikatakan lintasan euler, ketika melalui setiap sisi di graf tepat

satu kali. Karena melalui setiap sisi tepat satu kali atau melalui sisi yang berlainan,

bisa dikatakan jejak euler. Sehingga lintasan euler sudah tentu jejak euler.

Sirkuit euler

Lintasan euler adalah simpul awal = simpul akhir/lintasan euler (tertutup) yang

merupakan sirkuit berarti sirkuit euler. Sehingga suatu graf yang memiliki sirkuit

euler atau berarti graf tersebut merupakan graf euler.

Teorema 1

Graf terhubung G adalah euler jika dan hanya jika derajat dari masing-masing vertex

adalah genap.

Teorema 2

a. Jika graf G memiliki lebih dari dua vertex berderajat ganjil, maka G adalah

graf non euler.

b. Jika G memiliki dua vertex berderajat ganjil, maka G memiliki lintasan euler

dan ini berlaku juga ketika memiliki satu vertex berderajat ganjil.

Teorema 3

Suatu graf terhubung adalah graf semi euler jika dan hanya jika memiliki tepat dua

vertex yang berderajat ganjil.

Teorema 4

Graf berarah G memiliki sirkuit euler jika dan hanya jika G terhubung dan setiap

simpul memiliki derajat masuk dan derajat keluar sama. G memiliki lintasan euler

jika dan hanya jika G terhubung dan setiap simpul memiliki derajat masuk dan

derajat keluar sama kecuali dua simpul, yang pertama memiliki derajat keluar satu

lebih besar dari derajat masuk, dan yang kedua memiliki derajat masuk lebih besar

dari derajat keluar.

A

BC

G F

H

DE

(i)

D C

BA

(ii)

C

A

D

B

(iii)

(i) Graf berarah euler

(ii) Graf berarah semi euler

(iii) Graf berarah bukan euler & semi euler

Jadi, dikatakan graf G memiliki sitkuit euler, ada beberapa poin yang harus

diperhatikan :

1. Jika ada vertex yang berderajat nol, maka graf adalah graf tak terhubung dan

tidak memiliki lintasan euler dan sirkuit euler.

2. Jika semua vertex memiliki derajat genap, maka memiliki lintasan euler dan

sirkuit euler.

3. Jika terdapat dua vertex yang memiliki derajat ganjil, maka memiliki lintasan

euler dan tidak memiliki sirkuit euler.

4. Jika terdapat lebih dari dua vertex yang memiliki derajat ganjil, maka tidak

memiliki lintasan euler dan sirkuit euler.

Graf yang hanya memiliki lintasan euler (terbuka) merupakan graf semi euler.

Graf yang tidak memiliki lintasan euler dan sirkuit euler merupakan graf non euler.

Fleury’s algoritm

Menggunakan fleury algoritm untuk mengkontruksi sirkuit euler.

Langkah 1 : pilihlah sebuah simpul sebagai simpul awal, misalnya simpul a.

Langkah 2 : laluilah sebuah sisi yang dapat ditelusuri. Pilihlah sebuah jembatan jika

tidak ada sisi lain sebagai alternatif yang dapat dilewati.

Langkah 3 : setelah melewati setiap sisi tepat satu kali, hapuslah sisi tersebut, hapus

pula simpul yang berderajat nol yang muncul akibat penghapusan sisi

tersebut. Kemudian lewatilah sisi lain yang masih tersedia.

Langkah 4 : stop jika tidak ada sisi lagi. Kalau masih ada sisi yang bisa dilewati,

kembalilah ke langkah 2.

A

B C

D(i)

A

B C

D(ii) (iii)

A

B C

D

Contoh graf untuk fleury’s algoritm.

B. Hamiltonian Graf

Graf hamilton diambil dari nama sir william rowan hamilton.

Sirkuit hamilton

Lintasan Hamilton suatu graf merupakan lintasan yang melalui setiap simpul dalam

graf tersebut tepat satu kali. Jika lintasan tersebut kembali kesimpul awal, sehingga

membentuk lintasan tertutup (sirkuit) maka lintasan ini dinamakan sirkuit Hamilton.

Lintasan hamilton

Lintasan hamilton adalah lintasan yang melalui tiap vertex di dalam graf tepat satu

kali.

Dengan demikian, sirkuit Hamilton merupakan sirkuit yang melewati masing-masing

sisi tepat satu kali. Graf yang memuat sirkuit Hamilton dinamakan graf Hamilton

(Hamiltonian graph), sedangkan graf yang memuat lintasan Hamilton dinamakan

graf semi Hamilton (semi- Hamiltonian graph).

(i) Graf yang memiliki lintasan hamilton (misalnya ABCD)

(ii) Graf yang memiliki sirkuit hamilton (misalnya DCBA)

(iii) Graf yang tidak memiliki lintasan maupun sirkuit hamilton

Misalkan G merupakan graf sederhana dengan jumlah simpulnya adalah n buah

(dimana n paling sedikit tiga buah). Jika derajat setiap simpulnya paling sedikit n/2

simpul maka graf G tersebut merupakan graf Hamilton.

Teorema 1

Syarat cukup (jadi bukan syarat perlu) supaya graf sederhana G dengan n≥ 3 buah

vertex adalah graf hamilton ialah bila tiap vertex paling sedikit n2

(yaitu, d (v)≥n2

untuk setiap simpul v di G).

Teorema 2

Setiap graf lengkap adalah graf hamilton.

Ingat : graf lengkap dengan n buah simpul dilabangkan dengan Kn. Jumlah sisi pada

graf lengkap yang terdiri dari n buah simpul adalah n(n−1)

2.

Teorema 3

Di dalam graf lengkap G dengan n buah vertex (n≥ 3), terdapat (n−1 ) !

2 buah sirkuit

hamilton.

Teorema 4

Di dalam graf 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−1 )

2 buah sirkuit hamilton yang saling lepas.

Teorema 5

Misalkan G adalah graf terhubung sederhana dengan n titik, dengan n ≥3 dan

deg v+deg w ≥n. Untuk tiap-tiap pasangan titik yang tidak berdekatan v dan w, maka

G adalah graf hamilton.

Teorema 6

Misalkan G adalah graf sederhana dengan n vertex. Jika jumlah dari derajat masing-

masing vertex di G paling sedikit n – 1, maka ada lintasan hamilton di G.

Perbedaan Sirkuit Euler dengan Sirkuit Hamilton :

5

2

4 3

6

1

(a)

3

5

1 2

4

(b)

1. Dalam Sirkuit Euler semua garis harus dilalui tepat satu kali, sedangkan

semua titiknya boleh dikunjungi lebih dari sekali.

2. Dalam Sirkuit Hamilton semua titiknya harus dikunjungi tepat satu kali dan

tidak harus melalui semua garis.

3. Dalam sirkuit Euler, yang dipentingkan adalah garisnya. Sebaliknya dalam

sirkuit Hamilton, yang dipentingkan adalah kunjungan pada titiknya.

Lintasan dan Sirkuit Hamilton/Euler

Beberapa graf dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus,

mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, mengandung

sirkuit Euler dan lintasan Hamilton, mengandung lintsan Euler maupun lintasan

Hamilton, tidak mengandung lintasan Euler namun mengandung sirkuit Hamilton,

dan sebagainya.

(a) mengandung sirkuit Hamilton maunpun sirkuit Euler,

(b) mengandung sirkuit Hamilton dan lintasan Euler.

REFERENSI

Ayu. 2013. Sirkuit Euler & Sirkuit Hamilton. Universitas Gunadarma

Tiarindarto. 2012. Eulerian-Graf-Hamiltonian-Graf. UHAMKA.

Wijaya, Adi. 2009. Matematika Diskrit. Bandung: POLITEKNIK TELKOM.