JEMBATAN KONIGSBERG
KONIGSBERG
Königsberg merupakan nama lama dari kota Kaliningrad. Awalnya Königsberg merupakan kota Sambia atau Prusia Lama, tetapi kemudian berada di bawah kekuasaan Negara Ordo Teutonik, Kadipaten Prusia, Kerajaan Prusia. Kota ini kini merupakan ibu kota Oblast Kaliningrad di Rusia, yang merupakan sebuah eksklave yang berbatasan langsung dengan Lituania di utara dan Polandia di selatan.
Tahukah Kamu?
Masalah jembatan Königsberg adalah teka-teki lama terkait kemungkinan menemukan jalan setapak di tujuh jembatan yang membentang di sepanjang sebuah sungai bercabang yang melewati dua pulau tetapi tanpa melewati jembatan dua kali.
Leonhard Euler
Leonhard Euler adalah seorang ahli matematika asal Swiss yang mencoba untuk memecahkan Masalah jembatan Königsberg dengan teorema Graph. Dari adanya 7 (tujuh) buah jembatan yang dapat menghubungkan 2 (dua) pulau dan sebuah sungai tersebut, Euler kemudian mencari solusi dengan membentuk model jembatan Königsberg meggunakan multigraph. Berdasarkan teori grafik (graph), istilah grafik disini tidak mengacu pada grafik data, seperti grafik garis atau grafik batang. Grafik yang dimaksud mengacu pada sekumpulan simpul (titik) dan tepi (garis) yang menghubungkan simpul. Bila dua simpul digabungkan lebih dari satu tepi, grafiknya disebut sebagai multigraph. Pada multigraph jembatan Königsberg terdapat 2 (dua) elemen yaitu himpunan vertex (titik/node) dan himpunan edge (garis) yang saling menghubungkan garis antar vertex.
Titik-titik yang diberi label X,Y,Z, dan W pada gambar diatas disebut sebagai vertex dan garis saling menghubungkan antar titik disebut dengan edge. Pada semua multigraph Euler terdapat sebuah aturan yang dapat dipakai dalam mencari solusi pada jembatan Königsberg, sehingga aturan ini disebut dengan sebutan Eulerian path, yang berbunyi: “Andai kita mempunyai sebuah multigraph untuk beberapa pasang verteks sehingga akan terdapat sebuah path (lintasan) diantara verteks-verteks tersebut. Multigraph tersebut memiliki eulerian path dan jika terdapat 0 atau 2 verteks maka banyak edge yang meninggalkan verteks tersebut akan berjumlah ganjil”
Lintasan Euler (Eulerian path ) merupakan lintasan yang melewati semua ruas pada graph tepat satu kali. Pada Multigraph jembatan Königsberg diatas terdapat empat vertex, dimana pada keempat vertex tersebut memiliki edge sehingga meninggalkan verteks yang berjumlah ganjil. Maka, berdasarkan aturan Eulirian path terbukti bahwa multigraph jembatan Königsberg tidak memiliki Eulirian path.
Pada permasalahan jembatan Königsberg menghasilkan solusi yang diperoleh melalui analogika bahwa setiap jembatan dimisalkan sebagai sisi dan setiap daratan diumpamakan sebagai simpul pada graph sehingga terbentuklah graph yang lengkap. Dengan memperhitungkan derajat dalam graph dari setiap simpulnya maka dengan menggunakan metode pembuktian di atas, kita dapat mengetahui bahwa jembatan Königsberg tidak memiliki Eulirian path sehingga suatu lintasan dari setiap sisi tidak dapat dilalui hanya satu kali saja.