Pengantar Teori Graf — cara merepresentasikan lokasi dan rute sebagai titik dan garis, sekaligus pembuka proyek akhir "Peta Jaringan Kota".
Durasi: 120 menitPrasyarat: Modul 3 — Kombinatorika (Pertemuan 9)Tools: kalkulator derajat titik di halaman ini
1
Graf: Titik dan Garis
Coba bayangin peta kota kecil: ada rumah, sekolah, taman, pasar, kantor — masing-masing lokasi itu jadi titik (dalam istilah matematika disebut vertex). Terus, tiap jalan yang menghubungkan dua lokasi jadi garis (disebut edge atau sisi). Gabungan titik-titik dan garis-garis ini namanya graf — alat yang super berguna buat memodelkan jaringan apa aja: peta jalan, pertemanan medsos, jaringan komputer, sampai skema kelistrikan.
Ada beberapa jenis graf yang perlu kamu kenal:
Graf tak berarah — jalannya dua arah, jadi rute A-B sama saja dengan B-A. Ini yang bakal kita pakai terus di modul ini.
Graf berarah — jalannya satu arah, digambar pakai panah (misalnya jalan satu arah di kota).
Graf berbobot — tiap garis punya "biaya" tambahan, misalnya jarak dalam km atau waktu tempuh dalam menit.
Nah, mulai pertemuan ini sampai Pertemuan 12, kita bakal bangun satu proyek akhir bareng-bareng: Peta Jaringan Kota — sebuah graf kecil berisi 5 lokasi dan 6 rute penghubung, yang bakal kita analisis derajatnya (hari ini), cek jalur Euler dan pohon merentangnya (Pertemuan 11), lalu warnai petanya (Pertemuan 12).
Istilah penting: graf ditulis G = (V, E), di mana V adalah himpunan vertex (titik) dan E adalah himpunan edge (sisi/garis penghubung).
2
Istilah Dasar Graf
Sebelum masuk ke kalkulator, kenalan dulu sama 4 istilah yang bakal sering muncul:
Titik
Vertex
Objek atau lokasi dalam graf — biasanya digambar sebagai lingkaran atau titik kecil.
Garis
Edge (Sisi)
Hubungan atau rute antara dua vertex — digambar sebagai garis penghubung di antara keduanya.
Struktur Data
Adjacency List
Cara komputer menyimpan graf: tiap vertex punya daftar vertex tetangga yang terhubung langsung dengannya.
Ukuran Koneksi
Derajat (Degree)
Banyaknya sisi yang terhubung langsung ke suatu vertex — makin banyak "jalan keluar-masuk", makin tinggi derajatnya.
3
Coba Langsung: Kalkulator Graf — Derajat Titik
Ini dia peta jaringan kota kita: A (Rumah), B (Sekolah), C (Taman), D (Pasar), E (Kantor), dihubungkan oleh 6 rute. Klik Hitung Derajat buat lihat berapa banyak rute yang terhubung ke tiap lokasi.
Kalkulator Graf: Derajat Titik
Klik Hitung Derajat untuk melihat hasilnya…
Penting: ingat contoh Peta Jaringan Kota di atas — kita akan pakai graf yang SAMA di Pertemuan 11 dan 12 untuk proyek akhir, jadi simpan baik-baik hasil derajatnya!
4
Latihan Mandiri / Mulai Proyek Akhir
Sebelum lanjut ke Pertemuan 11, coba kerjakan sendiri:
Rancang sendiri 5-6 lokasi dan rute penghubungnya DI KERTAS (boleh beda dari contoh di kalkulator) — ini bakal jadi "Peta Jaringan Kota" versimu sendiri.
Masukkan rancanganmu ke kalkulator di atas untuk verifikasi derajat tiap lokasi.
Simpan rancangan ini baik-baik — kamu akan pakai lagi graf yang sama persis di Pertemuan 11 (cek Euler & pohon merentang) dan Pertemuan 12 (pewarnaan graf) sebagai bagian dari proyek akhir.
5
Cek Pemahaman
1. Dalam graf, "vertex" (titik) merepresentasikan...
Vertex adalah "benda"-nya (lokasi, orang, dsb), sedangkan edge adalah hubungan antar vertex.
2. Graf tak berarah berbeda dari graf berarah karena...
Di graf tak berarah, jalan dianggap dua arah; di graf berarah, arah panahnya menentukan dari mana ke mana.
3. Derajat suatu titik pada graf tak berarah dihitung sebagai...
Derajat menghitung berapa banyak "koneksi langsung" yang dimiliki satu titik.
4. Pada graf dengan sisi A-B, B-C, C-D, D-E, E-A, A-C (Peta Jaringan Kota kita), berapa derajat titik A?
A muncul di tiga sisi: A-B, E-A, dan A-C — jadi derajatnya 3.
5. Jumlah seluruh derajat titik pada suatu graf selalu...
Tiap sisi punya 2 ujung, dan tiap ujung menambah 1 derajat ke titik itu — jadi total derajat = 2 × banyak sisi (pada Peta Jaringan Kota kita: 2×6=12).
Skor: 0 / 5 terjawab benar
6
Ringkasan Pertemuan 10
Graf terdiri dari vertex (titik/lokasi) dan edge (sisi/rute penghubung) — ditulis G = (V, E).
Derajat suatu titik = banyaknya sisi yang terhubung langsung ke titik itu. Total derajat seluruh graf selalu 2 × banyak sisi.
Peta Jaringan Kota kita (A,B,C,D,E dengan rute A-B,B-C,C-D,D-E,E-A,A-C) punya derajat A=3, B=2, C=3, D=2, E=2 — akan dipakai terus sampai Pertemuan 12.
Selanjutnya
Di Pertemuan 11, kita pakai derajat yang sudah dihitung hari ini untuk cek apakah Peta Jaringan Kota kita punya lintasan/sirkuit Euler dan mencari pohon merentangnya.