Lintasan Hamilton: Perbedaan antara revisi

Jelajahi riwayat secara interaktif

← Revisi sebelumnya

Konten dihapus Konten ditambahkan

VisualTeks wiki

Revisi per 1 November 2018 20.48 sunting Vale979 (bicara \| kontrib) Peninjau otomatis 62 suntingan k grafik -> graf (term yang lebih cocok dalam konteks ini) Tag: VisualEditor ← Revisi sebelumnya		Revisi terkini sejak 15 Desember 2022 05.33 sunting balikkan 114.10.11.181 (bicara) Tidak ada ringkasan suntingan Tag: Pengembalian manual Suntingan perangkat seluler Suntingan peramban seluler
(5 revisi perantara oleh 5 pengguna tidak ditampilkan)
Baris 2: [[Berkas:Hamiltonian path.svg\|jmpl\|Sebuah lintasan Hamilton dalam [[dodekahedron]].]] [[Berkas:Herschel graph.svg\|jmpl\|[[Graf (matematika)\|Graf Herschel]] adalah [[grafik polihedral\|graf polihedral]] terkecil yang mungkin yang tidak memiliki lintasan Hamilton.]] '''Lintasan Hamilton''' ~~ialah~~adalah lintasan yang melalui tiap verteks di dalam graf tepat satu kali. Bila lintasan itu kembali ke verteks asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit Hamilton adalah sirkuit yang melalui tiap verteks di dalam graf tepat satu kali, kecuali verteks asal (sekaligus verteks akhir) yang dilalui dua kali. Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton. Pada tahun 1859, Matematikawan dari Irish, [[Sir William Rowan Hamilton]] mengembangkan permainan yang di beli dari perusahaan mainan di Dublin. Permainan itu dinamakan Prominent Cities. Tujuan dari permainan iu adalah mencari sirkuit sepanjang jalan yang terbentuk sehingga di dalam itu terdapat 20 kota dan dapat dilewati tepat satu kali. Penulis dapat menggambarkan alat itu dengan sebuah graf : Verteks dari graf melambangakan verteks dari alat tersebut dan panjangnya edges disamakan dengan alat tersebut. Untuk menentukan sebuah graf itu adalah Siklus Hamilton atau tidak, pastinya lebih sulit ~~daripada~~dari pada menentukan itu Eulerian. ~~Dan~~Selain itu, tidak ada cara pasti yang diketahui untuk ~~menentukan itu~~menentukannya. Siklus dalam graf akan terbagi menjadi dua yaitu Euler dan Hamilton. Eulerian adalah sebuah siklus dalam graf yang memastikan bahwa dirinya telah melewati semua edges yang ada dalam graf tersebut. Dan tidak menjadi suatu masalah jika sebuah verteks dilewati sebanyak apapun. Tetapi pada Hamilton adalah sebuah siklus dalam graf yang memastikan bahwa dirinya telah melewati semua verteks dalam graf tersebut dan hanya tepat satu kali, kecuali verteks awal didatangi dua kali. Jika sebuah verteks itu telah dilewati dua atau lebih dalam suatu siklus maka siklus tesebut tidak dapat dikatakan sebagai siklus Hamiltonian.