Definisi Graf
Graf adalah struktur matematika yang terdiri dari sekumpulan simpul (atau vertex) dan sekumpulan sisi (atau edge) yang menghubungkan pasangan simpul. Secara formal, sebuah graf tak berarah dapat dituliskan sebagai G = (V, E) dimana V adalah himpunan simpul dan E adalah himpunan sisi, masingmasing sisi merupakan pasangan tidak berurutan {u, v} dengan u, v V. Jika sisi memiliki arah, graf disebut graf berarah (digraph) dan setiap sisi ditulis sebagai ordered pair (u, v).
Jenisjenis Graf
Graf Tak Berarah vs Berarah
Graf tak berarah tidak memperhatikan urutan simpul pada sisi, sedangkan graf berarah memperlakukan (u, v) dan (v, u) sebagai sisi yang berbeda.
Graf Sederhana
Graf sederhana tidak mengizinkan loop (sisi yang menghubungkan simpul dengan dirinya sendiri) dan tidak ada multiple edges (lebih dari satu sisi antara dua simpul).
Graf Berat
Setiap sisi dapat memiliki nilai numerik yang disebut berat. Berat biasanya mewakili jarak, biaya, atau kapasitas.
Graf Bipartit
Simpul dapat dibagi menjadi dua himpunan U dan V sehingga setiap sisi menghubungkan satu simpul dari U ke satu simpul dari V. Contoh klasik adalah graf pencocokan (matching).
Graf Planar
Graf dapat digambar di bidang tanpa ada sisi yang saling bersilangan. Teorema Kuratowski memberikan karakterisasi graf planar.
Graf Pohon
Pohon adalah graf bersambung yang tidak mengandung siklus. Pohon memiliki |V| - 1 sisi.
Representasi Graf
Ada dua cara utama untuk menyimpan graf dalam memori komputer.
Matrix Adjacent
Matrix n n dimana n = |V|. Elemen A[i][j] bernilai 1 (atau berat) bila terdapat sisi antara simpul i dan j, selain itu 0.
List Adjacent
Setiap simpul menyimpan daftar semua tetangganya. Representasi ini lebih efisien untuk graf jarang (sparse).
A: B CB: A DC: A DD: B C Edge List
Daftar berisi semua sisi sebagai pasangan simpul. Sangat sederhana, cocok untuk input file.
Algoritma Penting dalam Teori Graf
Pencarian Jalur
- DFS (DepthFirst Search) menelusuri graf secara mendalam dulu, cocok untuk menemukan komponen terhubung, siklus, topological order.
- BFS (BreadthFirst Search) menelusuri lapisan demi lapisan, memberikan jarak terpendek pada graf tak berberat.
Jarak Terpendek
- Dijkstra graf berberat nonnegatif, kompleksitas
O((V+E) log V)dengan heap. - BellmanFord menangani sisi dengan berat negatif, mendeteksi siklus negatif.
- FloydWarshall semuapasangsemua,
O(V), berguna untuk graf kecil.
Minimum Spanning Tree (MST)
- Prim memulai dari satu simpul, menambah sisi terdekat secara iteratif.
- Kruskal mengurutkan semua sisi dan menambahkannya bila tidak membentuk siklus (unionfind).
Aliran Maksimum
Model jaringan transportasi atau komunikasi. Algoritma klasik:
- FordFulkerson (augmenting path)
- EdmondsKarp BFS untuk jalur augmentasi,
O(VE) - Dinic level graph + blocking flow,
O(VE)pada umumnya.
Pencocokan Bipartit
Algoritma HopcroftKarp menemukan pencocokan maksimum pada graf bipartit dengan kompleksitas O(VE).
Aplikasi Teori Graf
Jaringan Komputer
Routing, penentuan jalur terpendek, desain jaringan, dan deteksi loop pada protokol.
Transportasi
Perencanaan rute kendaraan, penjadwalan kereta, serta optimasi logistik (Vehicle Routing Problem).
Ilmu Sosial
Analisis jaringan sosial, pengaruh, komunitas, serta penyebaran informasi atau penyakit.
Bioinformatika
Representasi protein sebagai graf, pencarian motif, dan analisis jaringan metabolik.
Operasi Penelitian
Masalah penjadwalan, penugasan, dan perancangan sirkuit elektronik (PCB layout) sering dirumuskan sebagai masalah graf.
Game dan AI
Pencarian solusi dalam papan permainan (chess, go), serta perencanaan lintasan robot.
Komputer Vision
Segmentasi citra, deteksi tepi, dan pengenalan pola menggunakan graf piksel atau superpixel.
Kriptografi
Beberapa skema kunci publik berbasis masalah graf seperti Hamiltonian cycle.
Data Mining
Frequent subgraph mining, analisis struktur data besar, serta rekomendasi produk dengan graf bipartit penggunaitem.
Kesimpulan
Teori graf menyediakan bahasa universal untuk memodelkan hubungan antar objek. Dari konsep dasar seperti simpul dan sisi, hingga algoritma canggih untuk aliran jaringan, graf telah menjadi fondasi penting dalam ilmu komputer, matematika terapan, serta bidangbidang teknik. Menguasai representasi graf, mengenali jenisjenisnya, dan mempelajari algoritma klasik membuka peluang untuk memecahkan beragam masalah dunia nyata secara efisien.
