Metode tetangga terdekat graf

28
Teori Graf Metode Tetangga Terdekat Matematika Diskrit

Transcript of Metode tetangga terdekat graf

Page 1: Metode tetangga terdekat   graf

Teori Graf Metode Tetangga

Terdekat

Matematika Diskrit

Page 2: Metode tetangga terdekat   graf
Page 3: Metode tetangga terdekat   graf

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)

Page 4: Metode tetangga terdekat   graf

Gambar :

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

2

43

1

Page 5: Metode tetangga terdekat   graf

DefinisiSirkuit Euleur adalah sirkuit yang

melewati masing-masing sisi tepat

satu kali.

Graf yang mempunyai sirkuit

tersebut disebut graf semi-euleur

(semi-Eulerian graph)

Page 6: Metode tetangga terdekat   graf

Gambar :

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

32

5

1

6 7

4

Page 7: Metode tetangga terdekat   graf

DefinisiLintasan Hamilton ialah lintasan

yang melalui tiap simpul didalam

graf tepat satu kali.

Graf yang memiliki lintasantersebut disebut graf semi-Hamilton.

Page 8: Metode tetangga terdekat   graf

Gambar :

Lintasan Hamilton : 3, 2, 1, 4

21

4 3

Page 9: Metode tetangga terdekat   graf

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

Page 10: Metode tetangga terdekat   graf

Gambar :

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

2

43

1

Page 11: Metode tetangga terdekat   graf

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.

Page 12: Metode tetangga terdekat   graf

Contoh soal (1) :

Gunakan algoritma tetangga terdekat pada

graph berbobot berikut:

Page 13: Metode tetangga terdekat   graf

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.

Page 14: Metode tetangga terdekat   graf

Kemudian tambahkan 5 ke w. Verteks yang tidak

bertanda yang terdekat dengan A adalah C, jadi

tambahkan C ke dalam path, dan tandai A.

Page 15: Metode tetangga terdekat   graf

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.

Page 16: Metode tetangga terdekat   graf

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.

Page 17: Metode tetangga terdekat   graf

Gambar berikut memperlihatkan semua ketiga Hamilton

sirkuit yang dapat dibentuk dari graf tersebut, dan yang

paling baik adalah yang memiliki total bobot 23.

Page 18: Metode tetangga terdekat   graf

Contoh soal (2)

Page 19: Metode tetangga terdekat   graf

Misalkan gambar tersebut diberikan

cara perhitungan untuk menyelesaikan

permasalahan perjalanan bus tersebut

dengan metode tetangga terdekat, adapun

langkah-langkahnya sebagai berikut:

Page 20: Metode tetangga terdekat   graf

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

Page 21: Metode tetangga terdekat   graf

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

Page 22: Metode tetangga terdekat   graf

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

Page 23: Metode tetangga terdekat   graf

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

Page 24: Metode tetangga terdekat   graf

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

Page 25: Metode tetangga terdekat   graf

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

Page 26: Metode tetangga terdekat   graf

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

Page 27: Metode tetangga terdekat   graf

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

Page 28: Metode tetangga terdekat   graf