Pengantar Teori Graf
Definisi Graf
Graf (atau dalam bahasa Inggris disebut graph) adalah struktur matematika yang terdiri atas sekumpulan simpul (vertex) dan sekumpulan sisi (edge) yang menghubungkan pasangan simpul. Secara formal, graf tak berarah dapat dituliskan sebagai pasangan terurut G = (V, E), dimana V adalah himpunan simpul dan E adalah himpunan sisi, masingmasing berupa pasangan tak berurutan {u, v} dengan u, v V. Pada graf berarah (directed graph atau digraph), sisi dituliskan sebagai pasangan berurutan (u, v) yang menyiratkan arah dari u ke v.
Jenisjenis Graf
Graf Sederhana
Graf yang tidak mengizinkan adanya sisi ganda (multiple edges) ataupun loop (sisi yang menghubungkan simpul dengan dirinya sendiri).
Graf Lengkap
Graf sederhana dimana setiap pasangan simpul terhubung oleh tepat satu sisi. Notasi umum untuk graf lengkap dengan n simpul adalah K. Pada K terdapat n(n1)/2 sisi.
Graf Bipartit
Graf yang dapat dipartisi menjadi dua himpunan U dan W sehingga setiap sisi menghubungkan satu simpul dari U ke satu simpul dari W. Jika semua pasangan antara U dan W terhubung, graf tersebut disebut graf lengkap bipartit dan dinotasikan K_{m,n}.
Graf Berarah (Digraph)
Setiap sisi memiliki arah. Contoh pentingnya adalah graf alur kerja, jaringan komputer, atau graf ketergantungan pada ilmu komputer.
Graf Berbobot
Setiap sisi memiliki nilai numerik (berat) yang biasanya mewakili jarak, biaya, atau kapasitas. Berat ini memungkinkan pemecahan masalah optimasi seperti shortest path atau minimum spanning tree.
Teorema Penting dalam Teori Graf
- Teorema Euler tentang Graf Planar Sebuah graf terhubung planar memenuhi
V E + F = 2, dimanaFadalah jumlah muka (face) pada gambar planar. - Teorema Knig Pada graf bipartit, ukuran maksimum pencocokan (matching) sama dengan ukuran minimum penutup vertex (vertex cover).
- Teorema Hall Menyediakan kondisi yang diperlukan dan cukup agar sebuah graf bipartit mempunyai pencocokan lengkap pada satu sisi.
- Teorema Brook Sebuah graf tak lengkap dan bukan graf siklus ganjil dapat diwarnai dengan paling banyak
warna, dimanaadalah derajat maksimum. - Teorema Kuratowski Graf tidak planar bila dan hanya bila mengandung subdivisi dari
KatauK_{3,3}.
Aplikasi Teori Graf
Teori graf tidak hanya bersifat teoritis; ia hadir dalam banyak bidang praktis:
- Jaringan Komputer Representasi topologi jaringan, routing, dan deteksi siklus.
- Transportasi Model jalan raya, penjadwalan penerbangan, dan optimasi rute logistik (misalnya algoritma Dijkstra atau A*).
- Kimia Model molekul sebagai graf atom dan ikatan, membantu dalam perhitungan sifat kimia.
- Ilmu Sosial Analisis jaringan sosial, penyebaran informasi, dan pengaruh.
- Biologi Analisis jaringan metabolik, jalur regulasi gen, serta evolusi filogenetik.
- Kriptografi Penyusunan graf eksponensial untuk masalah hardproblem seperti graf Hamiltonian.
- Game & Puzzle Permainan labirin, Sudoku, dan tekateki lain yang dapat dimodelkan sebagai graf.
Referensi
Bagi yang ingin memperdalam materi, berikut beberapa sumber yang direkomendasikan:
- J. A. Bondy & U. S. R. Murty, Graph Theory, Springer, 2008.
- Douglas B. West, Introduction to Graph Theory, Prentice Hall, 2001.
- R. Diestel, Graph Theory, 5th ed., Springer, 2017.
- Wikipedia Bahasa Indonesia Teori Graf.
- Materi kuliah daring MIT OpenCourseWare: Mathematics for Computer Science.
