Sejarah Graf


Menurut catatan sejarah Jembatan Konigsberg adalah masalah yang pertama kali menggunakan graf (tahun 1736). Di kota Konigsberg (sebelah timur negara bagian Prussia, Jerman), sekarang bernama Kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari Pulau Kneighof lalu bercabang menjadi dua buah anak sungai.

Ada tujuh buah jembatan yang mengubungkan daratan yang dibelah oleh sungai tersebut. Masalah jembatan Konigsberg adalah apakah mungkin memlalui ketujuh bauh jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula? Sebagian penduduk kota sepakat bahwa memang tidak mungkin melalui setiap jembatan itu hanya sekali dan kembali lagi ketempat asal mula keberangkatan, tetapi mereka tidak dapat menjelaskan mengapa demikian jawabannya, kecuali dengan cara coba-coba. Tahun 1736, seorang matematikawan Swiss, Leonhard Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan pembuktian yang sederhana. Ia memodelkan masalah ini kedalam graf. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakan sebagai titik (noktah)- yang disebut simpul (vertex)- dan jembatan dinyatakan sebagai garis-yang disebut sisi (edge). Setiap titik diberi label huruf A, B, C, dan D. Graf yang dibuat oleh Euler diperlihatkan pada gambar dibawah ini.

Photobucket

Jawaban yang dikemukakan oleh Euler adalah orang yang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya genap. Yang dimksud derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh, simpul B, C dan D memiliki derajat tiga karena ada tiga buah garis yang bersisisan dengannya, sedangkan simpul A berderajat lima. Karena tidak semua berderajat genap, maka tidak mungkin dilakukan perjalanan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.

 

Sumber :

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

Iklan

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