Simulic
Bahasa Indonesia

Lintasan dan sirkuit Euler – tujuh jembatan Königsberg

MatematikaHimpunan, logika, dan teori grafUsia 16–17

Memuat…

Bagikan Laporkan masalah

Gambar atau ubah sebuah graf (simpul adalah daratan, sisi adalah jembatan) dan langsung lihat derajat setiap simpul, jumlah derajat yang sama dengan dua kali banyak sisi, serta kesimpulan dari banyak simpul berderajat ganjil: ada sirkuit Euler, ada lintasan Euler, atau tidak ada keduanya. Ketuk sisi sendiri untuk mencoba melewati setiap sisi tepat satu kali, atau biarkan algoritma Fleury (hindari jembatan) atau Hierholzer (sambung sirkuit) mencari rutenya langkah demi langkah.

Pelajaran: Lintasan Euler dan sirkuit Euler

Yang ditunjukkan

Pada 1736 Leonhard Euler bertanya apakah sebuah jalan-jalan di Königsberg dapat melewati masing-masing dari tujuh jembatannya tepat satu kali. Dengan mengubah daratan menjadi simpul dan jembatan menjadi sisi, ia menunjukkan bahwa jawabannya hanya bergantung pada derajat. Graf terhubung memiliki sirkuit Euler jika semua simpul berderajat genap, dan lintasan Euler jika tepat dua simpul berderajat ganjil; lintasan itu berawal di satu simpul ganjil dan berakhir di simpul ganjil lainnya. Simulasi ini mengizinkan beberapa sisi di antara dua simpul yang sama, tetapi tidak ada gelang, dan peta Königsberg disederhanakan.

Cara menggunakan

Mulailah dengan Tujuh jembatan Königsberg lalu baca derajat dan kesimpulannya. Ubah Mode ke Telusuri sendiri dan ketuk sisi-sisi untuk mencoba melewati setiap jembatan satu kali. Dalam mode Gambar / geser, tambahkan atau hubungkan simpul sampai kesimpulannya berubah, lalu pilih Fleury (hindari jembatan) atau Hierholzer (sambung sirkuit) dan tekan Langkah atau Jalankan untuk melihat rute terbentuk.

Parameter yang dapat diubah

  • Graf awal Tujuh jembatan Königsberg, Amplop (gambar tanpa mengangkat pensil), Dua segitiga dengan satu simpul bersama, Graf lengkap 5 simpul (K5), Halaman kosong – gambar sendiri
  • Algoritma Fleury (hindari jembatan), Hierholzer (sambung sirkuit)
  • Kecepatan animasi 0,5–4 sisi/detik

Pertanyaan untuk dijelajahi

  1. Mengapa tidak mungkin melewati setiap jembatan dari tujuh jembatan Königsberg tepat satu kali?
  2. Paling sedikit berapa jembatan yang harus Anda tambahkan agar ada lintasan Euler, dan di mana?
  3. Mengapa lintasan Euler harus berawal di satu simpul ganjil dan berakhir di simpul ganjil lainnya?

Simulasi terkait