Metode tetangga terdekat graf
-
Upload
noni-meylia -
Category
Education
-
view
605 -
download
32
Transcript of Metode tetangga terdekat graf
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