300000
Sarang Lelabah©
Jumlah kemenangan: 129258
| (6 – 20): | Kitaran Laluan Rawak Cabaran |
Definisi + Bagaimanakah ini masih permainan "matematik"?
Gambar rajah dalam permainan ini adalah berdasarkan bidang matematik yang dikenali sebagai teori graf!
Apakah graf?
Graf: Graf terdiri daripada titik dan sisi.
Titik: "Objek" penyambung graf dipanggil nod. Dalam Sarang Lelabah, nod adalah bulatan.
Sisi: Sisi ialah sambungan dalam graf antara dua titik. Dalam Sarang Lelabah, sisi adalah garisan.
Memperluaskan laluan
Laluan: Laluan ialah jujukan sisi bersambung dengan titik permulaan dan titik akhir.
Laluan Eulerian: Ini adalah laluan yang menggunakan setiap sisi dalam graf tepat sekali.
Matlamat dalam permainan ini adalah untuk mencari Laluan Eulerian.
Apakah laluan Eulerian dalam kehidupan seharian?
Lampu salji, trak pembersihan jalan, dan posmen adalah contoh untuk kereta dan orang yang perlu melalui setiap jalan tetapi ingin mengelakkan melalui jalan dua kali.
Adakah nama "Euler" terdengar biasa?
Teori graf bermula apabila ahli matematik Leonhard Euler sedang mengusahakan laluan seperti ini.
Euler menulis kertas kerja mengenai Tujuh Jambatan Königsberg membuktikan bahawa mustahil untuk berjalan melalui lintasan bandar di atas setiap jambatan tepat sekali.
Klik peta masalah di bawah untuk membaca lebih lanjut mengenainya.
Kitaran: Kitaran adalah laluan yang berakhir pada titik yang dimulakan.
Kitaran Eulerian: Ini Laluan Eulerian yang juga kitaran. Pilih "Kitaran" dalam permainan kami di atas dan penyelesaiannya akan sentiasa menjadi Kitaran Eulerian!
Arahan Tetapan Permainan
Dalam kotak teks di sebelah Titik, anda boleh menaip sebarang nombor antara 6-20. Nombor ini akan menjadi bilangan titik yang dipaparkan pada graf. Semakin besar bilangan penyelesaian yang lebih mencabar menjadi!
Seterusnya, pilih jenis graf
Kitaran: Laluan kemenangan akan sentiasa berakhir pada titik yang mereka mulakan.
Laluan: Laluan kemenangan tidak akan berakhir pada titik yang mereka mulakan.
Rawak: Graf yang mungkin membenarkan kitaran Eulerian atau laluan Eulerian. Laluan kemenangan mungkin atau mungkin tidak berakhir pada titik yang mereka mulakan.
Cabaran: Graf buatan tangan di mana sisi menyeberang dan oleh itu jambatan tidak jelas untuk dilihat.
Akhirnya, klik "Buat Sarang Baru" untuk melihat perubahan anda pada tetapan graf!
Titik apa yang harus saya pilih dahulu?
Darjah: Darjah adalah sifat titik. Ia adalah bilangan sisi yang disambungkan kepadanya. Kami akan membezakan antara titik darjah ganjil dan titik darjah ternampak, bergantung pada darjah mereka.
Graf Bersambung: Graf di mana setiap pasangan titik boleh disambungkan melalui laluan.
Jambatan: Sisi ialah jambatan jika kedua-dua hujung sisi tidak dapat disambungkan sebaliknya. Oleh itu selepas menyeberangi jambatan, seseorang tidak akan kembali ke sisi sebelumnya. Mengeluarkan jambatan memisahkan graf menjadi dua komponen yang terputus.
Graf Tidak Diperbetulkan : Graf di mana sisi tidak mempunyai arah yang terpesong. Kami hanya mempertimbangkan mereka dalam permainan ini.
Graf Diarahkan : Graf di mana setiap sisi mempunyai arah yang ditetap seperti jalan sehala.
Graf yang tidak diperbetulkan mengandungi Kitaran Eulerian apabila semua titik mempunyai darjah genap (darjah 0, 2, 4, 6...) . Untuk ini, anda boleh memilih mana-mana titik sebagai titik permulaan anda dan masih menang. Perlu diingat bahawa anda perlu menyelesaikan titik yang anda mulakan.
Graf mengandungi Laluan Eulerian, tetapi tidak Kitaran Eulerian, apabila tepat dua titik mempunyai darjah ganjil (darjah 1, 3, 5, 7...) dan semua titik lain mempunyai darjah yang sama. Dalam kes ini, anda mesti memilih titik dengan darjah ganjil sebagai titik permulaan anda atau anda tidak akan dapat melengkapkan Laluan Eulerian.
Kenapa betul-betul dua titik?
Fikirkan setiap langkah sebagai "keluar" dari titik yang anda bermula dan "masuk" ke titik yang anda lalui. Kebanyakan titik akan mengikuti corak pasangan ini, jadi mereka akan mempunyai darjah genap.
Apabila anda memulakan permainan, kelebihan pertama yang anda tandakan ialah langkah "keluar" titik permulaan. Ini tetap tidak berpasangan semasa anda bermain permainan.
Untuk membuat Kitaran Eulerian, sisi terakhir yang anda tandakan adalah langkah "masuk" ke titik permulaan. Ini mencipta pasangan dengan langkah pertama, yang bermaksud titik permulaan mempunyai darjah yang sama.
Jika Laluan Eulerian graf bukan kitaran, sisi terakhir yang anda tandakan ialah pergerakan tidak berpasangan "dalam" ke titik yang bukan titik permulaan. Titik permulaan kekal dengan darjah ganjil, dan titik akhir juga akan mempunyai darjah ganjil.
Jangan risau tentang kes lain. Jika bilangan titik dengan darjah ganjil tidak betul-betul 0 atau 2, tidak akan ada Laluan Eulerian dan tiada Kitaran Eulerian, yang bermaksud tidak ada cara untuk menang. Graf seperti itu tidak sepatutnya muncul dalam permainan ini.
Soalan Pendahuluan
Bolehkah terdapat bilangan titik ganjil dengan darjah ganjil?
Tidak.
Mengapa?
Bukti:
Mengira semua hujung semua sisi memberikan nombor yang sama seperti menambah semua darjah semua titik, dipersetujui?
Kerana setiap sisi mempunyai 2 hujung, jumlah hujung semua sisi mestilah genap. (Menambah nombor genap memberikan nombor genap.)
Untuk menambah darjah semua titik, seseorang akan menambah darjah genap yang memberikan nombor genap dan menambah darjah ganjil.
Sekiranya terdapat bilangan titik darjah ganjil yang ganjil maka jumlah itu akan ganjil dan kemudian + ganjil = ganjil, jadi jumlah darjah akan ganjil. Tetapi ia sama dengan jumlah keseluruhan semua hujung semua tepi dan itu juga. Oleh itu, bilangan titik darjah ganjil tidak boleh ganjil, ia mestilah genap.
Sebagai contoh, 1 adalah nombor ganjil, jadi tiada graf dengan hanya 1 titik darjah ganjil.
Bilakah Laluan atau Kitaran Eulerian wujud?
Jika titik mempunyai darjah genap, iaitu 2, 4, 6,... sisi dilekatkan pada titik, maka apabila tiba di titik itu, bilangan ganjil sisi yang tidak digunakan dibiarkan yang lebih besar daripada sifar, jadi seseorang akan dapat meninggalkan titik itu dan meneruskan. Sekiranya darjah itu ganjil, iaitu 1, 3, 5,.. sisi dilekatkan maka seseorang mesti memulakan laluan di titik ini atau laluan akan berakhir di titik ini. Kerana laluan hanya mempunyai 2 hujung, hanya ada 2 titik dengan darjah ganjil. Itu:
Untuk mempunyai Kitaran Eulerian, graf mesti mempunyai hanya titik darjah genap, dan untuk mempunyai Laluan Eulerian, ia mesti mempunyai 2 titik darjah ganjil, satu titik akan menjadi permulaan dan satu akan menjadi akhir laluan.
Bagaimanakah seseorang mencari Laluan atau Kitaran Eulerian?
Seperti yang ditunjukkan di atas, jika tiada titik darjah ganjil, maka seseorang boleh bermula di mana-mana titik dan akan berakhir pada titik yang sama. Sekiranya terdapat 2 titik darjah ganjil, maka seseorang perlu bermula di mana-mana satu daripada 2 titik ini dan akan berakhir secara automatik pada yang lain.
Bolehkah sesuatu menjadi salah apabila memanjangkan jalan?
Ya, ada sesuatu yang tidak kena. Sebagai contoh:
2 4 / \ / \ 1---3---5
Darjah semua titik adalah 2 kecuali titik 3 yang mempunyai darjah 4. Jadi semua darjah adalah sama dan kita boleh bermula di mana-mana sahaja. Mari kita mulakan pada titik 1 dan pergi ke titik 3 dan marilah kita menjatuhkan semua sisi yang telah dilalui.
2 4 / \ / \ 1 3---5
Sisi 3-2 menjadi jambatan. Menyeberangi dan mengalih keluar sisi ini 3-2 menghasilkan graf terputus
2 4 / / \ 1 3---5
yang tidak boleh dilalui sepenuhnya. Oleh itu, seseorang harus meneruskan dari 3 hingga 4 atau 5 untuk melengkapkan kitaran Eulerian.
Bagaimanakah seseorang boleh menghalang menyeberangi jambatan?
Untuk memeriksa sama ada sisi adalah jambatan, seseorang akan bermula di satu hujung sisi dan melawat semua titik jiran dan semua jiran mereka dan sebagainya. Jika seseorang tidak sampai ke seberang sisi, maka sisi adalah jambatan. Carian lengkap seperti semua jiran tidak terlalu mahal. Tetapi jika seseorang perlu melakukannya sebelum menyeberangi setiap sisi, maka jumlah usaha adalah besar. Algoritma lengkap dipanggil algoritma Fleury, sejak tahun 1883.
Adakah terdapat algoritma yang lebih cekap?
Algoritma yang lebih cekap ialah Hierholzer (1873).
Sekiranya graf mempunyai 2 titik darjah ganjil, maka seseorang mendapati jalan sebaliknya kitaran, dalam kedua-dua kes sangat cepat tanpa memeriksa jambatan.
1) Selepas mengeluarkan semua sisi yang digunakan, darjah sisi yang tidak digunakan adalah walaupun untuk semua titik.
Mengapa?
Sekiranya darjah titik adalah genap, maka ia sama-sama sering didekati kerana ia ditinggalkan, jadi ia masih genap. Sekiranya darjah itu ganjil, maka ia adalah titik permulaan atau titik akhir laluan pertama dan kemudian ia dibiarkan + didekati dalam jumlah bilangan ganjil kali, jadi darjah yang tinggal adalah ganjil − ganjil = genap.
2) Mesti ada sekurang-kurangnya satu titik dengan sisi bersebelahan yang digunakan dan tidak digunakan.
Mengapa?
Kerana graf asal disambungkan.
Kerana 1) seseorang dapat mencari kitaran sisi yang tidak digunakan, bermula dan berakhir di titik ini. Kerana 2) kitaran ini boleh dimasukkan ke dalam laluan / kitaran pertama apabila ia mencapai titik ini. Pembenaman kitaran sisi yang tidak digunakan setakat ini diulang sehingga semua sisi digunakan dan oleh itu mempunyai laluan Eulerian atau kitaran Eulerian yang menggunakan semua sisi.
Berapakah harga versi yang lebih pantas ini?
Seseorang perlu mengingati laluan / kitaran sebelumnya supaya seseorang boleh memasukkan kitaran tambahan.
Sebagai contoh:
2 4 / \ / \ 1---3---5
Biarkan kitaran pertama menjadi 1-3-2-1. Titik 3 berlaku dalam kitaran ini dan dalam kitaran yang tidak digunakan 3-4-5-3. Kami memasukkannya ke dalam kitaran pertama dan mendapatkan kitaran 1-3-4-5-3-2-1. Tiada lagi sisi yang tidak digunakan jadi algoritma berakhir di sini, kami mendapati kitaran Eulerian.
Bagaimanakah kitaran boleh dimasukkan menggunakan antara halaman kita?
Seseorang boleh mengklik 'Buat asal' sehingga seseorang telah mencapai titik terkini yang telah menggunakan dan tidak digunakan sisi, seperti titik 3 di atas, dan kemudian melalui kitaran 3-4-5-3 dan kemudian teruskan dengan sisi yang tidak dilakukan.
Sekiranya terdapat titik darjah ganjil, adakah seseorang perlu mencari kedua-duanya untuk menarik jalan pertama dari satu ke yang lain?
Tidak. Jika seseorang hanya menemui satu, maka seseorang boleh memulakan laluan di titik ini dan satu akan secara automatik berakhir di titik darjah ganjil yang lain sama ada seseorang menggunakan semua sisi atau tidak.
Mengapa?
Kerana apabila seseorang tiba di titik darjah genap, maka bilangan sisi yang ganjil telah digunakan.
Mengapa?
Setiap kali seseorang tiba di titik, seseorang juga meninggalkan titik, jadi bilangan sisi genap digunakan. Sekarang, seseorang tiba dan menggunakan satu sisi pada titik darjah genap. jadi satu digunakan dalam jumlah bilangan sisi ganjil pada titik darjah genap.
Genap − ganjil = ganjil, oleh itu bilangan ganjil sisi yang tidak digunakan dibiarkan. Nombor ganjil sentiasa bukan sifar, jadi terdapat sekurang-kurangnya satu sisi yang tidak digunakan yang boleh digunakan untuk meninggalkan titik itu. Oleh itu, seseorang akan berakhir secara automatik pada titik darjah ganjil sama ada semua sisi digunakan atau tidak.
Adakah anda mempunyai cadangan bagaimana seseorang dapat mencari satu titik darjah ganjil?
Seseorang tentu saja boleh menyemak tahap setiap titik sehingga seseorang menemui titik darjah ganjil. Berikut adalah cara tanpa mengira.
Seseorang boleh memilih mana-mana titik. Sekiranya darjahnya ganjil, maka seseorang telah menemui satu. Jika tidak, maka seseorang bermula pada titik ini untuk menarik kitaran. Ia akan berakhir sama ada titik darjah ganjil, maka seseorang telah menemui titik darjah ganjil, atau satu akan berakhir pada titik permulaan. Jika ya, maka seseorang mengabaikan semua sisi yang digunakan dan melakukannya sekali lagi iaitu memilih titik dan lukis laluan atau kitaran. Ini berterusan sehingga seseorang sama ada menemui titik darjah ganjil atau tidak ada lagi sisi yang tidak digunakan. Kemudian semua titik mempunyai darjah genap.
Bagaimana jika graf itu seperti bandar dengan jalan-jalan 1 hala?
Graf dengan sisi yang hanya boleh dilalui dalam satu arah dipanggil graf yang diarahkan. Berikutan hujah di atas, 2 kenyataan berikut adalah munasabah.
Graf yang diarahkan membolehkan Kitaran Eulerian, jika dan hanya jika, untuk setiap titik bilangan sisi keluar adalah sama dengan bilangan sisi masuk.
Graf yang diarahkan membolehkan Laluan Eulerian, jika dan hanya jika
• satu titik mempunyai satu sisi yang keluar lebih daripada sisi masuk,• satu titik mempunyai satu sisi yang masuk lebih daripada sisi keluar,
dan • semua sisi lain mempunyai bilangan sisi keluar dan
masuk yang sama.
Ikuti atau langgan untuk kemas kini: