“ TEKA-TEKI TUJUH JEMBATAN KONISBERG”

Oleh : NURHAYATI

. A. LATAR BELAKANG

Graph merupakan salah satu cabang ilmu matematika yang merepresentasikan objek - objek diskrit dan hubungan antara objek – objek tersebut. Representasi visual dari graph adalah dengan menyatakan obyek dengan noktah dan hubungan antara objeknya dengan garis. Untuk selanjutnya kita sebut noktah pada graph sebagai simpul (vertex) dan garis pada graph sebagai sisi (edge).

Teori graph merupakan sebuah pokok bahasan yang muncul pertama kali pada tahun 1736, yakni ketika Leonhard Euler mencoba untuk mencari solusi dari permasalahan yang sangat terkenal yaitu Jembatan Königsberg. Di kota Königsberg (sebelah timur Prussia, Jerman sekarang), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai.

Konigsberg, sebuah kota di bagian utara Jerman, memiliki sebuah kisah terkenal yang memberikan pengaruh besar pada kehidupan seorang bernama Euler dan sejarah perkembangan teori Graph. Sungai Pregel yang melalui Konigsberg membagi wilayah daratan pada kota tersebut menjadi empat bagian. Tujuh buah jembatan dibangun di atas sungai tersebut pada bagian yang memungkinkan untuk bepergian antar keempat wilayah tersebut. Pada abad ke-17, warga Konigsberg gemar berjalan di tepi sungai, hingga akhirnya beberapa dari mereka memikirkan apakah mungkin untuk berjalan di Konigsberg dan melalui setiap jembatan hanya sekali. Hal inilah yang kemudian disebut Teka-Teki Jembatan Konigsberg yang tidak dapat terselesaikan untuk waktu yang cukup lama dan menjadi terkenal di seluruh negeri.

Teka-teki tersebut menarik perhatian Euler, yang diyakini ketika itu berada di St. Petersburg. Ia kemudian meneliti bahwa kasus tersebut dapat direpsersentasikan dalam sebuah diagram. Setelah sekian banyak kegagalan warga Konigsberg untuk menemukan cara melalui seluruh jembatan hanya sekali, hingga akhirnya pada tahun 1736 masalah tersebut dijadikan sebuah kasus matematika dan kemustahilan untuk menyelesaikan teka-teki tersebut terbukti.

B. PEMBAHASAN

Masalah jembatan Königsberg ini adalah, mungkinkah melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula? Kemudian tahun 1736 seorang matematikawan Swiss, Leonhard Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan memodelkan masalah ini ke dalam graph. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakan sebagai titik (noktah) yang disebut simpul atau titik (vertex) dan jembatan dinyatakan sebagai garis-garis yang disebut sisi atau garis (edge).Euler memberi permisalan daratan sebagai sebuah titik, setiap titik diberi label A, B, C, dan D.

Euler mengungkapkan bahwa tidak mungkin seseorang berjalan melewati tepat satu kali masing-masing jembatan dan kembali lagi ke tempat semula, karena pada graph model jembatan Königsberg itu tidak semua simpul berderajat genap (derajat sebuah simpul adalah jumlah sisi yang bersisian dengan simpul yang bersangkutan).
Teori graph merupakan salah satu pokok bahasan yang sudah sangat tua usianya tetapi memiliki banyak terapan praktis hingga saat ini. Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan sisi atau garis.

Dalam kasus jembatan Konigsberg huruf C akan muncul sebanyak tiga kali (BAC, DAC, BDC) karena terdapat lima jembatan yang menyusun jalan menuju C. Kemudian, karena tiga jembatan menyusun jalan menuju A, maka A akan muncul sebanyak dua kali (CDA, BDA). Dengan cara serupa kita dapatkan bahwa kemunculan B dan D juga dua kali. Maka dalam kombinasi delapan huruf sebagai solusi dengan kemunculan huruf ,C dan D sebanyak masing-masing dua kali, ternyata kombinasi seperti itu tidak mungkin ada, sehingga kesimpulannya adalah bahwa teka-teki Konigsberg adalah mustahil.

1. Analisis Euler

Pertama, Euler menunjukkan bahwa pilihan rute di dalam setiap daratan tidak relevan. Satu-satunya fitur penting dari rute adalah urutan jembatan menyeberang. Hal ini memungkinkan dia untuk merumuskan masalah dalam hal abstrak (meletakkan dasar-dasar teori graph ), menghilangkan semua fitur kecuali daftar massa tanah dan jembatan yang menghubungkan mereka. Dalam istilah modern, masing-masing satu menggantikan massa tanah dengan sebuah "abstrak titik "atau node, dan masing-masing jembatan dengan koneksi abstrak, sebuah"tepi ", yang hanya berfungsi untuk merekam yang sepasang simpul (massa tanah) yang dihubungkan dengan jembatan itu. Struktur matematika yang dihasilkan disebut graph.

Karena hanya informasi koneksi yang relevan, bentuk representasi bergambar grafik mungkin terdistorsi dengan cara apapun, tanpa mengubah grafik itu sendiri. Hanya keberadaan (atau kekurangan) dari tepi antara setiap pasangan node adalah signifikan. Sebagai contoh, tidak masalah apakah tepi digambar lurus atau melengkung, atau apakah satu node adalah ke kiri atau kanan lain.

Selanjutnya, Euler mengamati bahwa (kecuali pada titik akhir dari berjalan), setiap kali salah satu titik masuk dengan jembatan, satu daun titik dengan jembatan. Dengan kata lain, selama yang berjalan pada grafik, jumlah kali memasuki simpul non-terminal sama dengan berapa kali satu daun itu. Sekarang, jika setiap jembatan dilalui tepat satu kali, itu berarti bahwa, untuk setiap massa tanah (kecuali mungkin untuk yang dipilih untuk mulai dan selesai), jumlah jembatan menyentuh daratan bahkan (setengah dari mereka, pada khususnya traversal, akan dilalui "menuju" daratan tersebut; setengah lainnya, "jauh" dari itu). Namun, keempat massa tanah dalam masalah asli tersentuh oleh ganjil jembatan (satu disentuh oleh 5 jembatan, dan masing-masing tiga lainnya disentuh oleh 3). Karena, paling tidak, dua massa tanah dapat berfungsi sebagai titik akhir dari jalan putatif, proposisi berjalan kaki melintasi jembatan setiap kali mengarah ke kontradiksi.

Dalam bahasa modern, Euler menunjukkan bahwa kemungkinan berjalan melalui grafik, melintasi setiap sisi tepat satu kali, tergantung padaderajat dari simpul-simpul. Derajat dari sebuah node adalah jumlah edge menyentuhnya. argumen Euler menunjukkan bahwa kondisi yang diperlukan untuk berjalan dari bentuk yang diinginkan adalah bahwa grafik dihubungkan dan memiliki tepat nol atau dua simpul berderajat ganjil. Kondisi ini ternyata juga cukup-hasil dinyatakan oleh Euler dan kemudian dibuktikan oleh Carl Hierholzer . Seperti jalan-jalan sekarang disebut jalur Euler atau jalan Euler untuk menghormatinya. Selanjutnya, jika ada node derajat ganjil, maka setiap path Euler akan dimulai pada salah satu dari mereka dan berakhir pada yang lain. Karena grafik yang sesuai dengan Königsberg historis memiliki empat node derajat aneh, ia tidak dapat memiliki jalur Euler.

Alternatif bentuk masalah meminta jalan yang melintasi semua jembatan dan juga memiliki sama titik awal dan akhir. Seperti berjalan-jalan disebut sirkuit Euler atau tur Euler. Seperti sebuah sirkuit ada jika, dan hanya jika, grafik tersambung, dan tidak ada node derajat aneh sama sekali. Semua sirkuit Euler juga jalur Euler, tetapi tidak semua jalan Euler adalah sirkuit Euler.

Hasil analisa Euler, pada tanggal 2 Agustus 1735 disampaikan kepada St Petersburg Academy dan diterbitkan sebagai geometriam problematis solutio situs iklan pertinentis ( pemecahan masalah yang berkaitan dengan geometri posisi) di Commentarii scientiarum academiae Petropolitanae jurnal pada 1741.

2. Solusi Euler

Untuk membuktikan hasilnya, Euler memformulakan masalah itu dalam teori graf, dengan menganalogikan pada kasus Königsberg. Pertama, dengan mengeliminasi semua fitur kecuali daratan dan jembatan yang menghubungkannya; kedua, dengan mengganti daratan dengan titik, disebut simpul(vertex) dan tiap jembatan dengan garis. Disebut sisi (edge). Hasil struktur matematikanya disebut graph. Bentuk dari graph dapat diubah-ubah dalam berbagai cara tanpa mengubah graph itu sendiri, selama sisi dari simpul tidak diubah. Tidak bermasalah antara sisi yang berbentuk lurus atau lengkung, atau simpul yang terletak di sisi kiri atau kanan sisi lainnya. Euler menyadari bahwa masalah itu dapat diselesaikan berdasarkan derajat dari simpul–simpulnya. Derajat dari tiap simpul adalah jumlah sisi yang bersinggungan dengannya, pada graph jembatan Königsberg, tiga simpul mempunyai derajat 3 dan salah satu berderajat 5. Euler menunjukkan sirkuit yang kita inginkan hanya mungkin jika tidak ada simpul yang berderajat negatif. Cara perjalanan itu disebut sirkuit euler. Karena graph Königsberg ini mempunyai 4 simpul yang berderajat ganjil maka graph ini tidak mempunyai sirkuit euler.

Masalah ini dapat dikembangkan seperti berikut ini, ketika kita diminta untuk menyusun rute yang melintasi semua jembatan tapi tidak perlu punya titik mula dan akhir yang sama. Lintasan ini disebut lintasan Euler. Lintasan ini dimungkinkan ada jika dan hanya jika:

a) Graph ini tidak punya simpul yang berderajat ganjil.

b) Tepat ada 2 simpul yang berderajat ganjil, dan kedua simpul itu akan menjadi titil awal dan akhir. (ini juga hal yang mustahil untuk graph jembatan Königsberg).

3. Signifikasi dalam sejarah matematika

Pada sejarah perkembangan matematika, solusi Euler tentang jembatan Königsberg dianggap sebagai teorema pertama dari teori graph, yang sekarang digeneralisasi sebagai cabang ilmu kombinatorial (meskipun masalah kombinatorial telah ditemukan sebelumnya). Sebagai tambahan, sesuai pengakuan Euler bahwa kuncinya terletak pada jumlah jembatan dan daftar dari titik akhirnya (lebih dari posisi aslinya) ditandai dengan perkembangan topologi. Perbedaan antara layout nyata dan skema graph adalah contoh yang bagus dari ide bahwa topologi tidak berpatokan pada bentuk asli benda.

4. Keadaan jembatan Konigsberg sekarang

Dua dari tujuh jembatan asli hancur saat pengeboman sekutu ke Königsberg pada Perang Dunia II. Dua lainnya dirusak oleh Rusia dan diganti dengan jembatan modern.Tinggal 3 lainnya yang tersisa, meskipun hanya ada 2 yang berasal dari masa Euler (salah satu dibangun ulang oleh Jerman pada 1935). Menurut teori graph, dua dari simpul sekarang mempunyai derajat 2, dan 2 lainnya punya derajat 3. Karena itu, sekarang lintasan Euler mungkin dapat dibentuk, tapi karena harus dimulai dari sebuah pulau dan berakhir pada pulau yang berbeda.

5. Penerapan Teori Graph.

Secara informal, suatu graph adalah himpunan benda-benda yang ada dalam matematika dan ilmu komputer, teori graph adalah cabang kajian yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graph digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).Banyak sekali struktur yang bisa direpresentasikan dengan graph, dan banyak masalah yang bisa diselesaikan dengan bantuan graph. Jaringan persahabatan pada Friendster bisa direpresentasikan dengan graf: simpul-simpulnya adalah para pemakai Friendster dan ada sisi antara A dan B jika dan hanya jika A berteman (berkoinsidensi) dengan B. Perkembangan algoritma untuk menangani graph akan berdampak besar bagi ilmu komputer.

Contoh-Contoh Pemakaian Graph.

Lintasan Terpendek (Shortest Path)

· graph berbobot (weighted graph),

· lintasan terpendek: lintasan yang memiliki total bobot minimum.

· Contoh aplikasi:

1. Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota

2. Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer.

· Terdapat beberapa jenis persoalan lintasan terpendek, antara lain:

a. Lintasan terpendek antara dua buah simpul tertentu.

b. Lintasan terpendek antara semua pasangan simpul.

c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.

d. Lintasan terpendek abtara dua buah simpul yang melalui beberapa simpul tertentu.

Persoalan Perjalanan Pedagang (Travelling Salesperson Problem - TSP)

Diberikan sejumlah kota dan jarak antar kota. Tentukan sirkuit terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan.

Persoalan Tukang Pos Cina (Chinese Postman Problem)

Dikemukakan oleh Mei Gan (berasal dari Cina) pada tahun 1962.

Masalahnya adalah sebagai berikut: seorang tukang pos akan mengantar surat ke alamat-alamat sepanjang jalan di suatu daerah. Bagaimana ia merencanakan rute perjalanannya supaya ia melewati setiap jalan tepat sekali dan kembali lagi ke tempat awal keberangkatan.

C. KESIMPULAN

Teka-teki jembatan Konigsberg adalah mustahil. Teka-Teki Jembatan Konigsberg telah membuka jalan bagi terciptanya teorema baru yang disebut teorema graph. Aplikasi teorema graph menganalogikan setiap jembatan sebagai sisi dan setiap daratan sebagai simpul pada graph, sehingga terbentuk sebuah graph lengkap. Dan dengan memperhitungkan derajat dari setiap simpul yang terdapat dalam graph, menggunakan metode yang diungkapkan dalam pembuktian di atas, kita akan dapat mengetahui apakah graph tersebut merupakan suatu lintasan di mana setiap sisi dilalui hanya satu kali saja. Fakta bahwa teorema graph lahir ketika Euler menyelesaikan masalah berdasarkan Teka-Teki Jembatan Konigsberg menyatakan hubungan tersendiri antara jaringan spasial (seperti jalur transportasi) dengan graph.

REFERENSI

http://matematika-asyik.blogspot.com/2011/02/teka-teki-jembatan-koenigsberg.html,

Diakses Sabtu, 17 Juni 2011. Pkl. 22.01

http://portalunique.blogspot.com/2010/12/10-matematikawan-terbesar-sepanjang.html. Diakses Sabtu, 17 Juni 2011. Pkl. 22.10