Teory Graf
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
Friendster
bisa direpresentasikan dengan graf: simpul-simpulnya adalah para
pemakai Friendster dan ada sisi antara A dan B jika dan hanya jika A
berteman (berkoinsidensi) dengan B. Perkembangan
algoritma 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). Digraf dengan 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).