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

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

Komentar

Posting Komentar

Postingan populer dari blog ini

Terjemah Mabadi' Fiqih Juz 3 (THOHAROH / BERSUCI)

Thoharoh ialah mengerjakan sesuatu yang tidak sah sholat seseorang kecuali dengan melakukan bersuci. Thoharoh itu ada dua macam yaitu: Thoharoh dari hadats dan thoharoh dari kotoran. Thoharoh dari hadats ialah bersuci dengan cara berwudlu', mandi dan tayammum (pengganti wudlu dan mandi). Thoharoh dari kotoran ialah bersuci dengan cara istinja' (sesudah buang air kecil atau besar), dan menghilangkan najis dari tubuh, pakaian dan tempat. Macam-macam benda yang dapat mensucikan itu ada empat, yaitu: air, debu, batu, dan menyamak untuk kulit binatang0. Pembagian air itu ada tiga, yaitu : 1. air suci yang dapat mensucikan, 2. air yang suci yang tidak dapat mensucikan, 3. air yang terkena najis. Air yang suci yang dapat mensucikan yaitu: semua air yang berasal dari langit atau yang bersumber dari bumi, dan tidak merubah sifat-sifatnya dengan sebab adanya benda yang dapat merubah kesucian air tersebut. seperti: air hujan, air laut, air sungai, air es dan air embun. Air yang ber

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 sebutkan

Akhlak Lil Banat Juz 1 Bab 7. ANAK PEREMPUAN YANG SHOLIHAH

             Khadijah adalah anak yang shalihah. Ayah, ibu, dan guru-guru perempuanya mencintai Khadijah, teman-teman Khadijah juga memulyakan Khadijah. Setiap anak perempuan pasti memiliki cita-cita, sama halnya seperti Khadijah. Kebiasaan Khadijah sebelum tidur adalah berdzikir kepada Allah dan bersyukur karena sudah menjaga Khadijah selama hidupnya dari segala musibah dan penyakit. Khadijah berkata: بِسْمِكَ اللهُمَّ اَحْيَاوَاَمُوْنُ yang artinya” Dengan Namamu Ya Allah saya hidup dan mati” . Dan ketika dia bangun dari tidurnya dia juga berzdikir kepada Allah. Dia bersyukur atas nikmat tidurnya dan yang telah mengistirahatkannya dari kelelahan dan Allah membiasakan di setiap aktifitasnya, Khadijah berkata: اَلْحَمْدُ لِلَّهِ الَّذِيْ أَحْيَانَا بَعْدَ مَا أَمَاتَنَا وَإِلَيْهِ النُّشُوْرِ yang artinya: “Segala puji bagi-Mu, ya Allah, yang telah menghidupkan kembali diriku setelah kematianku, dan hanya kepada-Nya nantinya kami semua akan dihidupkan kembali.”              Da