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).
Sedikit lebih formal
Suatu graph G dapat dinyatakan sebagai G = <
V,E > . Graph G terdiri atas himpunan V yang berisikan simpul pada graf
tersebut dan himpunan dari E yang berisi sisi pada graf tersebut. Himpunan E
dinyatakan sebagai pasangan dari simpul yang ada dalam V. Sebagai contoh
definisi dari graf pada gambar di atas adalah : V = {1,2,3,4,5,6} dan E =
{(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}
Pada digraf maka pasangan-pasangan ini merupakan
pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda
panah) kita dapat menggunakan himpunan edge sebagai berikut :
E = { < 1,2 > , < 1,5 > , < 2,5
> , < 3,2 > , < 4,3 > , < 5,4 > , < 4,6 > }
Dalam himpunan edge untuk digraf, urutan pasangan
verteks menentukan arah dari edge tersebut.
Dalam teori graf, formalisasi ini untuk
memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan
dengan graph. Beberapa terminologi berhubungan dengan teori graf :
- Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
- Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path b \rightarrow c \rightarrow g
- Cycle siklus ? path yang kembali melalui titik asal 2 f \rightarrow c \rightarrow d \rightarrow e kembali ke 2.
- Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf diatas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV – 1. Dimana nV adalah jumlah vertex
- Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (vi,vj)=(vj,vi)
- Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.