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 6. ِApa Kewajian Anak Perempuan Kepada Tuhannya?

ماذايجب عليك لربك  kamu harus benar-benar tahu bagaimana Tuhanmu memberimu nikmat yang begitu besar. Maka kamu harus mensyukuri nikmat itu dengan beribadah kepada Allah dan mengagungkan-Nya. Dan menjalankan semua yang diperintah oleh Allah kepadamu dan meninggalkan semua hal yang harus di tinggalkan. Dan kamu harus mencintai Allah melebihi cintamu kepada ayah dan ibumu, melebihi cintamu kepada dirimu sendiri. Dan memohon kepada Allah dengan semua permohonan yang bagus. Dan kamu terus berdoa kepada Allah agar allah menjunjukkan kepadamu kesematan dan jalan yang baik. Dan Allah akan menjadikanmu anak perempuan yang bagus, yang beruntung di dunia dan di akhirat. Apabila kamu bersyukur kepada Allah dan menjalankan perintah Allah. Maka kamu dicintai Allah yang Maha suci dan Maha Luhur dan menjadikanmu manusia yang menyayangi sesama manusia dan Allah akan menjagamu dari segala musibah dan penyakit, dan Allah akan memberimu segala hal yang akan menambahkan nikmat, seperti yang di sebu...
7 komentar
Baca Selengkapnya

Terjemahan Akhlak Lil Banat Juz 2 (Bab 1 AKHLAK)

1. Ingatlah wahai anak perempuan yang mulia, sesungguhnya akhlak yang baik itu menjadi penyebab keberuntunganmu di dunia dan di akhirat. Serta Allah akan ridho padamu, dan Allah akan menambah imanmu, dan engkau akan dimasukkan ke dalam surga-Nya. Allah akan melapangkan rizkimu, dan memberikan berkah dalam umurmu dan semua amalan-amalanmu. Allah Swt berfirman : قَدْ اَفْلَحَ مَنْ زَكَّهَاوَقَدْخَابَ مَنْ دَسَّاهَا "sesungguhnya beruntunglah orang yang membersihkan (dengan beriman) jiwa itu, dan sesungguhnya merugilah orang  yang mengotorinya." Rasul Saw bersabda: اِنَّ اْلمُؤْمِنِيْنَ اِيْمَانًاأَحْسَنُهُمْ خُلُقًا "Orang mukmin yang paling sempurna imannya adalah orang yang paling bagus akhlaknya" اِنَّ اْلمُؤْمِنَ لَيُدْرِكَ بِحُسْنِ خُلُقِهِ دَرَجَةَالصَّائِمِ اْلقَائِمِ "Sesungguhnya seorang mukmin dengan akhlaknya yang mulia dapat menyamai derajat orang yang berpuasa dan qiyamul lail" kanan adalah sebagus-bagusnya budi pekerti. Hakim ...
6 komentar
Baca Selengkapnya

Terjemah Mabadi' Fiqih Juz 1 (2)

S: Apa niat wudhu' itu? J: Niat wudhu' yaitu: Saya berniat menghilangkan hadats kecil. ----------------------------------------------------------------------------------------------- S: Apa Hadats 1  kecil itu? J: Yaitu sesuatu sesuatu yang menyebabkan batalnya wudhu'. 1. Hadats yaitu sesuatu yang timbul pada diri seteleh mengalami perkara yang membatalkan wudhu'. ----------------------------------------------------------------------------------------------- S: Apa perkara yang membatalkan wudhu? J: Hal-hal yang membatalkan wudhu ada 5: 1) Keluarnya sesuatu dari kedua lubang, 2) Hilangnya akal, 3) Tidur, 4) Menyentuh perempuan yang bukan muhrim, 5) Menyentuh qubul atau dubur dengan menggunakan telapak tangan. ----------------------------------------------------------------------------------------------- S: Siapa itu perempuan yang bukan muhrim? J: Perempuan yang bukan muhrim yaitu perempuan yang haram untuk dinikahi karena sebab nasab, atau sepe...
Posting Komentar
Baca Selengkapnya