Tujuh Jambatan Königsberg
Tujuh Jambatan Königsberg ialah satu masalah matematik bersejarah yang ternama. Penyelesaian negatifnya oleh Leonhard Euler pada tahun 1735 menjadi asas kepada teori graf dan memberi gambaran awal topologi.
Bandar Königsberg di Prussia (kini Kaliningrad, Rusia) terletak di kedua-dua belah sungai Pregel, dan merangkumi dua buah pulau besar yang disambungkan antara satu sama lain dan dengan tanah besar oleh tujuh jambatan.
Masalah matematiknya ialah mencari satu laluan untuk merentasi seluruh bandar yang melintasi jambatan-jambatan ini sekali dan hanya sekali. Pulau-pulau di bandar ini tidak boleh dicapai melalui cara lain kecuali dengan melintasi jambatan-jambatan ini, dan setiap jambatan perlu dilintasi sepenuhnya setiap kali. Dengan erti kata lain, seseorang tidak boleh melintasi satu jambatan, lalu berpatah balik di pertengahan jalan dan melintasi jambatan lain. Laluan itu tidak perlu bermula dan berakhir di tempat yang sama. Euler telah membuktikan bahawa masalah ini tidak ada penyelesaian. Semua laluan akan melintasi salah satu jambatan ini lebih daripada sekali. Masalahnya adalah pembangunan satu teknik analisis dan ujian-ujian selepasnya yang mendirikan pernyataan ini dengan rigor matematik.
Analisis Euler
[sunting | sunting sumber]Pertama sekali, Euler telah menyatakan bahawa pemilihan laluan di dalam setiap daratan adalah tidak penting. Satu-satunya ciri yang penting dalam laluan yang diambil adalah urutan lintasan jambatan. Ini membolehkan beliau untuk menyusun semula masalah ini dalam bentuk abstrak (dan menjadi dasar kepada teori graf), iaitu dengna menyingkirkan semua unsur-unsur lain dalam masalah ini kecuali senarai daratan-daratan dan jambatan-jambatan yang menyambungkannya. Dalam istilah moden, seseorang boleh menggantikan setiap dataran dengan satu "bucu" abstrak, ataupun nod, dan setiap jambatan boleh digantikan dengan satu sambungan abstrak, iaitu satu "sisi", yang hanya berfungsi untuk menunjukkan bucu-bucu (daratan) mana yang disambungkan oleh sesuatu jambatan. Struktur matematik pada akhirnya dipanggil satu graf.
→
→
Oleh kerana hanya maklumat sambungan yang penting, bentuk perlambangan bergambar boleh diherotkan dengan apa cara sekalipun tanpa mengubah graf itu sendiri. Hanya kewujudan (atau ketiadaan) satu sisi di antara setiap pasangan nod sahaja yang penting. Misalnya, satu sisi boleh dilukis sama ada lurus ataupun melengkung, atau satu nod boleh berada sama ada di sebelah kiri atau kanan.
Kemudian, Euler telah memerhatikan bahawa (kecuali di titik-titik hujung satu laluan) apabila seseorang memasuki satu bucu dengan satu jambatan, ia meninggalkan bucu itu dengan satu jambatan. Dengan erti kata lain, dalam mana-mana laluan dalam graf itu, jumlah berapa kali seseorang memasuki bucu bukan penghujung bersamaan dengan bilangan kali dia meninggalkannya. Jika setiap jambatan hanya boleh direntasi tepat-tepat sekali, bermaksud yang untuk setiap daratan (kecuali yang dipilih sebagai titik permulaan dan penamat), jumlah jambatan yang menyentuhnya mestilah genap (separuh daripada bilangan itu adalah untuk ke daratan itu, dan separuh lagi adalah untuk meninggalkannya). Namun, keempat-empat daratan di dalam masalah ini disentuhi oleh jumlah jambatan yang ganjil (satu pulau mempunyai lima jambatan dan satu lagi mempunyai tiga jambatan).
Dalam istilah moden, Euler menunjukkan bahawa kemungkinan satu laluan dalam graf yang melalui satu sisi hanya sekali bergantung kepada darjah setiap nod. Darjah satu nod ialah bilangan sisi yang menyentuhnya. Hujah Euler menunjukkan bahawa keadaan yang perlu untuk berjalan dalam keadaan yang diberikan ialah graf itu bersambung dan mempunyai tepat sifar atau dua nod berdarjah ganjil. Keadaan ini rupanya cukup—satu keputusan yang dinyatakan oleh Euler dan kemudiannya dibuktikan oleh Carl Hierholzer. Perjalanan seperti ini kini dinamakan laluan Euler untuk menghargai beliau. Tambahan lagi, jika ada nod berdarjah ganjil, mana-mana laluan Euler akan bermula di satu nod dan berakhir di nod yang lain. Oleh kerana graf yang mewakili jambatan-jambatan Königsberg mempunyai empat nod berdarjah ganjil, ia tidak boleh ada satu laluan Euler.
Bentuk lain masalah ini meminta satu laluan yang melalui semua jambatan dan mempunyai titik permulaan dan penamat yang sama. Laluan sebegini dipanggil litar Euler. Litar sebegini wujud jika, dan hanya jika, graf ini bersambung dan langsung tidak ada nod berdarjah ganjil. Semua litar Euler adalah laluan Euler, tetapi tidak semua laluan Euler adalah litar Euler.
Hasil kerja Euler telah dibentangkan kepada Akademi St. Petersburg pada 26 Ogos 1735 dan diterbitkan dengan nama Solutio problematis ad geometriam situs pertinentis (Penyelesaian satu masalah berkaitan geometri kedudukan) di dalam jurnal Commentarii academiae scientiarum Petropolitanae pada 1741.[1] Ia boleh didapati dalam bahasa Inggeris dalam The World of Mathematics.
Kepentingan kepada sejarah matematik
[sunting | sunting sumber]Dalam sejarah matematik, penyelesaian Euler bagi masalah jambatan-jambatan Königsberg dianggap sebagai teorem pertama dalam teori graf, subjek yang kini dianggap sebagai salah satu cabang kombinatorik. Masalah-masalah kombinatorik jenis lain telah difikirkan sejak dahulu kala.
Tambahan lagi, Euler mendapati bahawa maklumat-maklumat utama dalam masalah ini ialah bilangan jambatan dan senarai titik akhir masing-masing, bukannya kedudukan tepatnya. Ini telah meramalkan pembangunan topologi. Perbezaan antara tataletak sebenar dan skematik graf jelas menerangkan idea yang topologi tidak mengambil berat bentuk sebenar objek-objek.
Variasi
[sunting | sunting sumber]Pernyataan klasik masalah ini, seperti yang diberikan di atas, menggunakan nod-nod yang tidak dikenalpasti—dengan kata lain, semua nod ini sama kecuali dalam cara ia bersambung antara satu sama lain. Terdapat satu variasi dalam permasalahan ini di mana semua nod dikenalpasti—setiap nod diberikan nama atau warna yang unik.
Di tebing utara sungai ini terdapat sebuah Schloß, atau istana, yang diduduki oleh Putera Biru, dan di tebing selatan pula letaknya istana yang diduduki oleh Putera Merah. Di tebing timur pula ada sebuah Kirche, atau gereja, yang diduduki oleh seorang biskop, dan di pulau kecil di tengah terletaknya sebuah Gasthaus, atau rumah persinggahan.
Masalah-masalah selepas ini perlu diselesaikan mengikut urutan, dan ia bermula dengan pernyataan masalah yang asal:
Sudah menjadi kebiasaan bagi orang-orang di pekan itu, selepas beberapa jam berada di Gasthaus, untuk mencuba berjalan melalui semua jambatan. Ramai yang pulang ke rumah persinggahan dengan dakwaan bahawa mereka telah berjaya. Namun, tidak seorang pun dapat mengulanginya dalam hari tersebut.
Jambatan 8: Setelah menganalisa sistem jambatan pekan itu melalui teori graf, Putera Biru telah memutuskan bahawa jambatan-jambatan ini tidak boleh dilintasi hanya sekali setiap satu dalam satu perjalanan. Oleh itu, dia merancang satu pelan licik untuk membina jambatan kelapan supaya dia boleh bermula pada waktu petang di Schloßnya, berjalan melalui semua jambatan, dan berakhir di Gasthaus untuk bermegah-megah dengan kejayaannya. Namun, dia tidak mahu Putera Merah mengulangi apa yang telah dia lakukan dari Istana Merah. Di mana Putera Biru membina jambatan kelapan itu?
Jambatan 9: Dengan rasa marah pada penyelesaian drastik Putera Biru bagi masalah ini, Putera Merah mahu membina jambatan kesembilan yang membolehkan dia melalui semua jambatan sekali bermula dari Schloßnya dan berakhir di Gasthaus untuk memalukan putera yang satu lagi. Dia juga mahu supaya Putera Biru tidak dapat lagi melalui semua jambatan daripada istananya. Di mana Putera Merah membina jambatan kesembilan?
Jambatan 10: Biskop telah memerhatikan pembinaan jambatan-jambatan ini dengan rasa hampa. Ia memburukkan pandangan dunia pekan itu dan, untuk memburukkan keadaan, membawa kepada kemabukkan yang melampau. Beliau ingin membina jambatan kesepuluh yang membolehkan semua orang melalui semua jambatan dan pulang ke tempat asal mereka. Di manakah Biskop ini membina jambatannya?
Penyelesaian
[sunting | sunting sumber]
Ringkaskan pekan tersebut, seperti sebelum ini, kepada sebuah graf. Warnakan setiap nod. Seperti dalam masalah klasik, laluan Euler tidak wujud dalam graf ini; warna setiap nod tidak memberi sebarang perbezaan. Keempat-empat nod mempunyai bilangan sisi yang ganjil.
Jambatan 8: Laluan Euler hanya boleh wujud sekiranya ada tepat sifar atau dua nod dengan bilangan sisi ganjil. Jika kita ada dua nod dengan bilangan sisi ganjil, laluan ini mesti bermula di satu nod sebegini dan berakhir di nod satu lagi. Oleh kerana hanya terdapat empat nod dalam teka-teki ini, penyelesaiannya mudah. Perjalanan yang ingin dilakukan perlu bermula di nod biru dan berakhir di nod jingga. Oleh itu, sisi baru dilukis di antara dua nod lain. Oleh kerana pada asalnya kedua-dua nod ini mempunyai bilangan sisi ganjil, kini sepatutnya nod-nod ini memiliki bilangan sisi genap dan memenuhi semua syarat. Ini merupakan perubahan pariti daripada darjah ganjil kepada genap.
Jambatan 9: Penyelesaian bagi jambatan ke-9 mudah sekiranya jambatan ke-8 telah diselesaikan. Keperluan bagi jambatan yang ini ialah ia membolehkan laluan bermula dari istana merah dan bukan di istana biru, sementara nod jingga kekal sebagai penamat laluan dan nod putih tidak terkesan. Untuk mengubah pariti nod merah dan biru, lukiskan sisi baru di antara kedua-dua nod.
Jambatan 10: Jambatan kesepuluh adalah lain daripada jambatan yang lain. Biskop pekan ini mahu setiap penduduk kembali ke titik permulaan mereka. Ini adalah litar Euler dan untuk membolehkannya, setiap nod perlu berdarjah genap. Selepas penyelesaian jambatan kesembilan, nod merah dan jingga memiliki nod ganjil, jadi pariti kedua-duanya perlu diubah dengan menambahkan sisi baru di antara keduanya.
Keadaan sekarang jambatan-jambatan
[sunting | sunting sumber]
Dua daripada tujuh jambatan asal tidak selamat dalam pengeboman Königsberg dalam Perang Dunia Kedua. Dua lagi kemudiannya diruntuhkan dan digantikan dengan lebuh raya moden. Hanya tiga jambatan yang kekal, tetapi dua sahaja daripadanya yang datang dari zaman Euler (satu telah dibina semula pada tahun 1935).[2] Oleh itu, setakat tahun 2000, terdapat lima jambatan di Kaliningrad.
Dari segi teori graf, dua daripada nod kini mempunyai darjah 2, dan dua lagi mempunyai darjah 3. Oleh itu, laluan Euler kini boleh dilakukan. Namun, oleh sebab ia perlu bermula di satu pulau dan berakhir di pulau yang lain, ia tidak praktikal bagi para pelancong.[3]
Universiti Canterbury di Christchurch, New Zealand, telah membina model jambatan-jambatan ini di kawasan rumput di antara bangunan Perpustakaan Sains Fizikal lama dan Bangunan Erskine yang memuatkan Jabatan Matematik, Statistik dan Sains Komputer.[4]
Lihat juga
[sunting | sunting sumber]Rujukan
[sunting | sunting sumber]- ^ The Euler Archive, komentari berkenaan terbitan, dan teks asal, dalam bahasa Latin.
- ^ Taylor, Peter (Disember 2000). "What Ever Happened to Those Bridges?". Australian Mathematics Trust. Diperoleh 2006-11-11.
- ^ Stallmann, Matthias (Julai 2006). ["http://www.csc.ncsu.edu/faculty/stallmann/SevenBridges/ The 7/5 Bridges of Koenigsberg/Kaliningrad]. Diperoleh 2006-11-11.
- ^ "About – Mathematics and Statistics – University of Canterbury". math.canterbury.ac.nz. Diperoleh 2010-11-04.
Pautan luar
[sunting | sunting sumber]- Kaliningrad and the Konigsberg Bridge Problemdi
- Terbitan asal Euler (bahasa Latin)
- The Bridges of Köningsberg Diarkibkan 2007-01-18 di Wayback Machine
- How the bridges of Königsberg help to understand the brain
- Euler's Königsberg's Bridges Problem Diarkibkan 2012-06-01 di Wayback Machine di Jabatan Matematik Kolej Contra Costa
- Pregel – alat penghasil graf oleh Google yang dinamakan bersempena masalah ini
- The count of Königsberg Diarkibkan 2012-04-07 di Wayback Machine