LATIHAN SOAL PERTEMUAN 13 ( METODE TRAVELLING SALESMAN & MINIMUM SPANNING TREE )

Nama kelompok :

#Tiar Prasetiyo ( 17190782 )

#Rivaldi Nazar Yuniar ( 17190659 )
#Eko Mardiyanto ( 17190801 )
#Rian Ferdian Maulana ( 17190684 )

UNIVERSITAS BINA SARANA INFORMATIKA
Kelas ( 17.1E.07 )

LATIHAN SOAL PERTEMUAN 13 
LOGIKA DAN ALGORITMA

1. Gunakan metode travelling salesman

Terapat 4 kota yaitu ABCD.

Jarak antar kota A, B, C, dan D sebagai berikut :

Jarak A ke B = 7, A ke C = 5, A ke D = 3, B ke C = 6, B ke D = 6, Dan C ke D = 2.

Graf dapat dilihat dibawah ini

Kota pusat : A

Buat lasolusi untuk jalur terpendeknya

Problem diatas menghasilkan waktu minimalnya adalah 18 diperoleh perjalanan sebagai berikut :

2. Buat lah minimum spanning tree (MST) dan nilai bobotnya dari graf berikut ini dengan menggunakan algoritma solin dan kruskal.

graf G :

Penyelesaian Algoritma Solin

1. Urutkan Ruas Graf (G) menurut bobotnya dari bobot terbesar sampai bobot terkecil.

BOBOT	RUAS
10	E,F	E,G
9	B,E	E,I
8	D,E	E,H
7	C,F	G,J	I,J
6	D,F	G,H	H,J
5	A,B	A,C
4	C,D	B,D	H,I
3	F,G

2. Lakukan penghapusan masing masing ruas yang tidak menyebabkan graf menjadi tidak terhubung atau membentuk sirkuit, kita mulai melakukan tahapan penghapusan dengan ruas dengan nilai terbesar sampai nilai terkecil.

1. Bobot : 10 EF, EG

Ruas EF, EG Tidak Dihapus karena ruas tersebut menyebabkan graf terhubung

2. Bobot : 9 BE, EI

BE, EI Tidak dihapus karena dua ruas tersebut menghubungkan graf

3. bobot : 8 DE, EH

Ruas DE, EH TIdak dihapus karena dua ruas tersebut menghubungkan graf

4. Bobot 7 : CF, GJ, IJ

Ruas CF GJ dihapus Sedangkan IJ dihapus Karena membentuk sirkuit

5. Bobot 6 : DF, GH, HJ

Ruas DF, GH, HJ dihapus karena membentuk sirkuit

6. Bobot 5 : AB, AC

Ruar AB tidak dihapus sedangkan AC dihapus karena membentuk sirkuit

7. Bobot 4 : BD, CD, HI

Ruas BD, CD, HI dihapus karena membentuk sirkuit

8. Bobot 3 : FG

Ruas FG dihapus karena membentuk sirkuit

Tahap penghapusan selesai, bobot 4 adalah minimum Spanning Tree dari graf G dengan nilai : 73

Penyelesaian Algoritma Kruskal

1. Mula mula kita buat graf G hanya terdiri dari simpul saja

2. Urutkan ruas dari bobot terkecil ke bobot terbesar (FG,CD,BD,HI,AB,AC,DF,GH,HJ,CF,GJ,IJ,DE,EH,BE,EI,EF,EG), Kemudian berdasarkan urutan tersebut, kita menambahkan ruas dengan mencegah terbentuknya sirkuit.

Gambar 1 : Penambahan Ruas FG

Gambar 2 : Penambahan Ruas BD, CD, HI

Gambar 3 : Penambahan Ruas AB, Ruas AC tidak dilakukan

Gambar 4 : Penambahan ruas DF, GH, HJ

Gambar 5 : Penambahan CF, GJ, IJ Tidak dilakukan karena membentuk sirkuit

Gambar 6 : Penambahan ruas DE dilakukan, sedangkan ruas EH tidak dilakukan karena membentuk sirkuit

Gambar 7 : Penambahan Ruas BE, EI tidak dilakukan karena membentuk sirkuit

Gambar 8 : Penambahan Ruas EF, EG tidak dilakukan karena membentuk sirkuit

Gambar 9 : SELESAI

MST Graf G Nilainya 46 

3. gunakan dijstra algoritma untuk mencari rute terpendek antara node 1 dan setiap node lainnya dalam jaringan berikut :

Titik Pengunjung	1	2	3	4	5	6	7	8
#	#	#	#	#	#	#	#	#
1	0	1	2	#	#	#	#	#
1,2	#	1	2	#	#	#	#	#
1,2,3	#	#	2	4	3	6	#	#
1,2,3,5	#	#	#	#	3	6	10	#
1,2,3,5,6	#	#	#	#	#	6	9	8
1,2,3,5,6,8	#	#	#	#	#	#	#	8

Titik Pengunjung	1	2	3	4	5	6	7
#	#	#	#	#	#	#	#
1	0	5	1	#	#	#	#
1,3	#	3	1	7	#	#	#
1,3,2	#	3	#	10	3	6	#
1,3,2,5	#	#	#	7	3	9	10
1,3,2,5,4	#	#	14	7	#	8	13
1,3,2,5,4,6	#	15	#	#	#	8	10
1,3,2,5,4,6,7	#	#	#	#	#	#	10