Dalam matematika dan ilmu komputer, teori graf adalah cabang kajian
yang mempelajari sifat-sifat graf.
Secara informal, suatugraf adalah himpunan benda-benda yang disebut simpul (vertex atau node)
yang terhubung oleh sisi (edge)
atau busur (arc).
Biasanya graf digambarkan sebagai kumpulan titik-titik
(melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan
sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan
suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).
Banyak sekali struktur yang bisa
direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan
bantuan graf. Jaringan persahabatan pada Facebook bisa direpresentasikan dengan graf, yakni
simpul-simpulnya adalah para penggunaFacebook dan ada sisi antar
pengguna jika dan hanya jika mereka berteman. Perkembanganalgoritma untuk menangani graf akan berdampak besar
bagi ilmu
komputer.
Dalam matematika dan ilmu komputer, teori graf adalah cabang kajian
yang mempelajari sifat-sifat graf.
Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node)
yang terhubung oleh sisi (edge)
atau busur (arc).
Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul)
yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah
(melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan
simpul yang sama. Sisi yang demikian dinamakan gelang (loop).
Banyak sekali struktur yang bisa
direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan
bantuan graf. Jaringan persahabatan pada Facebook bisa direpresentasikan dengan graf, yakni
simpul-simpulnya adalah para pengguna Facebook dan ada sisi antar pengguna jika
dan hanya jika mereka berteman. Perkembanganalgoritma untuk menangani graf akan berdampak besar bagi ilmu komputer.
Sebuah struktur graf bisa dikembangkan dengan
memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan
banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan
jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan
tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat
sisinya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digrafdengan sisi berbobot disebut jaringan.
Jaringan banyak digunakan pada cabang praktis
teori graf yaitu analisis jaringan.
Perlu dicatat bahwa pada analisis jaringan, definisi kata
"jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa
bobot dan arah).
Graf
memiliki banyak jenis, dalam tulisan ini akan dibahas beberapa jenis graf yang
sering digunakan. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf dan berdasarkan sisi pada graf
yang mempunyai orientasi arah.
Berdasarkan ada
tidaknya gelang atau sisi ganda pada suatu graf maka graf digolongkan menjadi
dua jenis:
- Graf
sederhana (simple graph)
Graf
yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana.
- Graf
tak-sederhana (unsimple graph)
Graf
yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana (unsimple
graph). Ada dua macam graf tak sederhana, yaitugraf ganda (multigraph)
atau graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda.
Graf semu adalah graf yang mengandung gelang (loop).
Jumlah
simpul pada graf disebut sebagai kardinalitas graf, dan dinyatakan dengan n =
|V|, dan jumlah sisi kita nyatakan dengan m = |E|
Berdasarkan orientasi
arah pada sisi, maka secara umum graf dibedakan atas 2 jenis :
- Graf
tak-berarah (undirected graph)
Graf
yang sisinya tidak mempunyai orientasi arah disebut tak-berarah. Pada graf
tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak
diperhatikan. Jadi, (u, v) = (v, u) adalah sisi yang sama.
- Graf
berarah (directed graph atau digraph)
Graf
yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Pada
graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan
kata lain (u, v) (v, u). Untuk busur
(u, v) simpul u dinamakan simpul asal (initial vertex) dan
simpul v dinamakan simpul terminal (terminal vertex).
Ini adalah contoh gambar graf teratur :
video graf teratur 3d,4d,5d :