Lintasan, Sirkuit & Pohon — melanjutkan proyek akhir Peta Jaringan Kota dengan mengecek jalur Euler dan mencari pohon merentang.
Durasi: 120 menitPrasyarat: Pertemuan 10 — Pengantar Teori GrafTools: kalkulator Euler & pohon merentang di halaman ini
1
Lintasan vs Sirkuit
Bayangin kamu jalan-jalan keliling kota lewat beberapa jalan yang berbeda-beda. Kalau di akhir perjalanan kamu balik lagi ke rumah (titik awal), itu namanya sirkuit (circuit). Tapi kalau kamu berhenti di tempat lain, bukan di rumah, itu namanya lintasan (path).
Lebih formalnya: lintasan adalah perjalanan melalui serangkaian titik lewat sisi-sisi yang berbeda, dan berakhir di titik yang BERBEDA dari titik awal. Sirkuit itu sama seperti lintasan, tapi kembali lagi ke titik awal.
Konsep ini penting banget buat proyek akhir kita: kita mau tahu, dari Peta Jaringan Kota yang sudah kita hitung derajatnya di Pertemuan 10, bisakah kita lewatin SEMUA rute tepat satu kali tanpa mengulang jalan yang sama?
Istilah penting: perjalanan yang melewati SETIAP SISI dalam graf tepat satu kali disebut jalur/lintasan Euler, dinamai dari matematikawan Leonhard Euler yang pertama kali memecahkan masalah ini (kasus klasik "Tujuh Jembatan Königsberg").
2
Euler & Pohon
Ada 4 istilah kunci di pertemuan ini:
Jalur Lengkap
Lintasan Euler
Melewati SETIAP SISI dalam graf tepat satu kali — boleh berakhir di titik yang berbeda dari titik awal.
Jalur Lengkap + Pulang
Sirkuit Euler
Melewati SETIAP SISI tepat satu kali DAN kembali ke titik awal — syaratnya SEMUA titik harus berderajat genap (dan graf terhubung).
Tanpa Putar Balik
Pohon (Tree)
Graf terhubung yang TIDAK memiliki sirkuit/siklus sama sekali — struktur paling "hemat" untuk menghubungkan semua titik.
Rangka Minimal
Pohon Merentang
Sub-graf berbentuk pohon yang menghubungkan SEMUA titik pada graf asli, memakai tepat (jumlah titik − 1) sisi.
3
Coba Langsung: Kalkulator Euler & Pohon Merentang
Masih pakai Peta Jaringan Kota yang sama dari Pertemuan 10. Coba dua tab di bawah: Cek Sirkuit/Lintasan Euler buat lihat apakah semua rute bisa dilewati tepat sekali, dan Cari Pohon Merentang buat cari rangka minimal yang menghubungkan semua lokasi.
Cek Sirkuit/Lintasan Euler
Klik Cek untuk melihat hasilnya…
Cari Pohon Merentang
Klik Cari untuk melihat hasilnya…
Dengan graf Peta Jaringan Kota kita, ada tepat 2 titik berderajat ganjil (A dan C) — jadi Lintasan Euler ADA (mulai dari A, berakhir di C, atau sebaliknya), tapi Sirkuit Euler TIDAK ADA.
4
Latihan Mandiri / Lanjutan Proyek Akhir
Sebelum lanjut ke Pertemuan 12, coba kerjakan sendiri:
Ambil rancangan Peta Jaringan Kota buatan sendiri dari Pertemuan 10, masukkan ke Tab "Cek Sirkuit/Lintasan Euler" — apakah punya sirkuit, lintasan, atau tidak keduanya?
Masukkan graf yang sama ke Tab "Cari Pohon Merentang" — catat berapa sisi yang ditemukan (harus tepat jumlah titik − 1).
Simpan hasilnya, karena rancangan ini masih akan dipakai lagi di Pertemuan 12 untuk pewarnaan graf.
5
Cek Pemahaman
1. Lintasan (path) dalam graf berbeda dari sirkuit (circuit) karena...
Perbedaan intinya ada di titik akhir — kembali ke awal (sirkuit) atau tidak (lintasan).
2. Syarat graf terhubung memiliki Sirkuit Euler (melewati SETIAP sisi tepat sekali dan kembali ke titik awal) adalah...
Supaya bisa "masuk dan keluar" lagi dari tiap titik tanpa mengulang sisi, tiap titik butuh pasangan sisi genap.
3. Jika tepat ada 2 titik berderajat ganjil dalam graf terhubung, maka graf tersebut memiliki...
Dua titik ganjil itu jadi titik awal dan akhir lintasan — perjalanan tidak bisa kembali ke awal karena itu akan membuat derajatnya genap.
4. Pohon (tree) dalam teori graf didefinisikan sebagai...
Pohon itu "struktur minimal" untuk menghubungkan semua titik — tanpa jalan memutar (siklus).
5. Jika suatu pohon merentang (spanning tree) diambil dari graf dengan 5 titik, berapa banyak sisi yang dimilikinya?
Pohon merentang selalu punya tepat (jumlah titik − 1) sisi, berapapun banyak sisi graf aslinya — di Peta Jaringan Kota kita (5 lokasi), pohon merentangnya selalu 4 sisi.
Skor: 0 / 5 terjawab benar
6
Ringkasan Pertemuan 11
Lintasan Euler melewati semua sisi tepat sekali (boleh berakhir beda titik); Sirkuit Euler juga melewati semua sisi tapi harus kembali ke titik awal (syarat: semua derajat genap).
Peta Jaringan Kota kita punya 2 titik ganjil (A dan C) — jadi punya Lintasan Euler tapi TIDAK punya Sirkuit Euler.
Pohon merentang menghubungkan semua titik tanpa siklus, selalu memakai (jumlah titik − 1) sisi — pada graf kita, itu 4 sisi.
Selanjutnya
Di Pertemuan 12 (pertemuan terakhir!), kita akan menyelesaikan proyek akhir dengan mewarnai peta — memastikan tidak ada dua lokasi bertetangga yang dapat warna sama.