Satu goresan
Simpul ganjil
Sisi tergambar
Cara menggambarnya

    • 0 simpul ganjil: sebuah sirkuit, dari simpul mana pun kembali ke simpul itu
    • 2 simpul ganjil: sebuah lintasan dari yang satu ke yang lain
    • 4 atau lebih: tidak mungkin dalam satu goresan

    Metode

    Selengkapnya tentang lintasan dan sirkuit Euler

    Pencari Lintasan Euler

    Bisakah Anda menggambar rumah Santo Nikolaus tanpa mengangkat pensil dan tanpa melewati garis dua kali? Bisa, tetapi hanya jika Anda mulai di salah satu dari dua sudut bawah, dan dari masing-masing ada 44 cara. Sebabnya adalah derajat sebuah simpul, yaitu banyaknya garis yang bertemu di sana: setiap kali pensil melewati sebuah simpul, ia memakai dua garisnya. Leonhard Euler menemukan aturan ini pada tahun 1736 lewat tujuh jembatan Königsberg. Telusuri sendiri sebuah gambar, lihat di mana dan mengapa Anda buntu, mintalah petunjuk, atau saksikan sebuah algoritma menggambarnya. Pilih sebuah gambar dan telusuri: ketuk sebuah simpul untuk memulai, lalu ketuk sisi-sisinya atau simpul berikutnya secara berurutan, atau seret dari simpul ke simpul. Setiap sisi hanya boleh dilalui sekali. Mundur membatalkan satu langkah, Petunjuk menunjukkan sisi aman berikutnya, dan Selesaikan memutar algoritma Fleury atau Hierholzer langkah demi langkah. Simpul ganjil digambar penuh, dan lencana pada setiap simpul adalah derajatnya. Dalam mode Gambar, ketuk ruang kosong untuk menambah simpul dan ketuk dua simpul untuk menghubungkannya, sekali lagi untuk sisi kedua; seret simpul untuk memindahkannya. Hapus membuang simpul dan sisi. Bila simpul ganjil lebih dari dua, Tambah memasukkan sisi-sisi yang membuat gambar bisa ditelusuri.

    Cara kerjanya

    1. Pilih sebuah gambar, seperti tujuh jembatan Königsberg, rumah Santo Nikolaus, atau sebuah bintang, atau gambar milik Anda sendiri dalam mode Gambar, dengan sebanyak apa pun sisi antara dua simpul.
    2. Ketuk sebuah simpul untuk memulai, lalu ketuk sisi atau simpul secara berurutan, atau seret dari simpul ke simpul. Jika buntu, baris status menjelaskan sebabnya; Mundur membatalkan satu langkah dan Petunjuk menunjukkan sisi yang aman.
    3. Baca aturan derajat di bawah gambar, tambahkan sisi-sisi yang disarankan pada gambar yang mustahil, atau tekan Selesaikan untuk melihat algoritma Fleury atau Hierholzer menggambarnya langkah demi langkah.

    Mengapa simpul ganjil yang menentukan

    Goresan yang melewati sebuah simpul masuk lewat satu garis dan keluar lewat garis lain, jadi ia memakai garis-garis simpul itu berpasangan. Hanya di tempat goresan dimulai atau diakhiri sebuah garis bisa tertinggal tanpa pasangan. Karena itu simpul dengan jumlah garis ganjil harus menjadi awal atau akhir. Tanpa simpul ganjil, goresan berakhir di tempat ia mulai: itulah sirkuit Euler. Dengan dua, ia berjalan dari yang satu ke yang lain: itulah lintasan Euler. Dengan empat atau lebih, ujungnya terlalu banyak untuk satu goresan, dan k simpul ganjil membutuhkan k/2 goresan. Königsberg punya empat daratan dengan lima, tiga, tiga, dan tiga jembatan: keempatnya ganjil, jadi tak ada perjalanan yang bisa melewati setiap jembatan sekali. Satu jembatan baru di antara dua daratan akan membuat perjalanan itu mungkin.

    Algoritma Fleury dan Hierholzer

    Mengetahui bahwa sebuah gambar bisa digambar tidak sama dengan menggambarnya: goresan yang ceroboh bisa memutus dirinya dari garis-garis yang masih dibutuhkan. Algoritma Fleury tahun 1883 mencegahnya dengan satu aturan: jangan pernah melewati jembatan, yaitu garis yang bila dibuang akan membelah garis-garis sisa menjadi dua bagian, kecuali tak ada garis lain. Algoritma Hierholzer, dari makalah yang terbit pada tahun 1873, lebih cepat: berjalanlah ke mana pun sampai buntu, yang hanya bisa terjadi di titik awal, lalu dari sebuah simpul pada tur yang masih punya garis bebas, tempuh satu lingkar tertutup lagi dan sisipkan ke dalam tur. Waktunya tumbuh sebanding dengan banyaknya sisi, dan begitulah komputer menemukan lintasan Euler.

    Pertanyaan yang sering diajukan

    Apa beda lintasan Euler dan sirkuit Euler?

    Keduanya memakai setiap sisi graf tepat sekali. Sirkuit Euler berakhir di tempat ia mulai; lintasan Euler berakhir di tempat lain. Graf terhubung memiliki sirkuit bila setiap simpul berderajat genap, dan lintasan bila tepat dua simpul berderajat ganjil; lintasan itu lalu berjalan dari yang satu ke yang lain.

    Mengapa tujuh jembatan Königsberg tidak bisa dilewati sekali masing-masing?

    Gambarlah setiap daratan sebagai simpul dan setiap jembatan sebagai sisi. Pulau Kneiphof punya lima jembatan dan tiga daratan lainnya tiga masing-masing, jadi keempat simpulnya ganjil. Sebuah perjalanan hanya bisa mulai atau berakhir di simpul ganjil, dan empat terlalu banyak. Menambah satu jembatan di antara dua di antaranya menyisakan dua simpul ganjil, dan perjalanan itu menjadi mungkin.

    Ada berapa cara menggambar rumah Santo Nikolaus?

    44 dari masing-masing dua sudut bawah, 88 seluruhnya, bila urutan atau arah yang berbeda dihitung sebagai cara yang berbeda. Dari simpul lain mana pun tidak bisa, karena hanya kedua sudut bawah itu yang jumlah garisnya ganjil. Aplikasi ini menghitung cara untuk gambar kecil dengan jalan seperti itu.

    Apa itu jembatan dalam graf?

    Sebuah sisi yang bila dibuang membelah graf terhubung menjadi dua bagian. Algoritma Fleury tak pernah melewati jembatan di antara sisi-sisi yang tersisa selama masih ada pilihan lain, sebab sebagian gambar akan tertinggal. Dalam aplikasi ini, goresan yang buntu setelah melewati jembatan terlalu dini diberi tahu langkah keberapa itu terjadi.

    Bolehkah ada lebih dari satu sisi antara dua simpul?

    Boleh. Graf dengan sisi sejajar disebut multigraf, dan Königsberg memerlukannya: dua jembatan menghubungkan Kneiphof dengan masing-masing tepian. Dalam mode Gambar, ketuk lagi dua simpul untuk menambah satu sisi lagi di antaranya, sampai empat. Aturan derajat tetap berlaku dan menghitung setiap sisi.

    Siap mencobanya?

    Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

    Ke Editor