Soal Latihan ETS Matdis 2 PDF

1. Soal Nomer 1 (Ahmad Fauzan Naji) Sebuah toko menjual dua jenis produk, yaitu produk A dan produk B, selama 10 minggu terakhir. Grafik di atas menunjukkan tren penjualan kedua produk tersebut dari minggu ke minggu. Penjuala n produk A ditandai dengan garis biru, sementara...

1. Soal Nomer 1 (Ahmad Fauzan Naji) Sebuah toko menjual dua jenis produk, yaitu produk A dan produk B, selama 10 minggu terakhir. Grafik di atas menunjukkan tren penjualan kedua produk tersebut dari minggu ke minggu. Penjuala n produk A ditandai dengan garis biru, sementara produk B dengan garis oranye. Pertanyaan 1: Pada minggu ke berapa penjualan produk A lebih tinggi dibandingkan produk B? Pertanyaan 2: Pada minggu ke berapa penjualan produk B mencapai puncaknya? Berapa unit yang terjual pada minggu tersebut? 2. Soal Nomor 2 (Alanna Tanisya) Ani baru saja pindah ke sebuah kota kecil dan ingin mengetahui rute terbaik untuk pergi ke sekolah barunya. Dia memiliki peta sederhana yang menunjukkan jalan-jalan di lingkungan barunya. a. Rute mana yang memiliki paling sedikit jalur yang harus dilewati Ani? b. Jika Ani ingin melewati semua jalur tepat satu kali dalam perjalanannya ke sekolah, apakah mungkin? Jika ya, sebutkan rutenya. 3. Soal Nomor 3 (Alya Gustiani) Diberikan 6 mahasiswa dalam sesi tanya jawab. Setiap mahasiswa memberikan pertanyaan kepada minimal 2 mahasiswa lain, dan jumlah mahasiswa yang menerima pertanyaan dari setiap mahasiswa berbeda-beda. a. Gambarkan graf yang merepresentasikan situasi ini, di mana simpul mewakili mahasiswa dan sisi (edge) mewakili pertukaran pertanyaan. b. Graf tersebut harus memiliki setidaknya satu simpul dengan derajat 5 (memberikan pertanyaan kepada semua mahasiswa lainnya) dan minimal satu simpul dengan derajat 2 (memberikan pertanyaan kepada dua mahasiswa lain). Pastikan graf tersebut terhubung.  c. Jelaskan apakah graf tersebut merupakan graf sederhana atau tidak, dan apakah graf tersebut planar atau bukan. 4. Soal Nomor 4 (Azka Darajat) Terdapat tabel seperti berikut Penjelasan: Terdapat 7 Mahasiswa di kelas 2B D3 Teknik Informatika yang mengikuti kegiatan UKM yang ada di Polban. Dari tabel diatas tentukan jadwal kegiatan UKM yang dapat diikuti sedemikian rupa sehingga semua mahasiswa dapat mengikuti tanpa ada kesulitan dalam penyelesaian waktu menggunakan pewarnaan graf!. Gambarkan bentuk graf dan juga matriks nya! 5. Soal Nomor 5 (Bandyaga Adiansyah Sugandi) Perhatikan kedua gambar graf di bawah ini. Apakah graf di bawah memiliki lintasan Euler, sirkuit Euler, lintasan Hamilton, atau sirkuit Hamilton? Jika iya, berikan penjelasan serta tuliskan contoh lintasan atau sirkuit dari graf Euler atau Hamilton tersebut! 6. Soal Nomor 6 (Daffa Al Ghifari) Berdasarkan graf dibawah ini tentukanlah dan gambarkanlah pohon merentang minimum (tahapan pembentukannya tidak perlu) menggunakan algoritma “Kruskal”. 7. Soal Nomor 7 (Daiva Raditya Pradipa) Seorang pengantar susu akan mengantar susu dari pabrik susu pada setiap rumah setiap hari di pagi hari. Bagaimana pengantar susu tersebut dapat menemukan rute tercepat dan terefisien untuk dapat mengantar susu pada setiap rumah pada setiap jalan dan kembali lagi ke pabrik susu (pabrik susu dilambangkan dengan simbol A)? 8. Soal Nomor 8 (Dhea Dria S) Diberikan graf berbobot G dengan simpul V={A,B,C,D,E} dan sisi berbobot E={(A,B,4),(A,C,1),(B,C,2),(B,D,5),(C,D,8),(D,E,6)}. A. Gambarkan graf berbobot tersebut. B. Gunakan algoritma Dijkstra untuk mencari jalur terpendek dari simpul A ke simpul E  C. Jelaskan langkah-langkah algoritma Dijkstra yang digunakan untuk menyelesaikan soal ini. 9. Soal Nomor 9 (Dhira Ramadini) Sebuah jaringan komputer memiliki 5 komputer (A, B, C, D, dan E) yang terhubung satu sama lain. Komputer A terhubung dengan B dan C. Komputer B terhubung dengan A, C, dan D. Komputer C terhubung dengan A, B, dan E. Komputer D terhubung dengan B dan E. Komputer E terhubung dengan C dan D. a) Gambarkan graf yang merepresentasikan jaringan komputer tersebut! b) Berapakah derajat masing-masing simpul? c) Apakah graf tersebut memiliki sirkuit? Jika ya, berikan satu contoh. 10. Soal Nomor 10 (Dwika Ali Ramdhan) Pada suatu gedung, petugas IT berencana memasang jaringan internet yang terhubung dengan semua ruangan. Setiap ruangan diwakili oleh simpul(node), dan koneksi antara ruangan diwakili oleh sisi(edge) dengan panjang kabel tertentu. Petugas ingin memasang jaringan internet dengan total panjang kabel seminimal mungkin. Untuk menyelesaikan masalah ini, gunakan algoritma Minimum Spanning Tree (MST), dengan algoritma Kruskal dan Prim! 11. Soal Nomor 11 (Erina Dwi Yanti)  Perhatikan gambar dua buah graf di bawah ini. Tentukanlah apakah kedua graf tersebut isomorfik atau tidak. Apabila isomorfik, tentukan pula simpul-simpul yang berkorespondensi! Tuliskan juga matriks ketetanggaannya. 12. Soal Nomor 12 (Farhan Maulana Query) Diketahui matriks ketetanggaan (adjacency matrix) dari sebuah graf tak berarah seperti berikut: Gambarkan dua buah graf yang isomorfik dengan matriks tersebut. 13. Soal Nomor 13 (Febi Shintawati) Gambarkan 2 buah graf yang isomorfik dengan graf teratur berderajat 3 yang mempunyai 10 buah simpul 14. Soal Nomor 14 (Febytha) Ubahlah graf dibawah ini dengan menggunakan Algoritma Kruskal agar menjadi pohon merentang minimum dan tentukan bobotnya! 15. a 16. Soal Nomor 16 (Hanif Ahmad Naufal) Tanpa menggambarkan graf-nya, tentukan apakah graf yang memiliki matriks adjacency diatas merupakan: - Graf yang terhubung atau bukan - Graf yang memiliki loop atau tidak - Graf yang memiliki simpul terpencil (isolated vertex) 17. Soal Nomor 17 (Hasbi Andi Muttaqin)  Hitung rute dari titik C ke titik G, pastikan setiap node di kunjungi dan tidak ada titik yang dikunjungi dua kali. 18. Soal nomor 18 (Indah Ratu Pramudita) Seorang salesperson harus mengunjungi 7 kota yang terhubung oleh jaringan jalan yang diwakili oleh graf berbobot. Jarak antar kota diberikan dalam bentuk tabel matriks adjacency di bawah ini (angka-angka mewakili jarak antar kota dalam satuan kilometer). Salesperson memulai perjalanannya dari kota A dan harus mengunjungi semua kota sekali saja, kemudian kembali lagi ke kota A. Tentukan rute perjalanan yang meminimalkan total jarak yang ditempuh dan gambarkan graf tersebut! A B C D E F G A 0 29 20 21 16 31 100 B 29 0 15 29 28 40 72 C 20 15 0 15 14 25 81 D 21 29 15 0 30 20 75 E 16 28 14 30 0 35 96 F 31 40 25 20 35 0 99 G 100 72 81 75 95 99 0 19. Soal nomor 19 (Muammar Syahid R) ada 7 jenis zat kimia yang perlu disimpan di dalam gudang. beberapa pasang dari zat itu tidak dapat disimpan di dalam ruangan yang sama, karena campuran gasnya bersifat eksplosif (mudah meledak). Untuk zat yang semacam itu perlu dibangun ruang-ruang terpisah yang dilengkapi ventilasi dan penyedot udara keluar berlainan. Jika lebih banyak ruang yang dibutuhkan, berarti lebih banyak ongkos yang harus dikeluarkan. Karena itu perlu diketahui berapa banyak minimum ruangan yang diperlukan untuk dapat menyimpan semua zat kimia dengan aman.Berikut adalah daftar pasangan zat kimia yang tidak dapat disimpan di dalam ruangan yang sama: Zat Kimia Tidak dapat disimpan bersama zat kimia A B,D B A,D,E,F,G  C E,G D A,F,B E B,C,G F B,D G C,E,B Gambarkan graf yang menyatakan persoalan di atas, lalu jelaskan arti simpul dan sisi yang menghubungkan dua buah simpul! 20. (Ilham) Tentukan lemma jabat tangan dan merentang minimum dari grafik pohon berikut dengan menggunakan metode Kruskal: 21. (Azzam)  a. Tentukan jalur terpendek antara simpul A dan simpul G, dan hitung total bobot jalur tersebut. b. Representasikan dengan adjacency matrix 22. (Raihan) Apakah graf sederhana yang disajikan oleh pasangan matriks ketetanggaan di bawah ini isomorfik? Jelaskan jawaban, lalu gambarkan grafnya! 23. Soal 23 ( Nalendra Praja Bredtyopati Yudo ) Temukan jalur terpendek ( shortest path ) dari a ke z menggunakan algoritma djikstra. 24. (Nazla)  Tentukan apakah graf dibawah ini planar atau tidak. Jika ya, tunjukan graf planarnya tanpa jalur yang bersilangan. 25. Soal no 25 (Nino Erico Apandi Nainggolan) Diberikan sebuah graf tidak terarah yang terdiri dari 6 simpul (A, B, C, D, E, F) sebagai berikut : A. Sebutkan derajat dari setiap simpul (A, B, C, D, E, F)! B. Gunakan Algoritma Prim untuk menemukan Minimum Spanning Tree dari graf ini. Sebutkan sisi-sisi yang terpilih dan total bobotnya. 26. Nur Akmal Ubahlah graf berikut ini dengan menggunakan algoritma prim agar menjadi pohon merentang minimum dan tentukan bobot nya ! 27. Soal no 27 (R. Muhammad Farrel Walid Imtiyaaz) Dapatkah sebuah graf sederhana dibuat dengan 15 simpul yang masing-masing berderajat lima? tuliskan alasannya. 28. Soal no 28 (Radja Restu Arsita) Tentukan tree merentang minimum untuk graf diatas menggunakan algoritma prim dan gambarkan setiap step nya. 29. Soal no 29 (Tresnardi Fathu Rhamdan) Representasikan matriks berikut dengan menggunakan matriks adjacency (ketetanggaan). 30. Soal no 30 (Yani Rahmawati) Buktikan apakah graf di bawah ini tidak memiliki circuit Hamilton! 31. Soal no 31(Zidan Tri Satria Mukti) Diketahui sebuah graf tidak berarah dengan 6 simpul. Setiap simpul memiliki derajat 2. a. Gambarlah salah satu kemungkinan bentuk graf tersebut. b. Apakah graf ini pasti berbentuk siklus? Jelaskan.