Graf Lintasan: Quiz dan Flashcards Sirkuit Hamilton

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Apa syarat agar graf mempunyai suatu sirkuit Hamilton menurut ORE's Theorem?

jumlah derajat setiap pasang vertex yang tidak bersisian ≥ n (correct)

jumlah derajat setiap pasang vertex yang tidak bersisian ≥ n/2

jumlah vertex yang tidak bersisian ≥ n

jumlah vertex yang bersisian ≥ n

Berapa kali vertex e harus dilalui dalam lintasan Hamilton pada graf tertentu?

tidak dapat ditentukan

dua kali (correct)

satu kali

tiga kali

Apakah graf berikut mempunyai lintasan Hamilton?

tidak, karena vertex a berderajat 1

tidak dapat ditentukan

ya, karena graf mempunyai sirkuit Hamilton

tidak, karena graf tidak mempunyai sirkuit Hamilton (correct)

Apa syarat agar graf mempunyai suatu sirkuit Hamilton menurut DIRAC's Theorem?

setiap vertex mempunyai derajat ≥ n/2 Signup and view all the answers

Lintasan Hamilton adalah?

Lintasan yang melalui setiap vertex tepat sekali Signup and view all the answers

Graf apakah yang tidak mempunyai sirkuit Hamilton?

Graf dengan vertex berderajat 1 Signup and view all the answers

Aplikasi lain dari lintasan Euler dalam kehidupan sehari-hari adalah?

Mengirimkan pesan melalui jalan yang diperlukan Signup and view all the answers

Dalam ilmu biologi molekuler, lintasan Euler dapat digunakan untuk?

Mengurutan DNA Signup and view all the answers

Dalam desain layout sirkuit elektronik, lintasan Euler dapat digunakan untuk?

Menggunakan multicasting Signup and view all the answers

Lintasan Hamilton adalah sebuah lintasan yang melalui setiap v ∈ V tepat?

Satu kali Signup and view all the answers

Berdasarkan Ore's Theorem, apa syarat yang harus dipenuhi untuk memastikan adanya sirkuit Hamilton?

jumlah derajat setiap pasang vertex yang tidak bersisian ≥ n Signup and view all the answers

Apa yang membedakan lintasan Euler dan lintasan Hamilton?

Jumlah vertex yang dilalui Signup and view all the answers

Apa yang digunakan untuk menentukan adanya sirkuit Hamilton dalam graf berikut?

Dirac's Theorem Signup and view all the answers

Jika jumlah vertex pada graf > 3, maka apa syarat yang harus dipenuhi untuk memastikan adanya sirkuit Hamilton?

derajat setiap vertex ≥ n/2 Signup and view all the answers

Sirkuit Hamilton adalah sebuah sirkuit yang melalui setiap v ∈ V tepat?

Kecuali vertex awal dan akhir Signup and view all the answers

Apa yang dapat disimpulkan jika derajat setiap vertex ≥ n/2?

Graf pasti mempunyai sirkuit Hamilton Signup and view all the answers

Apa yang dapat disimpulkan jika tidak semua vertex mempunyai derajat ≥ n/2?

Tidak dapat disimpulkan Signup and view all the answers

Bagaimana cara menentukan adanya sirkuit Hamilton dalam graf?

Menghitung jumlah derajat setiap pasang vertex yang tidak bersisian Signup and view all the answers

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

Lintasan Hamilton: L =

Sirkuit Hamilton: S =

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.