Teori Graf

Teori graf adalah cabang ilmu yang mempelajari sifat-sifat graf. Secara umum suatu Graf adalah himpunan busur (edge) dan simpul (vertex atau node) yang banyaknya berhingga dan busur busurnya menghubungkan sebagian atau keseluruhan pasangan dari simpulsimpulnya.

Graf G(V, E) terdiri atas himpunan simpul yang dinyatakan dengan V = {v1,v2, v3, ..., vn} dan himpunan busur yang dinyatakan dengan E = {e1, e2, e3, ..., en} dengan ei = (vi, vj) merupakan busur yang menghubungkan simpul vi dan simpul vj."

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)}

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-> c -> g
• Cycle siklus ? path yang kembali melalui titik asal 2 f -> c -> d -> 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 (v_i,v_j)=(v_j,v_i)

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