Petualangan Teori Graf - Game Edukasi Struktur Diskrit

Materi Belajar Interaktif

Pelajari teori graf dengan analogi dunia nyata yang mudah dipahami!

Definisi Graf

Graf adalah kumpulan simpul (vertex) dan sisi (edge) yang menghubungkan simpul-simpul tersebut.

Analogi Dunia Nyata: Bayangkan peta kota! Setiap kota adalah simpul, dan jalanan yang menghubungkan kota-kota adalah sisi.

Jenis-Jenis Graf

Graf Tak Berarah: Sisi dapat dilalui dua arah.

Analogi: Seperti jalan dua arah di kota, bisa bolak-balik.

Graf Berarah: Sisi hanya bisa dilalui satu arah.

Analogi: Seperti jalan satu arah, hanya boleh lewat dari satu sisi.

Graf Sederhana vs Tak Sederhana:

Analogi: Graf Tak Sederhana itu seperti jalan yang punya "flyover putar balik" (gelang/loop) atau ada dua jalan berbeda untuk ke tujuan yang sama (sisi ganda).

Terminologi Penting

Bertetangga & Bersisian:

Analogi: Tetangga itu kota sebelah, bersisian itu jalan yang nempel di kota itu.

Simpul Terpencil:

Analogi: Kota di tengah pulau tanpa jalan akses.

Graf Kosong:

Analogi: Peta yang cuma ada nama kota tapi belum dibangun jalan.

Derajat:

Analogi: Jumlah jalan yang terhubung ke satu kota.

Lintasan (Path) vs Sirkuit/Siklus:

Analogi: Lintasan itu perjalanan dari A ke B. Sirkuit itu jalan-jalan yang balik lagi ke rumah (A ke A).

Pohon (Tree):

Analogi: Jaringan jalan yang tidak memutar (tidak ada sirkuit), ibarat struktur folder di komputer atau silsilah keluarga.

Representasi Graf

Komputer tidak melihat gambar graf, tapi melihat angka-angka.

Matriks Ketetanggaan: Tabel berisi 0 dan 1 (Biner).

Analogi: 1 artinya "ada jalan", 0 artinya "buntu/tidak terhubung".

Matriks Bersisian & Senarai Ketetanggaan:

Analogi: Cara lain mencatat rute perjalanan, seperti daftar kota yang saling terhubung.

Graf Isomorfik

Dua graf yang secara struktural sama tetapi bentuk visualnya berbeda.

Analogi: Ibarat dua jaring laba-laba yang bentuknya beda saat ditarik, tapi jumlah benang dan sambungannya sebenarnya sama persis.

Graf Planar

Graf yang dapat digambarkan pada bidang datar tanpa sisi-sisi yang saling berpotongan.

Analogi: Ibarat mendesain jalur di papan sirkuit (PCB) atau jalan layang dimana kabel/jalan tidak boleh saling bertabrakan/berpotongan di satu titik datar.

Euler vs Hamilton

Lintasan Euler: Harus melewati SEMUA JALAN (Sisi) tepat satu kali.

Analogi: Ibarat "Tukang Pos" yang harus melewati semua jalan di kompleks tepat satu kali untuk mengantar surat.

Lintasan Hamilton: Harus mengunjungi SEMUA KOTA (Simpul) tepat satu kali.

Analogi: Ibarat "Kurir Paket" atau Pedagang Keliling yang harus mengunjungi semua toko/kota tepat satu kali untuk mengantar barang.

Visualisasi Graf & Contoh Penerapan

Lihat contoh-contoh graf dan bagaimana teori graf diterapkan dalam kehidupan nyata!

Graf Sederhana

Graf sederhana dengan 5 simpul dan 5 sisi. Tidak ada gelang atau sisi ganda.

Graf Berarah

Graf berarah dengan sisi memiliki arah tertentu. Digunakan untuk merepresentasikan hubungan satu arah.

Pohon (Tree)

Struktur pohon dengan simpul root dan cabang-cabang. Tidak ada sirkuit, digunakan untuk hierarki.

Graf Planar

Graf planar dapat digambar tanpa sisi yang saling berpotongan. Penting dalam desain papan sirkuit.

Graf Isomorfik

Dua graf isomorfik memiliki struktur yang sama meski bentuk visual berbeda. A↔1, B↔2, C↔3, D↔4, E↔5.

Lintasan Euler

Lintasan Euler melewati semua sisi tepat satu kali. Contoh: A→E→B→D→E→C (melewati semua 6 sisi).

Lintasan Hamilton

Lintasan Hamilton mengunjungi semua simpul tepat satu kali. Contoh: 1→2→3→4→1 (mengunjungi semua 5 simpul).

Jaringan Sosial

Facebook, Instagram, Twitter menggunakan graf untuk merepresentasikan hubungan pertemanan. Setiap user adalah simpul, dan hubungan pertemanan adalah sisi.

Jenis Graf: Graf tak berarah (pertemanan biasanya timbal balik)

Peta & Navigasi

Google Maps, Waze menggunakan graf untuk mencari rute terpendek. Persimpangan adalah simpul, jalan adalah sisi dengan bobot (jarak/waktu).

Algoritma: Dijkstra untuk mencari jalur terpendek

Rancangan Sirkuit

Desain PCB (Printed Circuit Board) menggunakan graf planar untuk memastikan jalur tidak saling bersilangan.

Konsep: Graf planar untuk menghindari short circuit

Struktur Data

Basis data menggunakan pohon (B-tree, Binary Tree) untuk indexing dan pencarian efisien.

Contoh: Struktur folder, organisasi file, silsilah keluarga

Kecerdasan Buatan

Jaringan saraf tiruan (Neural Network) adalah graf berarah dengan bobot pada sisi-sisinya.

Aplikasi: Pengenalan gambar, terjemahan bahasa, rekomendasi

Logistik & Distribusi

Masalah Traveling Salesman (TSP) menggunakan graf untuk mencari rute terpendek mengunjungi semua kota.

Optimasi: Menghemat waktu dan biaya pengiriman

Kuis Interaktif

Uji pemahamanmu dengan kuis berikut!

Skor: 0/20 Progress: 0/20

Himpunan simpul-simpul yang dihubungkan oleh sisi sisi disebut...

a Graf

b Pohon

c Vertex

d edges

e node

Graf yang tidak mengandung gelang maupun sisi ganda disebut graf...

a Berhingga

b Sederhana

c Berarah

d Tak sederhana

e Tak berhingga

Dalam pengujian program kita menerapkan jenis graf...

a Sederhana

b Tak berarah

c Berarah

d Tak sederhana

e Tak berhingga

Lintasan elementer dengan simpul awal sama dengan simpul akhir disebut...

a Derajat

b Terhubung

c Simpul terpencil

d Siklus

e Pohon

Jumlah sisi pada graf lengkap dirumuskan dengan...

a n-1

b (n-1)/2

c nr/2

d 2n

e n(n-1)/2

Suatu graf dimana simpul tidak boleh kosong tetapi garis atau sisi boleh kosong terminologi graf...

a simpul terpencil

b graf kosong

c derajat

d lintasan

e pohon

Simpul yang tidak bersisian dengan simpul lainnya merupakan terminologi graf...

a simpul terpencil

b graf kosong

c derajat

d lintasan

e pohon

Jumlah sisi pada sebuah simpul dalam terminologi graf disebut...

a graf terpencil

b graf kosong

c derajat

d lintasan

e pohon

Rangkaian sisi yang menghubungkan dari simpul awal hingga simpul akhir terminologi graf...

a graf terpencil

b graf kosong

c derajat

d lintasan

e pohon

Graf dimana sisi-sisinya hanya berupa percabangan tidak membentuk lintasan tertutup atau sirkuit terminologi graf...

a graf terpencil

b graf kosong

c derajat

d lintasan

e pohon

Untuk merepresentasikan graf ada ... cara

a 1

b 2

c 3

d 4

e 5

Dua buah graf sama dengan bentuk yang berbeda disebut graf...

a Isomorfik

b Dual

c Euler

d Hamilton

e Planar

Untuk menyatakan jumlah wilayah dalam graf dinotasikan dengan...

a n

b f

c e

d s

e r

Lintasan atau sirkuit yang melalui sisi-sisi graf tepat satu kali disebut...

a Isomorfik

b Dual

c Planar

d Euler

e Hamilton

Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut graf...

a Isomorfik

b Dual

c Planar

d Euler

e Hamilton

Lintasan yang melalui sisi-sisi dalam graf tepat satu kali disebut...

a Lintasan euler

b Sirkuit euler

c Lintasan Hamilton

d Sirkuit Hamilton

e Pohon

Lintasan yang melalui sisi-sisi dalam graf tepat satu kali kembali ke simpul awal (membentuk lintasan tertutup) disebut...

a Lintasan euler

b Sirkuit euler

c Lintasan Hamilton

d Sirkuit Hamilton

e Pohon

Lintasan yang melalui simpul dalam graf tepat satu kali disebut...

a Lintasan euler

b Sirkuit euler

c Lintasan Hamilton

d Sirkuit Hamilton

e Pohon

Lintasan yang melalui simpul dalam graf tepat satu kali dan kembali pada simpul awal (membentuk lintasan tertutup) disebut...

a Lintasan euler

b Sirkuit euler

c Lintasan Hamilton

d Sirkuit Hamilton

e Pohon

Dalam representasi graf menggunakan jenis bilangan...

a Asli

b Biner

c Oktal

d Heksa

e Cacah

Mulai Kuis!

Pilih jawaban untuk melihat hasil