@tiarindarto FKIP UHAMKA (Math_H) 0901125227

EULERIAN GRAF & HAMILTONIAN GRAF

A. Eulerian Graf

Graf yang memuat sirkut 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.1

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.2

Teorema 3

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

vertex yang berderajat ganjil.3

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.4

(i) Graf berarah euler

(ii) Graf berarah semi

euler

(iii) Graf berarah bukan

euler & semi euler

1 C. Vasudev. Graph Theory With Applications. New Delhi: New Age International. hlm 69

2 Ibid. hlm 70

3 Ibid.

4 Politeknik Telkom. Graf. (Dalam Bentuk Slide Power Point). Bandung: Politeknik Telkom. Slide ke 79

@tiarindarto FKIP UHAMKA (Math_H) 0901125227

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.

Contoh 1 :

lintasan euler.

ABCDEFCGA, ABCFEDCGA, dan lainnya.

Lintasan euler merupakan sirkuit berarti

graf euler.

Contoh 2 :

lintasan euler.

ABEDCB, BCDEBA, dan lainnya.

Lintasan euler tidak termasuk sirkuit atau graf tidak memiliki

sirkuit euler. Sehingga graf merupakan graf semi euler.

Contoh 3 :

lintasan euler.

SRQSTQPT, SRQSTPQT, dan lainnya.

Lintasan euler tidak termasuk sirkuit atau graf

tidak memiliki sirkuit euler. Sehingga graf

merupakan graf semi euler.

@tiarindarto FKIP UHAMKA (Math_H) 0901125227

Contoh 4 :

deg(K)=deg(L)=deg(M)=deg(P)=deg(O)=deg(N)=3

berdasarkan teorema 2 dapat dikatakan graf di

samping adalah graf non euler, karena memiliki

vertex berderajat ganjil lebih dari dua.

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.5

Contoh graf untuk fleury’s algoritm.

5 Kartika Yulianti. Hand Out Mata Kuliah Teori Graf (MT 424) Jilid Satu . Bandung: UPI. hlm 11

@tiarindarto FKIP UHAMKA (Math_H) 0901125227

B. Hamiltonian Graf

Graf hamilton diambil dari nama sir william rowan hamilton.

Suatu graf terhubung adalah graf hamilton memuat sirkuit yang melalui setiap vertex

tepat satu kali disebut sirkuit hamilton.

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

kali.

Graf yang hanya memiliki lintasan hamilton disebut graf semi hamilton.

Contoh 1 :

(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

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

(yaitu, d(v)

untuk setiap simpul v di G).

Contoh :

(i) n = 3, dengan tiap vertex memiliki d(v) = 1,5 2

(ii) n = 4, dengan tiap vertex memiliki d(v) = 2

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 ( )

.

Contoh :

dan seterusnya

@tiarindarto FKIP UHAMKA (Math_H) 0901125227

Teorema 3

Di dalam graf lengkap G dengan n buah vertex (n 3), terdapat ( )

buah sirkuit

hamilton.

Contoh :

(i) Graf lengkap n = 3, memiliki sirkuit

hamilton 1 yaitu 1231

(ii) Graf lengkap n = 4, memiliki sirkuit

hamilton 3 yaitu, ABCDA, BDCAB,

dan CADBC

Teorema 4

Di dalam graf lengkap G dengan n buah simpul (n 3 dan n ganjil), terdapat ( )

buah sirkuit hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap

dan n 4, maka di dalam G terdapat ( )

buah sirkuit hamilton yang saling lepas.

Contoh :

(persoalan pengaturan tempat duduk). Sembilan anggota sebuah klub yang bertemu

tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk

sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda setiap

makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan?

Jumlah pengaturan tempat duduk yang berbeda adalah ( )

Graf yang merepresentasikan :

@tiarindarto FKIP UHAMKA (Math_H) 0901125227

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.

Contoh :

Untuk graf yang ditunjukkan pada gambar berikut deg v + deg w 5 untuk masing-

masing vertex yang tidak berdekatan v dan w. Jadi menurut teorema 5 graf ini 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.

Contoh :

deg(a)+deg(b)+deg(c)+deg(d)+deg(e) = 1 + 2 + 2 + 2 + 1 = 8

jumlah derajat dari masing-masing vertex lebih dari n – 1 =

5 – 1 = 4

C. Referensi

Bondy, J. A, & Murty, U. S. R. 2000. Graduate Texts In Mathematics Graph Theory.

Springer

. 1976. Graph Theory With Applications. New York: Elsevier Science

Publishing

Chartrand, G, & Lesniak, L. 1996. Graphs & Digraphs Third Edition. Florida: Chapman

& Hall (CRC)

http://syaifulhamzah.files.wordpress.com/2012/10/course-note-graph-hamilton.pdf

(diakses 20 November 2012 pukul 08:56 WIB)

http://syaifulhamzah.files.wordpress.com/2012/10/course-note-4-graph-euler-dan-

hamilton.pdf (diakses 20 November 2012 pukul 08:56 WIB)

http://www.slideshare.net/CliquerzJavaneze/bab-9-graf#btnNext

(diakses 20 November 2012 pukul 19:45 WIB)

@tiarindarto FKIP UHAMKA (Math_H) 0901125227

Politeknik Telkom. Graf. (Dalam bentuk slide power point). Bandung: Politeknik

Telkom

Yulianti, K. 2008. Hand Out mata Kuliah Teori Graf (MT 424) Jilid Satu . Bandung: UPI

Vasudev, C. 2006. Graph Theory With Applications. New Delhi: New Age International

Publishers

www.repository.upi.edu