Graf

Graf G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E). Dalam hal ini, V merupakan himpunan tidak kosong dari simpul-simpul (vertices atau node) digambarkan dalam titik-titik, dan E adalah himpunan sisi-sisi (edges atau arcs) digambarkan dalam garis-garis yang menghubungkan sepasang simpul (Munir, 2009). Dapat dikatakan graf adalah kumpulan dari simpul-simpul yang dihubungkan oleh sisi-sisi

 

Gambar 2.9 Graf

Pada gambar graf G diatas, graf terdiri dari himpunan V dan E yaitu:

V  =  (A, B, C)  ……….……….. (1)

E  =  (e1,   e2,     e3,     e4);    

Bisa ditulis{(A,B),(B,C),(B,C),(A,C)}  ….... (2)

2.5.1   Graf Terhubung (Connected Graph)

Graf G disebut graf terhubung jika untuk setiap pasang simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v. Jika tidak, maka graf G disebut graf tak terhubung (disconnected graph) (Munir, 2009).

Keterhubungan dua buah simpul adalah penting di dalam graf. Jika dua buah simpul terhubung maka pasti simpul yang pertama dapat dicapai dari simpul yang kedua.

Misalkan u dan v adalah titik yang berbeda pada graf G. Maka titik u dan   v dapat dikatakan terhubung (connected), jika terdapat lintasan u-v di G. Sedangkan suatu graf G dapat dikatakan terhubung (connected), jika untuk setiap titik u dan v di G terhubung (Chartrand dan Lesniak, 1986:28). Keterhubungan adalah sifat yang dimiliki graf. Graf terhubung dapat dilihat atau dibuktikan dari keterhubungan antara u dan v. Untuk lebih menguatkan kondisi (u , v)

2.5.2        Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga. Bobot pada tiap sisi dapat berbeda-beda bergantung pada masalah yang dimodelkan dengan graf (Munir, 2005:376). Bobot dapat menyatakan jarak antara dua buah tiang listrik, kapasitas, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah simpul komunikasi ke simpul komunikasi lain, ongkos produksi, dan sebagainya.

Posted in: