18 Questions
Apa syarat agar graf mempunyai suatu sirkuit Hamilton menurut ORE's Theorem?
jumlah derajat setiap pasang vertex yang tidak bersisian ≥ n
Berapa kali vertex e harus dilalui dalam lintasan Hamilton pada graf tertentu?
dua kali
Apakah graf berikut mempunyai lintasan Hamilton?
tidak, karena graf tidak mempunyai sirkuit Hamilton
Apa syarat agar graf mempunyai suatu sirkuit Hamilton menurut DIRAC's Theorem?
setiap vertex mempunyai derajat ≥ n/2
Lintasan Hamilton adalah?
Lintasan yang melalui setiap vertex tepat sekali
Graf apakah yang tidak mempunyai sirkuit Hamilton?
Graf dengan vertex berderajat 1
Aplikasi lain dari lintasan Euler dalam kehidupan sehari-hari adalah?
Mengirimkan pesan melalui jalan yang diperlukan
Dalam ilmu biologi molekuler, lintasan Euler dapat digunakan untuk?
Mengurutan DNA
Dalam desain layout sirkuit elektronik, lintasan Euler dapat digunakan untuk?
Menggunakan multicasting
Lintasan Hamilton adalah sebuah lintasan yang melalui setiap v ∈ V tepat?
Satu kali
Berdasarkan Ore's Theorem, apa syarat yang harus dipenuhi untuk memastikan adanya sirkuit Hamilton?
jumlah derajat setiap pasang vertex yang tidak bersisian ≥ n
Apa yang membedakan lintasan Euler dan lintasan Hamilton?
Jumlah vertex yang dilalui
Apa yang digunakan untuk menentukan adanya sirkuit Hamilton dalam graf berikut?
Dirac's Theorem
Jika jumlah vertex pada graf > 3, maka apa syarat yang harus dipenuhi untuk memastikan adanya sirkuit Hamilton?
derajat setiap vertex ≥ n/2
Sirkuit Hamilton adalah sebuah sirkuit yang melalui setiap v ∈ V tepat?
Kecuali vertex awal dan akhir
Apa yang dapat disimpulkan jika derajat setiap vertex ≥ n/2?
Graf pasti mempunyai sirkuit Hamilton
Apa yang dapat disimpulkan jika tidak semua vertex mempunyai derajat ≥ n/2?
Tidak dapat disimpulkan
Bagaimana cara menentukan adanya sirkuit Hamilton dalam graf?
Menghitung jumlah derajat setiap pasang vertex yang tidak bersisian
Study Notes
Lintasan dan Sirkuit Hamilton
- Lintasan Hamilton adalah sebuah lintasan yang melalui setiap vertex tepat satu kali.
- Sirkuit Hamilton adalah sebuah sirkuit yang melalui setiap vertex tepat satu kali (kecuali vertex awal dan akhir).
Contoh Lintasan dan Sirkuit Hamilton
Teorema Ore
- Jika G adalah graf sederhana dengan n buah vertex (n ≥ 3) sedemikian hingga jumlah derajat setiap pasang vertex yang tidak bersisian ≥ n maka G mempunyai suatu sirkuit Hamilton.
Teorema Dirac
- Jika G adalah graf sederhana dengan n buah vertex (n > 3) dengan setiap vertex mempunyai derajat ≥ n/2 maka G mempunyai suatu sirkuit Hamilton.
Aplikasi Lintasan dan Sirkuit Euler
- Postman problem: mencari cara agar seorang petugas pos harus melalui semua jalan yang diperlukan untuk menyampikan pesan dimana setiap jalan cukup dilewati satu kali.
- Electronic and Networking Layout: membuat sirkuit elektronik atau network multicasting yang efisien dengan memanfaatkan lintasan/sirkuit Euler.
- Molecular biology: Lintasan Euler dapat digunakan pada pengurutan DNA.
Temukan lintasan dan sirkuit Hamilton pada graf berikut. Contoh soal dan jawaban untuk materi Matematika Diskret 2.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
