DEKOMPOSISI DAN SIKLUS Hamilton

Oleh :

1. Fatimatuz Zahro’ (100311404211)

2. Harwati (100311404215)

Perhatikan gambar berikut!

Jika kita memberi warna sisi dari graph G dengan dua warna merah dan biru, tanpa ada batasan, maka sisi merah merupakan bentuk subgraph H1 dari G, dan sisi biru bentuk subgraph H2 dari G. H1 dan H2 semua di GKita mengatakan bahwa G dekomposisi menjadi H1 dan H2.

DEKOMPOSISI DAN SIKLUS Hamilton

suatu graph G dikatakan dekomposisi menjadi subgraph H1,

H2, ..., Ht, jika sebarang dua subgraph Hi dan Hj tidak mempunyai sisi yang sama, dan gabungan dari semua subgraph Hi adalah G.

Dekomposisi ini memiliki aplikasi langsung ke round-robin turnamen catur, tenis, dll Katakanlah kita memiliki sepuluh pemain. Kemudian mengidentifikasi pemain dengan nomor 0, 1, ..., 8, x. Dan ia membaca pasangan dari gambar seperti ini:

Putaran pertama O x 1 8 2 7 3 6 4 5Putaran kedua 1 x 2 0 3 8 4 7 5 6dan sebagainya.

• Lintasan Hamilton ialah lintasan yang melalui tiap vertex di dalam graph tepat satu kali.

• Siklus Hamilton ialah siklus yang melalui tiap vertex di dalam graph tepat satu kali, kecuali vertex asal (sekaligus vertex akhir) yang dilalui dua kali.

• Graph yang memiliki siklus Hamilton dinamakan graph Hamilton, sedangkan graph yang hanya memiliki lintasan Hamilton disebut graph semi-Hamilton.

• kita tahu bahwa K2n-1 tidak memiliki 1-faktor, karena jumlah simpulnya ganjil.

• Tapi dengan Teorema 2.2.4, K2n-1 memiliki dekomposisi menjadi 2n-1 subgraphs, setiap isomorfis ke grafik dari gambar 2.2.4. subgraphs ini dapat digambarkan tanpa titik terisolasi, karena dekomposisi hanya mengacu pada sisi-sisinya

• Gambar 2.3.1 menunjukkan rencana kebun binatang. Setiap titik mewakili kandang dengan hewan yang menarik. Sisi-sisinya merupakan suatu jalur. Seorang pengunjung ingin memasuki kebun binatang katakan pada titik 1, dan mengunjungi setiap kandang tepat satu kali, kemudian kembali pada akhir vertex 1. Inilah yang disebut siklus Hamilton.

Simpul dari siklus secara berurutan adalah 1,2, 3, dan seterusnya. Hal ini terjadi dalam grafik yang memiliki beberapa sisi, misalnya sisi dari 1 sampai 9, yang tidak terdapat dalam sebarang siklus Hamilton. Dengan kata lain, anda tidak dapat menemukan siklus Hamilton melalui sisi dari 1 sampai 9.

Gambar 2.3.2 adalah gambar dari graph komplit K7. kita dapat mengetahui bahwa K7 berisi siklus Hamilton. Berikut ini adalah siklus Hamilton di K7.0 1 2 3 4 5 6.Kemudian kita dapat menemukan satu diantara yang lain lain,0 2 4 6 1 3 5,yang tidak memuat sisi dari siklus pertama. Ada satu lagi, yang tidak mengandung sisi dari pertama yang kedua

Yaitu, 0 4 1 5 2 6 3jadi kita dapat mengatakan bahwa K7 adalah decomposable menjadi tiga siklus dari panjang tujuh

• Teorema 2.3.1 (Lucas) graph komplit K2n +1 memiliki dekomposisi menjadi n Hamilton siklus.

• Untuk K2n+1 simpul dilambangkan dengan 0, 1, 2, . . . , 2n-1, x dan kita memilih siklus

• Teorema 2.3.2. K2n memiliki dekomposisi menjadi n-1 siklus Hamilton dan suatu 1 -faktor.

pembuktian dari Teorema 2.3.2 menggunakan 1-faktor yang disajikan pada pembuktianTeorema 2.2.3. Ambil dua 1-faktor yang pertama, C1 dan C2, untuk membentuk Hamilton siklus yang pertama; C3 dan C4 untuk yang kedua, dan seterusnya. Maka 1-faktor C2n-1 akan tersisa.

• Sebuah lintasan Hamilton dalam graf G adalah lintasan yang memuat setiap vertex (titik) dari G.Karena setiap lintasan juga pohon, suatu lintasan Hamilton di G adalah rentangan pohon dari G.Jelas, jika graph memiliki siklus Hamilton, juga memiliki lintasan Hamilton, tetapi kebalikannya tidak benar.

• Ada grafik yang memiliki lintasan Hamilton tapi tidak Hamilton siklus. Contoh yang mudah adalah lintasan Pn. Sebuah contoh yang lebih menarik adalah graph Petersen. Kita telah melihat bahwa K2n tidak memiliki dekomposisi menjadi siklus Hamilton. Namun, memiliki dekomposisi menjadi lintasi Hamilton

• Teorema 2.3.3. K2n memiliki dekomposisi menjadi n lintasan Hamilton.

Untuk membuktikan hal ini cukup elegan, pertimbangkan K2n + 1, yang kita tahu memiliki sebuah dekomposisi ke dalam n siklus Hamilton. Sekarang kita menghapus vertex (titik) dari K2n + 1, sehingga mendapatkan dekomposisi yang diinginkan K2n ke dalam n lintasan Hamilton. Lihat Gambar 2.3.3, dan mengabaikan vertex (titik) x. Kita dapat menggunakan Teorema 2.3.3 untuk menunjukkan bahwa K10 dapat didekomposisi menjadi suatu P1, suatu P2, suatuP3, .... suatu P8, dan suatu P9. Berdasarkan Teorema 2.3.3, K10 memiliki dekomposisimenjadi lima lintasan Hamilton, masing-masing yang merupakan P9. Kita mengambil satu yaitu untuk P9, kemudian membagi sisanya menjadi P1 dan P8, P2 dan P7, P3 dan P6 , P4 dan P5.

• Teorema 2.3.4. Graph komplit K2n memiliki dekomposisi ke dalam 2n-1 lintasan yang terdiri dari satu lintasan dari masing-masing panjang k untuk k = 1 2,3, ..., 2n-1.

Contoh untuk 2n = 10 secara umum mudah untuk pembuktian Teorema umum.Sekarang kita menyebutkan masalah yang belum terpecahkan. Dugaan (Gyarfas, Lehel) [9]. Diberikan T1, T2, ..., T2n-1, di mana masing-masing Ti adalahpohon dengan i sisi, diduga bahwa K2n dapat dipecah menjadi sebanyak pohon yangdiberikan.

• Ingatlah bahwa snark adalah graph kubik dengan bilangan kromatk empat

• Teorema 2.3.5. suatu Snark tidak memiliki siklus Hamilton.

Bukti:• Misalkan G menjadi snark, dan misalkan G memiliki siklus

Hamilton. Warna sisi dari siklus dengan alternatif warna 1 dan 2. Ini adalah sisi yang tepat untuk mewarnai siklus, karena jumlah simpulnya genap. Warnai sisi yang tersisa dalam graph dengan warna 3. Di setiap vertex (titik) ada dua sisi dari siklus, salah satunya diwarnai 1 dan salah satunya adalah berwarna 2, dan sisi ketiga berwarna 3. Dengan demikian kita dapat mewarnai sisi G hanya dengan tiga warna, yang bertentangan dengan fakta bahwa G adalah suatu snark. Oleh karena asumsi kita bahwa G memiliki siklus Hamilton salah. ■

• Konvers dari Teorema 2.3.5 tidak benar. Graph dari gambar 2.3.4 dan 2.3.5 sisinya yang berhasil diwarnai dengan tiga warna, tetapi tidak memiliki siklus Hamilton. Mereka memiliki lintasan Hamilton.Secara umum sangat sulit untuk mengetahui apakah graph tertentu memiliki siklus Hamiltonatau lintasan Hamilton.

Graph dari Gambar 2.3.6 berisi siklus Hamilton