Lintasan dan Sirkuit Hamilton

Lintasan dan Sirkuit Hamilton

Lintasan dan Sirkuit Hamilton – Melihat judul ini, mimin yakin sobat beautymatika sudah menyadari bahwa materi ini akan sangat berkaitan dengan materi graf. Yap, benar bahwa lintasan dan sirkuit hamilton merupakan materi dari graf. Kesempatan kali ini mimin akan memberikan penjelasan mengenai lintasan dan sirkuit hamilton. Pembahasan akan melingkupi pada pengertian dan juga contoh soal.

Tanpa berlama-lama lagi, yuk langsung saja kita pelajari bersama-sama materi lintasan dan sirkuit hamilton 💨

Daftar isi

1. Pengertian Graf Hamilton
2. Lintasan Hamilton
3. Sirkuit Hamilton
4. Contoh soal
5. Penutup

Pengertian Graf Hamilton

Graf hamilton sebenarnya memiliki pengertian yang mirip dengan graf euler. Graf hamilton adalah graf yang memuat lintasan dan sirkuit hamilton. Secara sederhana dapat dikatakan bahwa suatu graf disebut graf hamilton jika memiliki lintasan dan sirkuit hamilton.

Lintasan Hamilton

Sobat beautymatika pasti mengetahui bahwa lintasan adalah suatu jalan yang dilalui oleh suatu objek. Pengertian ini juga tidak jauh berbeda dengan lintasan hamilton. Lintasan hamilton merupakan lintasan yang mengunjungi tiap simpul/vertex graf tepat sekali.

Untuk lebih memudahkan, sobat beautymatika dapat melihat contoh berikut :

Contoh graf dengan lintasan hamilton

Ini merupakan lintasan hamilton dengan lintasan A-B-C-D-E yang melewati tiap simpul tepat 1 kali.

Sirkuit Hamilton

Sirkuit hamilton adalah jalur yang mengunjugi setiap simpul/vertex tepat 1 kali tanpa ada pengulangan. Hal penting yang sobat beautymatika ingat adalah sirkuit hamilton tidak perlu melalui setiap sisi. Sirkuit hamilton hanya perlu melewati vertex/simpul.

Untuk lebih memudahkan, sobat beautymatika dapat melihat contoh berikut :

Contoh graf dengan sirkuit hamilton

Sirkuit hamiltonnya adalah A-B-C-D-E-A. Ingat bahwa tidak masalah jika ada sisi yang tidak dilalui. Pada graf diatas tetap memiliki sirkuit hamilton meskipun sisi EC dan DB tidak dilalui.

Contoh soal

Untuk menambah pemahaman, sobat beautymatika dapat mempelajari contoh berikut :

1.     Apakah graf berikut memiliki lintasan dan sirkuit hamilton ?

Graf 1

Jawaban : Ya. Graf diatas memiliki lintasan hamilton, yaitu A-B-C-D-E. Graf diatas juga memiliki sirkuit hamilton, yaitu A-B-C-D-E-A.

2.     Apakah graf berikut memiliki lintasan dan sirkuit hamilton ?

Graf 2

Jawaban : Ya. Graf diatas memiliki lintasan hamilton, yaitu A-E-B-C-D. Graf diatas juga memiliki sirkuit hamilton, yaitu A-E-B-C-D-A.

3.     Apakah graf berikut memiliki lintasan dan sirkuit hamilton ?

Graf 3

Jawaban : Tidak, graf diatas tidak memiliki lintasan dan sikuit hamilton. Contoh jika disusun lintasan A-C-B-D-E-F, tidak termasuk lintasan karena melewati 2 simpul/vertex sebanyak 2 kali, yaitu simpul C dan D. Sirkuit juga tidak akan terbentuk karena pada lintasan sudah terbukti bahwa ada 2 simpul/vertex yang dilewati sebanyak 2 kali.

Penutup

Demikian materi singkat yang dapat mimin bagikan untuk sobat beautymatika mengenai lintasan dan sirkuit hamilton. Mimin yakin sobat beautymatika mampu menguasai materi ini dengan baik. Tetap semangat belajar dan sampai jumpa di materi lainnya.

 

 

 

 

Bagikan Artikel ini