Teori Graf Metode Tetangga

Terdekat

Matematika Diskrit

Definisi Lintasan Euler adalah lintasan yang

melalui masing-masing sisi didalam

graf tepat satu kali

Graf yang mempunyai lintasan

tersebut disebut graf semi-Euler

(Euleurian graph)

Gambar :

Lintasan Euleur : 3, 1, 2, 3, 4, 1

2

43

1

DefinisiSirkuit Euleur adalah sirkuit yang

melewati masing-masing sisi tepat

satu kali.

Graf yang mempunyai sirkuit

tersebut disebut graf semi-euleur

(semi-Eulerian graph)

Gambar :

Sirkuit Euler : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1

32

5

1

6 7

4

DefinisiLintasan Hamilton ialah lintasan

yang melalui tiap simpul didalam

graf tepat satu kali.

Graf yang memiliki lintasantersebut disebut graf semi-Hamilton.

Gambar :

Lintasan Hamilton : 3, 2, 1, 4

21

4 3

DefinisiSirkuit Hamilton ialah sirkuit yang melalui

tiap simpul didalam graf tepat satu kali,

kecuali simpul asal (sekaligus simpul akhir)

yang dilalui dua kali

Graf yang memiliki sirkuit disebut

graf Hamiton

Gambar :

Sirkuit Hamilton : 1, 2, 3, 4, 1

2

43

1

Metode Tetangga Terdekat

Adalah metode yang didasarkan

pada jarak minimum, dimulai

dengan objek yang dipisahkan

dengan jarak paling pendek maka

keduanya akan ditempatkan pada

kelompok pertama dan

seterusnya.

Contoh soal (1) :

Gunakan algoritma tetangga terdekat pada

graph berbobot berikut:

PenyelesaianDimulai dari B. Beri nilai awal w=0 dan daftar verteks

dalam path adalah B. Verteks yang tidak bertanda yang

terdekat dengan B adalah A, jadi tambahkan A ke dalam

path, dan tandai B.

Kemudian tambahkan 5 ke w. Verteks yang tidak

bertanda yang terdekat dengan A adalah C, jadi

tambahkan C ke dalam path, dan tandai A.

Tambahkan w dengan 6. Vertaks yang tidak

bertanda yang terdekat dengan C adalah D, jadi

tambahkan D ke dalam path, dan tandai C.

Kemudian tambahkan 3 ke w.

Karena tidak ada sisa verteks yang tidak bertanda, maka

cycle akan terpenuhi dengan menambahkan verteks B ke

dalam path. Kemudian tambahkan w dengan 10.

Bobot dari sirkuitnya adalah 24.

Gambar berikut memperlihatkan semua ketiga Hamilton

sirkuit yang dapat dibentuk dari graf tersebut, dan yang

paling baik adalah yang memiliki total bobot 23.

Contoh soal (2)

Misalkan gambar tersebut diberikan

cara perhitungan untuk menyelesaikan

permasalahan perjalanan bus tersebut

dengan metode tetangga terdekat, adapun

langkah-langkahnya sebagai berikut:

1. Diambil A sebagai

terminal

2. Dipilih halte pertama

yang paling dekat

dengan A, yaitu C,

bobot AC adalah 6 km

A

C

6 km

3. Ambil halte C untuk

dihubungkan dengan halte

lain yang terdekat yaitu halte

F, bobot CF adalah 2,5 km

A

F

C

6 km

2,5 km

B

4 km

4. Ambil halte F untuk

dihubungkan dengan halte

lain yang terdekat yaitu

halte B, bobot FB adalah 4

km

5. Ambil halte B untuk

dihubungkan

dengan halte lain

yang terdekat yaitu

halte G, bobot BG

adalah 7,5 kmA

F

C

6 km

2,5 km

B

4 km

G

7,5 km

6. Ambil halte G untuk

dihubungkan dengan halte lain

yang terdekat yaitu halte H atau

I, karena dua halte tersebut

bobotnya sama ke halte G,

kemudian dipilh yang

mempunyai bobot lebih kecil,

tetapi tidak boleh memilih halte

yang pernah dipilih. Diambil

halte I, bobot GI adalah 4,5 km

I

H

A

F

C

6 km

2,5 km

B

4 km

G

7,5 km

4,5 km

7. Ambil halte I untuk

dihubungkan dengan halte

lain yang terdekat yaitu H,

bobot IH adalah 1 kmI

H

A

F

C

6 km

2,5 km

B

4 km

G

7,5 km

4,5 km1 km

J2,5 km

8. Ambil halte I untuk

dihubungkan dengan halte

lain yang terdekat yaitu J,

bobot HJ adalah 2,5 km

9. Ambil halte J untuk

dihubungkan dengan halte

lain yang terdekat yaitu E,

bobot JE adalah 3,5 km

I

H

A

F

C

B

G

7,5 km

4,5 km

J

2,5 km

E

3,5 km

D

4 km

12 km

10. Ambil halte E untuk

dihubungkan dengan halte

lain yang terdekat yaitu D,

bobot ED adalah 4 km

Dari halte terakhir

yang dipilh langsung

kembali ke terminal, yaitu

halte A dengan bobot 7

km.

Maka penyelesaian

yang mungkin dengan

metode tetangga

terdekat adalah: A-C-F-B-

G-I-H-J-E-D-A.

I

H

A

F

C

B

G

7,5 km

4,5 km

J

2,5 km

E

3,5 km

D

4 km

12 km

Jadi total bobot rute yang

ditempuh oleh bus tersebut

adalah 6 + 2,5 + 4 + 7,5 + 4,5

+ 1 + 2,5 + 3,5 + 4 + 7 = 42,5

km dengan perjalanan dimulai

dari titik A atau terminal

Giwangan.

I

H

A

F

C

B

4 km

G

7,5 km

4,5 km

J

2,5 km

E

3,5 km

D

4 km

12 km