Langsung ke konten utama

SOAL + JAWABAN UAS 4 "TEORI GRAPH"

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

============================================================
Labels:

Komentar

  1. Unknown21 Maret 2013 pukul 06.54

    Saya nggak mudeng karena saya masih SMP -_-

    BalasHapus
  2. Apaajaa15 Desember 2016 pukul 07.30

    Kak klo yg nomor 1 itu graph apa ya namanya??

    BalasHapus
  3. Apaajaa15 Desember 2016 pukul 07.31

    Kak klo yg nomor 1 itu graph apa ya namanya??

    BalasHapus

Posting Komentar

Postingan populer dari blog ini

Akhlak Lil Banat juz 1 Bab 40. NASIHAT UMUM (1)

-1- Wahai anak perempuan yang cerdas: ketika kalian menuntun sesuatu kepada seseorang, terlebih kepada ibu kalian, maka janganlah kalian berkata kepada ibu kalian: Berikan aku ini, lakukan seperti ini. Tetapi lakukanlah seperti dengan tata makerama, dan ucapkan: silahkan ibu, atau silahkan melakukan ini, kemudian berterima kasihlah kalian kepada ibu kalian atas bantuan dari nya, dengan berkata: Terima kasih, atau terima kasih banyak. atau: Allah akan membalas kebaikanmu. -2- Ketika seseorang berkata kepada kalian, maka dengarkanlah dengan sesama, dan jangan memutus perkatannya, tetapi tunggulah sampai dia selesai berbicara, ketika seseorang datang kepada kalian dengan perkataan atau cerita bersungguh-sungguhlah dalam mendengarkannya, jangan berkata kepada dia: sesungguhnya saya sudah mendengarkan cerita ini, agar hati orang tersebut tidak sakit. -3- Selalu jagalah kebersihan gigi kalian, seperti menggunakan siwak atau sikat gigi setiap hari apa lagi setelah makan sehingga gigi...
1 komentar
Baca Selengkapnya

PENGEMBANGAN ALAT PENILAIAN KEGIATAN / PEMBELAJARAN DI TK - Konsep Dasar Penilaian, Prosedur, Jenis, dan Alat Penialaian TK

 
Posting Komentar
Baca Selengkapnya

Khulashoh Nurul Yaqin Juz 1 (Pelajaran 2) NASAB DAN WAFATNYA AYAH RASULULLAH SAW

-1- Ayah Rasul: Abdullah bin Abdul Mutholib bin Abdi Manaf bin Qusay bin Kilab. -2- Ibu Rasul: Aminah bin Wahab bin Abdi Manaf bin Zuhroh bin Kilab. -3- Nasab ibu dan ayah Rasul bertemu pada kakk rasul yang kelima yaitu Kilab. -4- Ayah Rasul wafat ketika Rasul masih di dalam kandungan, dan usia ayah Rasul pada waktu itu 18 tahun, dan dimakamkan di kota Madinah, dan orang tuanya tidak meninggalkan harta untuk Rasul. SOAL Siapakah nasab Rasul dari arah ayahnya? Siapakah nasab Rasul dari arah ibunya? Pada kakek siapa nasab Ibu dan Ayah bertemu? Kapan ayah Rasul wafat? Dimakamkan di mana ayah Rasul? RINGKASAN Ayah Rasul bernama Abdullan bin Abdul Mutholib, dan Ibu beliau Aminah binti Wahab. Nasab Ibu dan Ayah Rasul bertemu pada kakeknya yang kelima. Ayah Rasul meninggal ketika Rasul masih di dalam kandungan.
Posting Komentar
Baca Selengkapnya