Matdis — Bab 9

Teori Graf

Pemodelan matematis hubungan antar objek — dari jaringan komputer dan rute optimal, hingga penjadwalan, pewarnaan, dan pohon rentang minimum.

Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 9. — Rosen, Discrete Mathematics, 8th ed., Ch. 10. — CLRS, Introduction to Algorithms, 4th ed., Ch. 22-25.

Mengapa Teori Graf?

Graf adalah bahasa universal untuk hubungan. Euler memulai teori ini pada 1736 dengan masalah Jembatan Königsberg — bisakah seseorang menyeberangi ke-7 jembatan tepat sekali? Jawabannya melahirkan konsep Euler circuit.

Hari ini, setiap aspek dunia digital menggunakan graf: routing internet (Dijkstra), social network (community detection), compiler (control-flow graph), database (query planning), dan sistem rekomendasi (graf bipartit pengguna–item).

1. Definisi dan Terminologi

Definisi (Graf)

Graf G = (V, E) terdiri dari V = himpunan berhingga simpul (vertex/node) dan E = himpunan sisi (edge) di mana setiap sisi menghubungkan dua simpul.

Simpul (vertex, v): titik/node graf.

Sisi (edge, e): hubungan antara dua simpul.

Derajat deg(v): jumlah sisi yang incident ke v.

Handshaking Lemma: Σ deg(v) = 2|E|

Lintasan (path): urutan simpul v₁,v₂,...,vₖ tanpa simpul berulang.

Sirkuit/Siklus: lintasan yang kembali ke simpul awal.

Graf terhubung: ada lintasan antara setiap pasang simpul.

Komponen terhubung: subgraf terhubung maksimal.

Analogi: Peta Kota

Simpul = kota, sisi = jalan. Graf berbobot = jarak antar kota. Lintasan = rute perjalanan. Lintasan terpendek = rute paling efisien. Sirkuit Euler = tour yang melewati semua jalan tepat sekali. Sirkuit Hamilton = tour yang mengunjungi semua kota tepat sekali (masalah TSP yang NP-hard).

2. Jenis-Jenis Graf

Eksplorasi: Tipe Graf

Graf Tak Berarah

Sisi tidak memiliki arah. Hubungan simetris: jika u-v ada, maka v-u ada. Degree = jumlah sisi incident. Handshaking lemma: Σdeg(v)=2|E|.

Contoh nyata: Internet connectivity, friendship graph

Jenis Graf	Sisi Ganda?	Self-loop?	Berarah?	Keterangan
Graf Sederhana	Tidak	Tidak	Tidak	Paling umum
Multigraf	Ya	Tidak	Tidak	Multi-edge antar simpul
Pseudograf	Ya	Ya	Tidak	Untuk loop
Graf Berarah	Tidak	Tidak	Ya	Digraph, DAG
Graf Berbobot	-	-	Opsional	Sisi memiliki bobot/biaya

3. Visualisasi Graf

Graf Berbobot dengan Animasi BFS

Graf berbobot 5 simpul. Sisi hijau = edge yang dipilih Dijkstra dari A. Angka = bobot sisi.

4. Representasi Graf

Matriks Ketetanggaan (Adjacency Matrix)

A[i][j] = 1 jika ada sisi dari i ke j, 0 jika tidak. Graf tak-berarah: matriks simetris.

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0

Space O(V²). Query edge O(1). Bagus untuk dense graph.

Adjacency List

Setiap simpul menyimpan daftar tetangganya. Efisien untuk sparse graph.

A: [B(w=4), C(w=2)]

B: [A(w=4), D(w=5)]

C: [A(w=2), D(w=8), E(w=10)]

D: [B(w=5), C(w=8), E(w=2)]

E: [C(w=10), D(w=2)]

Space O(V+E). Query edge O(degree). Bagus untuk sparse graph (jaringan dunia nyata).

5. Sirkuit Euler & Hamilton

Euler (Sisi)

Euler circuit: Melewati setiap sisi tepat sekali, kembali ke awal.

Syarat: Graf terhubung dan SEMUA simpul berderajat genap.

Euler path: Tepat 2 simpul berderajat ganjil (menjadi titik awal dan akhir).

Algoritma Hierholzer O(E) untuk mencari Euler circuit.

Hamilton (Simpul)

Hamilton circuit: Melewati setiap simpul tepat sekali, kembali ke awal.

NP-complete problem — tidak ada kondisi perlu dan cukup sederhana.

Dirac (1952): Jika deg(v) ≥ n/2 untuk semua v, ada Hamilton circuit.

TSP (Travelling Salesman) = Hamilton dengan minimisasi bobot. NP-hard.

6. Lintasan Terpendek: Algoritma Dijkstra

Algoritma Dijkstra O((V+E) log V)

Inisialisasi: dist[s] = 0, dist[v] = ∞ untuk semua v ≠ s.
Masukkan semua simpul ke priority queue (min-heap berdasarkan dist).
Ambil simpul u dengan dist minimum dari queue.
Untuk setiap tetangga v dari u: jika dist[u] + w(u,v) < dist[v], perbarui dist[v] dan prev[v] = u.
Ulangi langkah 3-4 sampai queue kosong.
Rekonstruksi jalur menggunakan prev[].

Catatan: hanya untuk graf berbobot non-negatif. Untuk negatif: gunakan Bellman-Ford O(VE).

Demo Dijkstra Interaktif (Graf A-B-C-D-E)

Mulai dari:

Sisi: A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, C-E:10, D-E:2

via: -

via: C

via: A

via: B

via: D

7. Pewarnaan Graf

Definisi (Pewarnaan Graf)

Pewarnaan simpul mengassign warna ke setiap simpul sehingga tidak ada dua simpul bertetangga memiliki warna yang sama. Bilangan kromatik χ(G) = jumlah warna minimum yang diperlukan.

χ(Kₙ) = n (graf lengkap n simpul: tiap simpul butuh warna beda)

χ(Pohon) = 2 (pohon adalah bipartit)

χ(Graf bipartit) = 2 (jika tidak kosong)

4-Color Theorem (Appel-Haken 1976): Setiap peta planar dapat diwarnai dengan 4 warna — dibuktikan dengan bantuan komputer.

8. Graf Planar dan Teorema Kuratowski

Graf Planar

Graf yang dapat digambar di bidang tanpa sisi bersilangan. Contoh: K₄ planar, K₅ tidak planar.

Formula Euler: Untuk graf planar terhubung: V - E + F = 2 (F = jumlah muka/region, termasuk muka tak hingga).

Akibat: E ≤ 3V - 6 untuk graf planar sederhana (V ≥ 3).

Teorema Kuratowski (1930)

Graf G tidak planar jika dan hanya jika G mengandung subdivisi K₅ atau K₃,₃ sebagai subgraf.

K₅: Graf lengkap 5 simpul (tidak planar).

K₃,₃: Graf bipartit lengkap (masalah "3 rumah, 3 utilitas" — tidak planar).

9. Isomorfisma Graf

Definisi (Isomorfisma)

Dua graf G₁ = (V₁, E₁) dan G₂ = (V₂, E₂) isomorfis jika ada bijeksi f: V₁ → V₂ sehingga (u,v) ∈ E₁ ⟺ (f(u), f(v)) ∈ E₂. Pada dasarnya, kedua graf "memiliki struktur yang sama" hanya labeling simpul yang berbeda.

Graph Isomorphism Problem: Menentukan apakah dua graf isomorfis. Tidak diketahui apakah di P, NP-complete, atau intermediate. Implikasi besar di kriptografi berbasis struktur graf.

Koneksi ke Ilmu Komputer

Perutean Jaringan: Internet adalah graf raksasa dengan router sebagai simpul. Protokol OSPF menjalankan algoritma Dijkstra untuk mencari lintasan terpendek, sementara BGP bekerja pada graf antar-jaringan.

Penjadwalan & Dependensi: "Modul A harus dikompilasi sebelum B" membentuk graf berarah asiklik (DAG). Pengurutan topologis atasnya menentukan urutan build pada Make, npm, dan Maven. Bila ditemukan siklus, artinya ada dependensi melingkar.

Pewarnaan Graf: Alokasi register pada kompilator, penjadwalan ujian agar tidak bentrok, dan pengalokasian frekuensi BTS semuanya adalah masalah pewarnaan graf.

Pohon Rentang Minimum: Algoritma Kruskal dan Prim dipakai untuk merancang jaringan listrik, kabel serat optik, dan klasterisasi data dengan biaya total seminimal mungkin.

Penelusuran Graf: BFS mencari jarak terpendek dalam graf tak berbobot (misalnya derajat pertemanan di media sosial), sedangkan DFS dipakai untuk deteksi siklus dan komponen terhubung kuat.

10. Contoh Soal & Pembahasan

Soal 1: Handshaking Lemma

Graf G memiliki derajat simpul: 2, 4, 2, 4, 2. Berapa banyak sisi G?

Soal 2: Euler Circuit

Apakah graf dengan derajat {2, 4, 2, 4, 2} memiliki Euler circuit?

Soal 3: Dijkstra Manual

Pada graf demo di atas (A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, C-E:10, D-E:2), tentukan lintasan terpendek dari A ke E.

Soal 4: Bilangan Kromatik

Tentukan χ(K₅).

Soal 5: Formula Euler (Planaritas)

Graf planar terhubung dengan V=6, E=9. Berapa banyak muka (F)?

Soal 6: Graf Bipartit

Apakah graf siklus C₆ bipartit? Bagaimana dengan C₅?

← Aljabar Boolean Pohon (Trees) →

Munir, R. (2020). Matematika Diskrit, Edisi 7, Penerbit Informatika ITB, Bab 9. — Rosen, K. H. (2019). Discrete Mathematics and Its Applications, 8th ed., Ch. 10. — Cormen, T. H. et al. (2022). Introduction to Algorithms, 4th ed., MIT Press, Ch. 22-25.

Bank Soal Multi-Kompleksitas & Kasus Terintegrasi

Referensi: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 9 — Teori Graf.

MUDAH Soal Dasar Graf

G-M1: Degree Sequence

Graf G memiliki 5 vertex dengan adjacency: v1-v2, v1-v3, v2-v3, v2-v4, v3-v5. Tentukan degree tiap vertex dan verifikasi Handshaking Lemma.

G-M2: Walk, Trail, Path

Pada graf K₄ (complete graph 4 vertex), apakah urutan v1-v2-v3-v4-v1-v3 merupakan walk, trail, atau path? Berikan alasan.

G-M3: Adjacency Matrix

Tulis adjacency matrix untuk graf segitiga (C₃ = triangle). Berapa jumlah walk panjang 2 dari v1 ke v1? (Petunjuk: (A²)[1,1])

G-M4: Konektivitas Graf

Apakah graf berikut terhubung (connected)? V={1,2,3,4,5}, E={(1,2),(1,3),(4,5)}. Identifikasi komponen terhubung.

SEDANG Lintasan Euler & Hamilton

G-S1: Teorema Euler (Circuit & Trail)

Graf G: V={a,b,c,d}, E={(a,b),(a,c),(b,c),(b,d),(c,d)}. Apakah ada Euler circuit? Apakah ada Euler trail?

G-S2: Konstruksi Euler Circuit

K₄ (complete graph 4 vertex) — apakah ada Euler circuit? Jika ada, temukan satu lintasannya. Jika tidak, berapa sisi yang harus ditambah/hapus?

G-S3: Hamilton Path vs Circuit

Graf path P₅ = v1-v2-v3-v4-v5. Apakah ada Hamiltonian path? Hamiltonian circuit? Gunakan Ore's theorem untuk graf lain jika perlu.

G-S4: Planar Graph & Euler's Formula

Verifikasi K₄ adalah planar menggunakan rumus Euler: V − E + F = 2. Gambarkan K₄ planar (tanpa sisi bersilang).

SULIT Algoritma Graf Kompleks

G-H1: Euler Circuit dengan Hierholzer

Graf: V={a,b,c,d,e}, E={(a,b),(a,c),(b,c),(b,d),(c,d),(c,e),(d,e)}. Semua degree genap? Jika ya, temukan Euler circuit menggunakan Hierholzer algorithm.

G-H2: Hamilton + TSP (Weighted)

Graf berbobot K₄: d(v1,v2)=10, d(v1,v3)=15, d(v1,v4)=20, d(v2,v3)=35, d(v2,v4)=25, d(v3,v4)=30. Temukan Hamiltonian circuit dengan bobot minimum (brute force).

G-H3: Graph Coloring & Chromatic Number

Graf siklus C₅ (pentagon). Tentukan chromatic number χ(C₅). Apakah C₅ bipartit? Bandingkan dengan C₄.

TERINTEGRASI Graf: Euler + Bobot, Hamilton + TSP, Planaritas + Pewarnaan

G-T1: Euler Circuit + Bobot — Chinese Postman Problem

Seorang kurir harus melewati semua jalan (sisi) tepat sekali dan kembali ke start. Graf berbobot: v1-v2(3), v2-v3(4), v3-v4(2), v4-v1(5), v1-v3(6). Apakah Eulerian? Jika tidak, temukan lintasan minimum yang melewati semua sisi.

G-T2: Hamilton + Planaritas — Network Topology

Dalam jaringan peer-to-peer, n=6 simpul saling terhubung penuh membentuk K₆. (a) Apakah K₆ planar? (b) Apakah K₆ Hamiltonian? (c) Berapa bilangan kromatik χ(K₆)?

G-T3: Graf + Kriptografi — Zero-Knowledge Proof & Graph Isomorphism

Graph Isomorphism Problem (GIP): dua graf G₁ dan G₂ diberikan. Verifier ingin membuktikan prover mengetahui isomorphism tanpa mengungkapkan isomorphism-nya. Jelaskan protokol ZK-proof berbasis GIP dan kompleksitas GIP.