Saat anak SD menggambar titik dan garis untuk menghubungkan rumah teman, tanpa sadar mereka sudah menyentuh konsep teori graf. Di SMP dan SMA, konsep ini mulai muncul dalam bentuk yang lebih abstrak, tetapi sering tidak dibahas mendalam.
Padahal, teori graf adalah dasar dari:
-
Google Maps
-
Media sosial
-
Jaringan internet
-
Sistem transportasi
-
Algoritma komputer
Materi ini sangat relevan dengan dunia nyata, namun jarang dijelaskan runtut dari dasar hingga lanjutan. Mari kita bahas secara lengkap.
Pengertian Teori Graf
Teori graf adalah cabang matematika yang mempelajari hubungan antar objek menggunakan titik dan garis.
Dalam graf:
-
Titik disebut vertex (simpul)
-
Garis disebut edge (sisi)
Graf digunakan untuk menggambarkan hubungan atau koneksi.
Contoh sederhana:
Sekolah memiliki 4 siswa yang saling berteman. Hubungan pertemanan bisa digambarkan dengan titik dan garis.
Konsep Dasar Di Kelas 3–4 SD: Menghubungkan Titik
Soal sederhana:
Ada 3 rumah: A, B, dan C.
Berapa banyak jalan yang bisa menghubungkan semuanya?
Siswa biasanya menggambar titik dan garis. Itu sudah termasuk graf sederhana.
Di tahap ini, anak belajar:
-
Menghubungkan titik
-
Menghitung jumlah garis
-
Melihat pola hubungan
Jenis Graf Di SMP
Di SMP, graf mulai diklasifikasikan:
-
Graf sederhana
-
Graf berarah
-
Graf tak berarah
Graf berarah memiliki panah (misalnya hubungan follower di media sosial).
Graf tak berarah tidak memiliki arah (misalnya hubungan pertemanan).
Derajat Suatu Titik
Derajat titik adalah jumlah garis yang terhubung pada titik tersebut.
Contoh:
Jika titik A terhubung ke 3 titik lain, maka derajatnya 3.
Soal:
Jika suatu graf memiliki 5 titik dan setiap titik terhubung ke 2 titik lain, berapa jumlah sisi?
Gunakan rumus:
Jumlah derajat = 2 × jumlah sisi
Lintasan Dan Sirkuit
Lintasan adalah jalur dari satu titik ke titik lain.
Sirkuit adalah lintasan yang kembali ke titik awal.
Contoh dalam kehidupan:
Rute pengantar paket yang kembali ke gudang adalah sirkuit.
Graf Euler Di SMA
Graf Euler adalah graf yang bisa dilalui semua sisinya tepat satu kali.
Syarat graf memiliki lintasan Euler:
-
Maksimal dua titik berderajat ganjil.
Jika semua titik berderajat genap → memiliki sirkuit Euler.
Contoh Soal Graf Euler
Suatu graf memiliki derajat titik:
2, 2, 4, 4
Apakah memiliki sirkuit Euler?
Jawaban:
Ya, karena semua genap.
Graf Hamilton
Berbeda dengan Euler.
Graf Hamilton adalah graf yang melewati semua titik tepat satu kali.
Tidak ada rumus sederhana seperti Euler. Biasanya diuji dengan analisis.
Graf Berbobot Dan Aplikasinya
Graf berbobot memiliki nilai pada setiap sisi.
Contoh:
Jarak antar kota:
A–B = 5 km
B–C = 7 km
Untuk mencari jalur terpendek digunakan algoritma (misalnya Dijkstra di tingkat lanjut).
Ini dasar sistem navigasi modern.
Contoh Soal Jalur Terpendek
Jika:
A–B = 3
B–C = 4
A–C = 10
Jalur terpendek dari A ke C?
A → B → C = 7
Lebih pendek dari 10.
Cara Mudah Memahami Teori Graf
-
Anggap graf seperti peta
-
Titik = lokasi
-
Garis = jalan
-
Hitung derajat untuk soal Euler
-
Untuk jalur terpendek, jumlahkan alternatif
Belajar graf akan terasa menyenangkan jika divisualisasikan.
Latihan Soal
Soal 1
Sebuah graf memiliki 4 titik masing-masing berderajat 3. Apakah mungkin?
Soal 2
Jika jumlah derajat seluruh titik adalah 12, berapa jumlah sisi?
Soal 3
Apakah graf dengan derajat 1, 2, 3, 2 memiliki lintasan Euler?
Soal 4
Jika A–B = 5 dan B–C = 6 dan A–C = 8, jalur terpendek dari A ke C?
Pembahasan Latihan
Soal 1:
Tidak mungkin, karena jumlah derajat harus genap.
Soal 2:
Jumlah sisi = 12 / 2 = 6
Soal 3:
Ada dua titik ganjil → memiliki lintasan Euler (bukan sirkuit).
Soal 4:
Bandingkan:
A–C langsung = 8
A–B–C = 11
Jawaban: 8
FAQ Seputar Teori Graf
Apakah teori graf sulit?
Tidak, jika dipahami sebagai hubungan titik dan garis.
Apa manfaat teori graf di kehidupan nyata?
Digunakan dalam transportasi, jaringan sosial, dan teknologi.
Apa beda graf Euler dan Hamilton?
Euler fokus pada sisi, Hamilton fokus pada titik.
Mengapa jumlah derajat harus genap?
Karena setiap sisi dihitung dua kali.
Apakah teori graf masuk ujian nasional?
Sering muncul dalam bentuk soal aplikasi dan logika.
baca artikel sebelumnya: