Teori graf
merupakan pokok bahasan yang sangat tua usianya namun memiliki banyak terapan
sampai saat ini. Graf digunakan untuk
merepsentasikan objek-objek diskrit dan hubungan antara objek dinyatakan
sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan
dengan garis. (Munir, Rinaldi. 2010 h353).
1.
Dafinisi Graf
Secara umum graf dapat didefinisikan sebagai berikut :
Graf G didefinisikan sebagai pasangan
himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini v adalah
himpunan tidak kosong dari simpul-simpul (vertices
atau node) dan E adalah himpunan sisi
(edges atau arcs) yang menghubungkan sepasang simpul. Simpul pada graf dapat dinomori dengan huruf, seperti
a, b, c ...... v, w, ......, dengan bilangan asli 1, 2, 3, ...., atau gabungan
keduanya. Sedangkan sisi yang menghubungkan simpul Vi dengan simpul
Vj dinyatakan dengan pasangan (U, V) atau dinyatakan dengan lambang
e1, e2, ..... dengan kata lain, jika E adalah sisi yang menghubungkan simpul Vi
dengan simpul Vj, maka E dapat ditulis sebagai E= (Vi, Vj),
berikut adalah contoh gambar graf pada gambar 2.1.
