Pohon, graf, dan hubungan antarsimpul
INFO9-07
Membedakan hierarki dari jaringan serta menelusuri jalur pada model kecil.
Bekal awal: Mengenali simpul, hubungan, dan daftar.
Konteks bab
Pembagian giliran adalah model belajar; aturan layanan nyata mengikuti pendamping. Kartu serta jaringan berikut rekaan.
Bacaan dan kasus
2 · Urutan yang berubah tanpa disadari
Bacaan pendalaman
Kasus dan angka yang dibuat untuk latihan adalah simulasi/rekaan; fakta konsep dan sumber dibedakan dalam uraian.
Permintaan berkode A,B,C masuk berurutan. Program model memakai tumpukan sehingga permintaan C keluar lebih dahulu. Pembuat menganggap hasilnya benar karena semua kode masih ada, tetapi petunjuk layanan menjanjikan urutan kedatangan. Masalahnya bukan hilangnya data, melainkan ketidaksesuaian struktur dengan kontrak.
Kelompok membandingkan antrean dan tumpukan di kertas. Mereka menambah D, mengambil dua entri, dan mencatat isi yang tersisa. Daftar langkah memperlihatkan perbedaan yang tidak terlihat dari sekadar jumlah entri. Urutan ternyata bagian penting dari makna data.
Pada tugas lain, mereka menggambar hubungan empat lokasi. Dua jalur mempunyai jumlah sisi sama, tetapi waktu berbeda setelah bobot ditambahkan. Mereka belajar bahwa struktur serta ukuran harus mengikuti pertanyaan. Lebih sedikit langkah, lebih dekat pada gambar, dan lebih cepat di dunia nyata tidak selalu berarti hal yang sama.
Fokus pemeriksaan. Mengapa jumlah entri yang benar belum menjamin perilaku layanan benar?
Tidak semua hubungan berbentuk urutan
Hierarki folder dapat digambarkan sebagai pohon: ada akar dan cabang, tanpa lintasan melingkar dalam model pohon. Hubungan antartempat dapat membentuk graf dengan beberapa jalur. Simpul mewakili objek; sisi mewakili hubungan yang didefinisikan. Arti sisi harus dijelaskan, misalnya terhubung langsung, bukan selalu jarak atau waktu.
Graf memerlukan aturan arah
Dalam graf tak berarah, hubungan A–B dapat dilalui dari kedua arah. Graf berarah memakai panah untuk hubungan yang mempunyai arah tertentu. Jangan menggambar panah hanya untuk hiasan jika maksudnya berbeda. Jaringan rekaan A–B, A–C, B–D, C–D menyediakan dua jalur dari A ke D dengan dua sisi. Tanpa bobot, kita hanya membandingkan banyak sisi, bukan kilometer atau menit.
Jejak kunjungan mencegah pengulangan
Menelusuri jaringan yang memiliki siklus dapat membuat pemeriksaan berulang tanpa akhir jika simpul yang sudah dikunjungi tidak dicatat. Daftar atau set kunjungan membantu menjaga jejak. Untuk kelas ini, gunakan graf kecil di kertas sebelum program. Model tidak dipakai untuk mengakses jaringan komputer atau memindai perangkat lain.
Daftar tetangga pada graf rekaan
graf = {"A": ["B", "C"], "B": ["A", "D"],
"C": ["A", "D"], "D": ["B", "C"]}
print(graf["A"])
print("D" in graf["B"])Keluaran contoh
['B', 'C'] True
Setiap nilai mencantumkan tetangga langsung. Hubungan dua arah ditulis pada kedua simpul; kode tidak melakukan koneksi jaringan.
Telusuri contoh
Sebutkan dua jalur A ke D pada model.
- A–B–D dan A–C–D.
- Keduanya terdiri dari2 sisi.
- Waktu perjalanan belum diketahui tanpa bobot yang sesuai.
Apakah satu simpul yang tergambar dekat pasti lebih cepat dicapai?
- Tidak.
- Posisi diagram bukan skala waktu.
- Periksa arti sisi serta bobot sebelum membandingkan.
Jalur paling sedikit sisi belum tentu tercepat jika bobot berbeda; diagram hubungan bukan peta berskala.
Latihan mandiri
1 Apa beda pohon dan graf umum?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Pohon merupakan struktur terhubung tanpa siklus; graf umum dapat mempunyai siklus dan beberapa jalur.
2 Apa yang harus dijelaskan tentang sisi?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Makna hubungan, arah, dan bobot jika ada.
3 Berapa sisi pada A–B–D?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Dua sisi.
4 Mengapa catatan dikunjungi berguna?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Mencegah pemeriksaan berulang dan membantu penelusuran berhenti.
Perluas pemahamanmu
Tambahkan bobot menit: A–B2, B–D8, A–C4, C–D3. Bandingkan waktu10 dan7 menit; jelaskan perubahan kesimpulan walau banyak sisi sama.
Coba dengan umpan balik
Latihan otomatis membantu pemeriksaan; tuliskan alasan dan langkah untuk membuktikan pemahaman.
1 Tanpa bobot, dua sisi pada jalur menyatakan…
Petunjuk awal
Tentukan informasi, konsep dan bukti yang dibutuhkan.
Pembahasan · buka setelah mencoba
A. jumlah hubungan yang dilalui. Makna ukuran berasal dari model; jumlah sisi bukan otomatis jarak atau waktu.
Praktik dan refleksi
Gambar graf empat simpul dari kasus. Telusuri semua jalur sederhana A ke D dan catat simpul yang sudah dikunjungi.
Penanda pribadi di perangkat ini; bukan nilai atau bukti penguasaan.