Graf


Teori Graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut representasi visual dari graf adalah dengan menyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis, sisi atau edge.

Graf ini berawal dari masalah jembatan Konigsberg yang berada di Jerman. Oleh matematikawan L.Euler tersebut graf ditemukan dan menyelesaikan masalah jembatan Konigsberg. Graf dalam kehidupan graf ini banyak digunakan, misalnya mencari jarak terpendek untuk menempuh satu kota ke kota lain. Kemudian dimanfaatkan untuk mencari jalan terpendek dalam mengantar surat agar tidak dalam perjalannya tidak melewati jalan yang sama lebih dari sekali. Secara umum graf dapat didefinisikan sebagai berikut.

Definisi Graf :

Graf G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E) yang dalam hal ini V adalah himpunan tak kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edge atau arcs) yang menghubungkan sepasang simpul.

Dalam definisi diatas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial .

 

Sumber :

Munir, R., 2005, Matematika Diskrit, Informatika, Bandung.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s