Project UTS Teori Graf PDF

PROJECT TEORI GRAF Deskripsi Proyek Mahasiswa mengumpulkan data tentang jarak atau bobot antara lokasi-lokasi di sekitar rumah mereka. Proyek ini akan memanfaatkan data tersebut untuk menerapkan algoritma Dijkstra, Prim, dan Kruskal dalam menentukan rute terpendek dan Minimum Spanning Tree (MST), s...

PROJECT TEORI GRAF Deskripsi Proyek Mahasiswa mengumpulkan data tentang jarak atau bobot antara lokasi-lokasi di sekitar rumah mereka. Proyek ini akan memanfaatkan data tersebut untuk menerapkan algoritma Dijkstra, Prim, dan Kruskal dalam menentukan rute terpendek dan Minimum Spanning Tree (MST), serta menganalisis keberadaan graf Hamiltonian dan graf Euler dalam konteks rute yang ditentukan. Tujuan Proyek 1. Menganalisis konsep dasar teori graf dan penerapannya dalam kehidupan sehari-hari. 2. Menerapkan algoritma Dijkstra, Prim, dan Kruskal untuk analisis graf. 3. Menganalisis keberadaan graf Hamiltonian dan graf Euler pada graf yang dibuat. Langkah-Langkah Proyek yang Dilakukan Mahasiswa 1. Kumpulkan data mengenai lokasi di sekitar rumah atau kost kalian (misalnya, sekolah, minimarket, mall, kampus atau tempat lainnya) serta tentukan jarak atau bobot antar lokasi tersebut. Jika jalan menuju Lokasi tertentu merupakan jalan 2 arah, maka jadikan sebagai sisi rangkap. Catatan: Jumlah Lokasi minimal 8 2. Data dapat diperoleh dari google map atau aplikasi lainnya. 3. Buatlah graf berdasarkan data yang dikumpulkan tersebut. Setiap lokasi menjadi simpul (node) dan jarak/bobot antar lokasi menjadi sisi (edge). 4. Anda dapat menggunakan berbagai aplikasi (IT) untuk membantu dalam visualisasi. Implementasi Algoritma 5. Algoritma Dijkstra: Berdasarkan graf yang telah Anda gambar pada poin 3, pilihlah Lokasi tertentu yang ingin ada datangi kemudian tentukan rute terpendek dari rumah atau kostan Anda ke lokasi tertentu tersebut (misalnya, dari rumah atau kostan ke kampus). Gunakan Algoritma Djikstra untuk menentukannya. Catatan: Jika jarak kostan Anda sangat dekat dengan kampus, bisa gunakan Lokasi tujuan lain yang tidak terlalu dekat. 6. Algoritma Prim: Temukan Minimum Spanning Tree (MST) dari graf yang telah dibuat pada poin 3 menggunakan ALgoritma Prim.  7. Algoritma Kruskal: Temukan Minimum Spanning Tree (MST) dari graf yang telah dibuat pada poin 3 menggunakan Algoritma Kruskal 8. Bandingkan hasilnya poin 6 dan poin 7. Apa yang dapat Anda jelaskan? Analisis Graf Hamiltonian dan Graf Euler 9. Graf Semi-Hamiltonian: Tunjukkan apakah graf yang dibuat pada poin 3 merupakan graf semi-Hamilton? Jika iya, tunjukkan lintasan Hamiltonnya! 10. Graf Semi-Euler: Tunjukkan apakah graf yang dibuat pada poin 3 merupakan graf semi-Euler? Jika iya, tunjukkan lintasan Eulernya! Format Pengerjaan - Anda dipersilahkan mengerjakan project ini dengan diketik atau menggunakan berbagai aplikalsi (Canva, Geogebra atau aplikasi lainnya) maupun ditulis tangan dengan menggunakan berbagai warna. - Tugas dikumpulkan paling lambat Kamis, 31 Oktober 2024 pukul 16.00 wita di Ruang Dosen Pendidikan Matematika (Meja dosen pengampu mata kuliah) Kriteria Penilaian Ketepatan dan kelengkapan data yang dikumpulkan. Kualitas graf yang dibuat dan representasi visualnya. Keberhasilan implementasi algoritma dan akurasi hasil. Analisis keberadaan graf Hamiltonian dan graf Euler. Kualitas laporan project.