Pertanyaannya adalah bisakah kita mengunjungi setiap bagian kota dengan melewati setiap jembatan satu kali?
Pertanyaan ini dulu diberikan kepada seorang matematikawan tersohor, Leonhard Euler... tapi coba kita pecahkan sendiri!
Dan dalam aktivitas ini kita akan mempelajari sedikit tentang "Teori Graf".
Kita Sederhanakan!
Mari kita sederhanakan peta di atas menjadi seperti ini:
Terdapat 4 bagian kota - daratan sebelah utara sungai, daratan sebelah selatan sungai, pulau di tengah kota, dan daerah semenanjung (bagian kanan).
Kita beri label A, B, C dan D.
Untuk mengunjungi setiap bagian kota, kita harus mengunjungi titik A, B, C, dan D.
Dan kita harus melewati setiap jembatan p, q, r, s, t, u, v hanya satu kali.
Dapat kita sederhanakan seperti ini:
Daripada kita mencari jawaban sambil berjalan sepanjang kota Königsberg, kita bisa mencari jawabannya dengan secarik kertas dan pensil.
Giliran Kalian!
Bisakah kalian menggambarkan setiap garis p, q, r, s, t, u, dan v dalam sekali garis, tanpa memindahkan pensil dari kertas kalian (kalian bisa mulai dari titik mana saja)?
Silahkan kalian coba dan kita lihat kemampuan kalian.
...
...
...
Apakah kalian berhasil?
Hmn... mungkin kita coba dulu bentuk yang lebih sederhana.
Cobalah bentuk-bentuk ini! (ingat: gambar semua garis dalam sekali coretan, maksudnya jangan pindahkan pensil kalian dari kertas saat membuat garis)
Catat hasil kalian di sini:
| Bentuk | Berhasil? |
| 1 | Ya |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
Jadi, Bagaimana kita dapat mengetahui bentuk mana yang berhasil mana yang tidak?
Ayo kita investigasi!
Tapi pertama-tama kita harus mempelajari beberapa kata khusus:
- titik disebut sebuah simpul (tapi di sini kita akan memakai kata vertex).
- garis disebut sisi (edge).
- dan seluruh diagram disebut graf.
Ingat Graf, bukanlah bagian dari Grafik. Mirip memang tapi mereka berbeda!
<-- Ini Grafik bukan Graf!
- Jumlah sisi yang berujung pada sebuah vertex disebut derajat.
- Lintasan mengelilingi graf dan melewati setiap vertex dalam sekali jalan disebut sirkuit simpel.
- Lintasan yang mengelilingi graf dan melewati setiap sisi dalam sekali jalan disebut sirkuit Euler.
Contoh:
Diagram 7 memiliki:
- 5 vertex: A, B, C, D, dan E
- 8 sisi: AB, BC, CD, AD, AE, EB, AC, dan BD
- Vertex A dan B berderajat 4
- Vertex C dan D berderajat 3
- Vertex E berderajat 2
Diagram 8 memiliki:
- 6 vertex: A, B, C, D, E dan F
- 10 sisi: AB, BC, CD, AD, AE, EB, AF, BF, CF dan DF
- Vertex A, B, dan F berderajat 4
- Vertex C dan D berderajat 3
- Vertex E berderajat 2
Sirkuit Euler
OK, kita bayangkan setiap garis adalah jembatan, dan kita hanya boleh melewatinya satu kali untuk memecahkan puzzle ini jadi ...
... apa yang kita perlukan adalah sirkuit Euler.
... dan ini ada petunjuk yang akan membantu kita: kita dapat mengenali graf mana yang memiliki sirkuit Euler dengan cara menghitung berapa banyak vertex yang memiliki derajat ganjil.
Mari kita isi tabel di bawah ini:
| Bentuk | Sirkuit Euler? | Vertex | berapa banyak yang memiliki derajat genap? | berapa banyak yang memiliki derajat ganjil? |
| 1 | Yes | 4 | 4000000040000000 | 000000000000000 |
| 2 | | | | |
| 3 | | | | |
| 4 | | | | |
| 5 | | | | |
| 6 | | | | |
| 7 | | | | |
| 8 | | | | |
Apakah kalian menemukan sebuah pola?
Selesaikan dulu investigasi kalian sampai kalian menemukan pola dari tabel, sebelum lanjut ke bagian selanjutnya!
...
...
Dan... Jawabannya adalah...
Jumlah vertex yang berderajat ganjil harus ada dua atau nol.
Jika jumlah vertex berderajat ganjil selain dua dan nol maka tidak ada sirkuit Euler pada graf tersebut.
Dan jika terdapat dua vertex yang berderajat ganjil bisa dipastikan vertex tersebut merupakan awal dan akhir dari garis lintas.
Alasannya ternyata tidak sulit untuk dipahami kok. Sebuah lintasan berawal dari sebuah vertex melalui sebuah sisi dan keluar dari sebuah sisi yang lain melalui vertex yang sama. Jadi sisi-sisi harus berpasangan (genap). Titik awal dan akhir dapat memiliki derajat ganjil walaupun hanya dapat berlaku bila vertex yang berderajat ganjil cuma dua.
Kembali Lagi ke Puzzle Jembatan Königsberg
Vertex A, B, dan D memiliki derajat 3 dan vertex C memiliki derajat 5, jadi graf ini memiliki 4 vertex berderajat ganjil. Graf ini tidak memiliki Sirkuit Euler!
Kita telah memecahkan puzzle Jembatan Königsberg sama seperti yang Euler lakukan 300 tahun yang lalu!
Tugas: Dari bentuk-bentuk di bawah ini, yang mana yang memiliki Sirkuit Euler?
| Bentuk | Sirkuit Euler? | Vertex | berapa banyak derajat genap? | berapa banyak derajat ganjil? |
| 9 | | | | |
| 10 | | | | |
| 11 | | | | |
| 12 | | | | |
| 13 | | | | |
| 14 | | | | |
Catatan Kaki:
Leonhard Euler (1707 - 1783), seorang matematikawan Swiss, merupaka salah satu matematikawan tersohor dan terproduktif sepanjang masa. Beliau banyak menghasilkan karyanya di Akademi Berlin, Jerman dan hasil pemecahan beliau tentang teka-teki "Tujuh Jembatan Königsberg" sangat terkenal pada masanya.
Kota Königsberg dilalui oleh Sungai Pregel. Dulu berada di dalam negara yang disebut bernama Prussia, sekarang dikenal sebagai Kaliningrad, Russia. Lokasi Königsberg sangat dekat dengan sungai dan memiliki 7 jembatan yang menghubungkan dua sisi sungai,juga pulau di tengah kota dan semenanjung.
Sumber:
