LKPD Informatika Kelas 9: Struktur Data Graph: Konsep dan Representasi

INFORMASI UMUM

TUJUAN PEMBELAJARAN

1. Murid dapat menjelaskan konsep struktur data graph beserta komponen-komponennya (simpul/vertex dan sisi/edge) menggunakan contoh nyata seperti peta rute atau jaringan pertemanan.
2. Murid dapat membuat representasi struktur data graph untuk memodelkan hubungan antar data dalam permasalahan sehari-hari, seperti menentukan rute dari satu tempat ke tempat lain.

PETUNJUK UMUM

• Baca setiap instruksi dengan cermat sebelum mulai mengerjakan.
• Kerjakan kegiatan secara berurutan dari Kegiatan 1 hingga Kegiatan 3.
• Kegiatan 1 dikerjakan secara individu, Kegiatan 2 secara berpasangan, dan Kegiatan 3 dalam kelompok kecil (3–4 orang).
• Boleh berdiskusi dengan teman semeja untuk memahami materi, namun jawaban akhir tetap ditulis sendiri kecuali pada bagian diskusi kelompok.
• Gunakan pensil atau pulpen untuk menulis dan menggambar. Boleh menggunakan penggaris untuk membuat diagram yang rapi.
• Jika ada istilah yang belum dipahami, tandai dengan tanda tanya (?) dan tanyakan kepada guru.
• Waktu total pengerjaan adalah 80 menit. Perhatikan estimasi waktu di setiap kegiatan agar kamu bisa menyelesaikan semua bagian.

KEGIATAN

Kegiatan 1: Kenali Graph di Sekitarmu!

Estimasi: 20 menit

Alat & Bahan:

• Pulpen atau pensil
• Penggaris (opsional, untuk rapi)

Petunjuk Pengerjaan:

1. Baca dua situasi di bawah ini dengan seksama.
2. Situasi A: Bayangkan kamu membuka aplikasi media sosial. Kamu mengikuti akun Rina, Rina mengikuti akun Dito, dan Dito juga mengikuti akunmu. Selain itu, kamu dan Rina saling mengikuti satu sama lain.
3. Situasi B: Perhatikan rute angkutan kota berikut — Stasiun → Pasar (2 km), Pasar → Sekolah (1,5 km), Stasiun → Mall (3 km), Mall → Sekolah (2 km), Pasar → Mall (1 km).
4. Jawab pertanyaan 1 sampai 5 secara individu berdasarkan kedua situasi tersebut.
5. Untuk pertanyaan yang meminta gambar/diagram, kerjakan di kotak yang sudah disediakan.

Pertanyaan:

1. Pada Situasi A (jaringan media sosial), siapa saja yang berperan sebagai SIMPUL (vertex)? Tuliskan semua nama yang ada.

2. Masih pada Situasi A, hubungan 'mengikuti' antarpemain diwakili oleh apa dalam struktur graph? Sebutkan istilahnya dan jelaskan dengan satu kalimat.

3. Gambarlah diagram graph Situasi A di kotak di bawah ini! Gunakan lingkaran untuk simpul (tulis nama di dalamnya) dan panah untuk ruas. Perhatikan arah panahnya — apakah satu arah atau dua arah?

4. Perhatikan Situasi B (rute angkot). Isilah tabel berikut untuk setiap ruas (jalur) yang ada. Kolom: Dari | Ke | Jarak (km)

5. Berdasarkan dua situasi di atas, apa perbedaan utama antara graph pada Situasi A (jaringan sosial) dan graph pada Situasi B (rute angkot)? Tuliskan minimal 1 perbedaan.

Jawaban nomor 1, 2, 4, 5 ditulis pada baris yang tersedia di bawah setiap pertanyaan. Nomor 3 digambar di dalam kotak berukuran 10×10 cm yang tersedia.

Kegiatan 2: Detektif Graph: Temukan Rute Terbaik!

Estimasi: 25 menit

Alat & Bahan:

• Pulpen atau pensil
• Penggaris

Petunjuk Pengerjaan:

1. Kerjakan bersama teman sebangkumu (berpasangan).
2. Perhatikan graph rute kota berikut yang sudah digambarkan di LKPD ini:
3. Simpul: Rumah (R), Warung (W), Sekolah (S), Taman (T), Perpustakaan (P).
4. Ruas dan bobotnya: R–W (3 menit), R–T (7 menit), W–S (4 menit), W–T (2 menit), T–S (5 menit), T–P (6 menit), S–P (3 menit).
5. Gambarlah graph ini terlebih dahulu di kotak yang tersedia, baru kemudian jawab pertanyaan 1 sampai 4.
6. Diskusikan setiap jawaban bersama pasanganmu, lalu tulis jawaban bersama di lembar masing-masing.

Pertanyaan:

1. Gambarlah graph rute kota di atas! Gunakan lingkaran untuk simpul dan garis untuk ruas. Tuliskan bobot (waktu tempuh) di samping setiap garis.

2. Temukan SEMUA rute yang mungkin dari Rumah (R) ke Perpustakaan (P)! Tuliskan setiap rute dan hitung total waktunya. (Contoh format: R → W → S → P = 3 + 4 + 3 = 10 menit)

3. Berdasarkan analisismu, rute manakah yang PALING CEPAT dari Rumah ke Perpustakaan? Mengapa struktur data graph membantu kamu menemukan jawaban ini dibandingkan hanya membaca daftar jalur?

4. [Diskusi Berpasangan] Andaikan jalan R–T ditutup karena perbaikan. Bagaimana perubahan ini memengaruhi pilihan rute? Apakah masih ada jalan dari Rumah ke Perpustakaan? Tuliskan hasil diskusimu.

Nomor 1 digambar di kotak 12×12 cm yang tersedia. Nomor 2 ditulis dalam tabel 3 kolom (Rute | Perhitungan | Total Waktu). Nomor 3 dan 4 ditulis dalam paragraf singkat (3–5 kalimat).

Kegiatan 3: Graph Duniamu Sendiri!

Estimasi: 25 menit

Alat & Bahan:

• Pulpen atau pensil warna (opsional, untuk mempercantik diagram)
• Penggaris
• Kertas tambahan jika diperlukan

Petunjuk Pengerjaan:

1. Kerjakan dalam kelompok kecil (3–4 orang).
2. Di kegiatan ini, kalian akan membuat representasi graph berdasarkan situasi nyata yang kalian pilih sendiri.
3. Pilih SATU dari dua tema berikut: (A) Jaringan pertemanan di kelas/grup chat, atau (B) Peta rute dari rumah salah satu anggota kelompok ke sekolah melewati beberapa titik (warung, halte, gang, dll.).
4. Langkah 1: Diskusikan dan tentukan tema yang akan dibuat.
5. Langkah 2: Identifikasi minimal 5 simpul yang relevan dengan temamu.
6. Langkah 3: Identifikasi minimal 6 ruas (hubungan/koneksi) antar simpul tersebut.
7. Langkah 4: Gambarkan graph-nya di kotak yang tersedia.
8. Langkah 5: Jawab pertanyaan analisis 1 sampai 3.
9. Langkah 6: Siapkan 1 perwakilan kelompok untuk mempresentasikan hasilnya dalam 2–3 menit.

Pertanyaan:

1. Tuliskan tema yang dipilih kelompokmu, lalu buat daftar semua SIMPUL dan RUAS yang akan digunakan dalam graphmu. Format: Simpul: [daftar], Ruas: [daftar pasangan simpul].

2. Gambarlah graph yang sudah kalian rancang di atas! Pastikan: (a) setiap simpul diberi label nama, (b) setiap ruas diberi bobot atau arah jika diperlukan, (c) gambar rapi dan mudah dibaca.

3. [Analisis Kelompok] Jawab dua pertanyaan berikut: (a) Apakah ada simpul dalam graphmu yang terhubung ke banyak simpul lain? Apa artinya dalam konteks tema kalian? (b) Bagaimana graph yang kalian buat bisa membantu seseorang yang baru pertama kali mau ke sekolah atau bergabung dengan teman-teman kalian?

Nomor 1 ditulis dalam format daftar bernomor (Simpul 1, 2, dst. dan Ruas 1, 2, dst.). Nomor 2 digambar di kotak besar 15×15 cm yang tersedia. Nomor 3 ditulis dalam 2 paragraf terpisah untuk pertanyaan (a) dan (b).

REFLEKSI

1. Setelah belajar tentang graph hari ini, coba pikirkan: ada berapa 'graph' yang tanpa sadar sudah kamu gunakan dalam kehidupan sehari-hari? Sebutkan minimal satu contoh yang belum dibahas di kelas!

2. Bagian mana dari kegiatan hari ini yang paling menantang bagimu — memahami konsep simpul dan ruas, menggambar diagram, atau menemukan rute terpendek? Apa yang akan kamu lakukan untuk lebih memahami bagian itu?

3. Kalau kamu bisa menambahkan satu fitur baru pada graph rute dari Kegiatan 2 (misalnya: mempertimbangkan kemacetan atau biaya angkot), fitur apa yang akan kamu tambahkan dan mengapa?