SOAL + JAWABAN UAS 4 "TEORI GRAPH"

Senin, 18 Juni 2012 · Posted in

SOAL DAN JAWABAN UJIAN AKHIR SEMESTER IV
Mata Kuliah "TEORI GRAPH"
UNIVERSITAS YUDHARTA PASURUAN
=================================================================
Nama : HUSNUL KHOTIMAH
NIM   : 2010.69.04.0004
Jurusan / Prodi : Teknik Informatika
=================================================================

1.   Tiga pasang suami istri hendak menyebrangi sungai. Dan hanya terdapat 1 perahu yang hanya untuk mengangkut dua orang. Dan ternyata semua suami adalah seorang pencemburu yang tidak mau meninggalkan istrinya bersama pria lain. Buatlah algoritma penyebrangan yang mungkin untuk ke tiga pasutri tersebut!
       Jawab:

 
2.   Tentukan banyak edge minimal dari sebuah graph dengan 10 vertex, sehingga untuk setiap vertex yang dihilangkan, ada sebuah cycle yang melewati 9 vertex yang tersisa.
Jawab:
Jika vertex (2) dihilangkan lintasan akan memutar pada titik (3) sampai dengan (1).
Maka jumlah edge adalah 9 edge, antara lain:
E1  = 1 - 3                       E4       = 5 -6                       E7        = 8 - 9
E2  = 3 - 4                       E5        = 6 - 7                    E8       = 9 - 0
E3  = 4 - 5                       E6       = 7 - 8                     E9       = 0 - 1
 
sebelum dihilangkan

setelah dihilangkan
























3.    Disebuah pulau terdapat 10 kota, dimana kota-kota tersebut dihubungkan dengan ruas-ruas jalan. Ada dua kota yang terhubung. Ada juga yang tidak. Suatu rute yang dimulai dari suatu kota, mengunjungi tepat 8 dari 9 kota lainnya masing-masing sekali dan kembali ke kota awal dinamakan rute wisata. Tentukan ruas jalan minimal yang perlu untuk dibuat, sehingga apabila diberikan sembarang kota di pulau tersebut ada rute wisata yang tidak melewati kota tersebut.
Jawab:
graph sebuah pulau dengan 10 kota

 
Rute  wisata di mulai dari kota 1 melewati 8 kota lainya. Kecuali kota 7. Ruas jalan yang di butuhkan ada 9 ruas jalan. Antara lain:
R1  : 1-2               R4       : 4-5              R7       : 8-9
R2 : 2-3              R5       : 5-6              R8       : 9-0
R3 : 3-4              R6       : 6-8              R9       : 0-1

============================================================

One Response to “SOAL + JAWABAN UAS 4 "TEORI GRAPH"”

chuzy-ballack.blogspot.com. Diberdayakan oleh Blogger.

✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿

Entri Populer

Tiny Kaoani