MODUL 5 KULIAH 9
LINTASAN HAMILTON & SIRKUIT HAMILTON :
- Sirkuit Hamilton dalam suatu graph G : Adalah sirkuit yang melalui setiap vertex dalam graph G tepat sekali kecuali vertex awal yang sama dengan vertext akhir.
TEOREMA : Jika G adalah graph dengan n vertex dan jumlah derajat dari setiap pasangan vertex di G adalah n-1 atau > (n-1) maka di G ada lintasan Hamilton.
Bukti : ………………. (konstruksi)
1. Buktikan graph terhubung 2. Konstruksi lintasan Hamilton
1. G adalah graph dengan n vertex. Jumlah derajat setiap pasangan vertex di G adalah (n-1). Akan ditunjukkan G terhubung Misalkan G tak terhubung, maka G terdiri dari 2 atau lebih komponen. Misalkan G1 dan G2 adalah komponen dari G. G1 dengan n1 vertex dan G2 dengan n2 vertex. Ambil v1 di G1 dan v2 di G2. Derajat dari vertex v1 maksimum adalah n1-1. Derajat dari vertex v2 maksimum adalah n2-1. Jumlah derajat pasangan v1 dan v2 maksimum adalah (n1+n2)-2 < (n-1). Kontradiksi dengan hipotesa. Jadi haruslah G terhubung. 2. Konstruksi lintasan Hamilton. - mulai dai lintasan dengan sisi tunggal. - Kemudian misalkan ada lintasan dengan p-1 sisi, p < n, dengan vertex yang dilalui lintasan tersebut adalah P = (v1,…….vi,………vp).
Di sini timbul beberapa kasus :
a. Jika v1 atau vp adjacent dengan vertex lain tidak pada lintasan maka lintasan dapat lansung ditambah sedemikian sehingga diperoleh lintasan dengan p sisi. b. Jika v1 dan vp tidak adjacent dengan vertex lain dari pada vertex-vertex yang ada di P, berarti v1 dan vp hanyaadjacent dengan salah satu vertex dari v1,v2,……………,vi,…………..,vp-1,vp. Akan ditunjukkan bahwa terdapat sirkuit yang memuat tepat v1,…………..,vp. B1. Bila v1 adjacent dengan vp maka terjadi sikuit yang dimaksud S = (v1,………vp,v1).
B2. Bila v1 adjacent hanya dengan vertex vi1,vi2,……,vik dimana 2 <= i1,i2,……….,ik <= p – 1 dan vp adjacent dengan salah satu vertex dari vi1-1,vi2-1,……….,vik-1. Misalkan vj-1 maka sikuitnya adalah S = (v1,v2,………….,vj-1,vp,vp-1,………….,vj,v1) yang memuat tepat vertex v1,………….,vp. Lihat contoh-36a.
v1
v2
vj
v3
vp
vj-1
Contoh-36a
B3. Bila v1 adjacent hanya dengan vertex vi1,vi2,………….,vik dimana 2 < i1,i2,…………..,ik < p –1 dan vp tidak adjacent dengan salah satu vi1-1,vi2-1…….,vik-1 maka vp adjacent paling banyak dengan p-k-1 vertex. Akibatnya jumlah derajat pasangan v1 dan vp paling banyak k + (p-k-1), sedangkan k + (p-k-1) = p-1
< n-1 kontradiksi
jadi sekarang dipunyai sirkuit S yang tepat memuat p vertex, v1,…….,vp.
Misalkan masih ada vertex-vertex yang tidak termasuk di S karena G terhubung, maka di antara vertex-vertex yang tidak termasuk di sirkuit S ada vertex vx yang adjacent dengan salah satu vertex dari v1,…..,vk,……,vp. Misalkan, lihat contoh-36b, maka akan diperoleh lintasan P’ = (vx,vk,vk+1,….,vj-1,vp,vp-1,sisi, lihat contoh-36c. vx
v1
v2 vp
vj-1
vk-1
vj
vk
Contoh-36b vx
v1
v2 vp
vj-1
vk-1
vj
vk
Contoh-36c.
Proses ini diulangi sampai dipunyai lintasan elementer dengan n-1 sisiyang merupakan lintasan Hamilton
Catatan :
1. Setiap lintasan Hamilton di graph dengan vertex terdiri dari n-1 sisi. 2. Setiap sirkuit Hamilton di graph dengan n vertex terdiri dari n sisi. 3. Tidak setiap graph yang terhubung mempunyai lintasan Hamilton atau sirkuit Hamilton Contoh : Graph contoh 37-a di bawah ini tidak memmiliki lintasan Hamilton
A
B
B B A
A A B A B
A
B
A
A
A Contoh 37
B
Bukti : Beri label A untuk vertex v1, beri label B setiap vertex yang adjacent dengan v1 lalu beri label A lagi untuk setiap vertex yang adjacent dengan vertex berlabel B dan …. l
…………….memiliki sirkuit Hamilton pasti ………………….. tetapi graph yang memiliki lintasan hamilton belum tentu memiliki sirkuit Hamilton.
Contoh : Graph di bawah ini memiliki lintasan Hamilton tapi tidak memiliki sikuit Hamilton.
(a)
(b) Contoh-37
5. Teorema di atas adalah syarat cukup untuk suatu graph dengan n vertex untuk memiliki lintasan Hamilton, tetapi bukan syarat perlu.
Contoh : Graph G dengan 6 vertex yang memiliki lintasan Hamilton tetapi jumlah derajat setiap pasang vertexnya adalah 4. sedangkan 4 < 5.
Contoh-38
Definisi : Suatu graph berarah G dikatakan komplit simetri bila dari setiap vertex di edge ke setiap vertex lainnya di G.
G ada
Definisi : suaru graph berarah G dikatakan komplit asimetris bila untuk setiap pasang vertex di G ada edge yang menghubungkannya. Catatan : Setiap graph berarah yang komplit simetris dengan n vertex memiliki n(n-1) sisi. Sedangkan berarah yang komplit asimetris dengan n vertex memiliki n(n-1) sisi. TEOREMA : Jika G adalah graph berarah dan komplit asimetris, maka selalu ada sirkuit Hamilton di G. Bukti : Misalkan P = (v1, v2, …, vp) adalah suatu litsan dengan p-1 sisi di g. misalkan vx adalah suatu vertex di luar lintasan p. Karena G komplit asimetris, maka salah satu sisi (vx, v1) atau sisi (v1, vx) ada di G. Jika (vx, v1) di G, perpanjang lintasan P menjadi P’ = (vx, v1, v2, …, vp) Jika (v1, vx) yang ada di G, maka perhatikan sisi (vx, v2) atau sisi (v2, vx) di G. Jika (vx, v2) di G, ganti (v1, v2) dengan (v2, vx) dan (vx, v3). Jika (v2, vx) yang di G, maka perhatikan sisi (vx, v3) atau sisi (v3, vx) di G. jika (vx, v3) di G, ganti (v2, v3) dengan (v2, vx) dan (vx, v3). Jika (v3, vx) yang di G, maka perhatikan sisi (vx, v4) atau sisi (v4, vx) di G. Jika (vx, v4) di G, ganti (v3, v4) dengan (v3, vx) dan (vx, v4). Maka pada akhirnya pasti vx dapat masuk ke lintasan P’ yang merupakan perpanjangan dari lintasan P dan terdiri dari p sisi. Dengan demikian semua vertex di G dapat masuk dalam perpanjangan dai lintasan P, yang merupakan lintasan Hamilton. Teorema : Jika G adalah graph berarah yang komplit simetri, maka G pasti memiliki lintasan Hamilton.
Teorema : Dia dalam setiap graph komplit G dengan n vertex terdapat (n-1) !/2 sirkuit Hamilton. Bukti : Ambil sembarang vertex v1 di G, dari v1 ada n-1 pilihan untuk v2, dari v2 ada n-2 pilihan untuk v3, dan seterusnya, maka ada (n-1) ! lintasan yang mungkin, tapi setiap lintasan ini dihitung 2 kali, maka banyaknya lintasan Hamilton sesungguhnya adalah (n-1) !/2. Teorema : Di dalam suatu graph komplit G dengan n vertex ada (n-1) /2 edge-disjoint sikuit Hamilton, jika n ganjil dan lebih besar dari 3. Bukti : Suatu graph komplit G dengan vertex memiliki n(n-1) /2 sisi. Sedangkan setiap sirkuit Hamilton di G terdiri dari n sisi. Maka banyaknya edge-disjoint lintasan Hamilton di tidak akan lebih dari (n-1) buah. BilaG mempunyai n vertex ganjil, maka vertex-vertexnya dapat digambarkan pada suatu lingkaran seperti pada contoh-39a. Sirkuit Hamilton pertama adalah S1 = (1, 2, 3, 4, 5, …, n-3, n-2, n-1, n) Misalkan n = 9, jadi S1 = (1, 2, 3, 4, 5, 6, ,7 , 8, 9, 1)
3
5
2
7 1
2
9
8
4 6
Contoh-39a
3 5 1
4
7
9
6 8
Contoh-39b
Untuk mendapati sikuit Hamilton lainnya yang edge-disjoin dengan S1 dilakukan pemutaran posisi vertex- vertex pada keliling lingkaran tersebut sebesar 360 / (n-1) derajat atau 360 / (9-1) = 45 derajat menjadi apa yang terlihat pada contoh39b. Sirkuit hamilton kedua yang egde-disjoin dengan S1 adalah S2 = (1, 4, 2, 6, 3, 8, 5, 9 , 7, 1)
Untuk mendapati sikuit hamilton berikutnya yang edge-disjoint dengan sikuit Hamilton yang sudah ada, lakukan pemutaran lagi sebesar 360 / (n-1) derajat. Pemutaran ini dapat dilakukan (n-3) / 2 kali maka akan terdapat sikuit Hamilton yang saling edge-disjoint sebanyak (n-3) /2 + 1 = (n-1) /2. Untuk n =9, maka terdapat (9-1) /2 = 4 sirkuit Hamilton yang saling edge-disjoint. Lihat contoh-39c dan contoh-39d. Dan sirkuit Hamiltonnya adalah S3 = (1, 6, 4, 8, 2, 9, 3 , 7, 5, 1) S4 = (1, 8, 6, 9, 4, 7, 2 , 5, 3, 1)
2
4
6 3 1
6
5
2 1
8
7
8
4
5
9
9
3
7
Contoh : Problema pemberian peringkat kepada bebrapa produk makanan anjing, misalnya ada 6 macam produk. Dibuat suatu eksperimen sebagai berikut : Setiap hari dua macam produk diberikan kepada seekor anjing, dilihat produk mana yang lebih disukai oleh anjing tersebut, eksperimen ini membutuhkan 15 hari, supaya semua produk dapat dibandingkan. Maka hasil eksperimen ini dapat digambarkan dalam suatu graph berarah G, lihat contoh-40. Grpah G terdiri dari 6 vertex yang mewakili masing-masing produk, bila si anjing lebih suka produk 1 dari produk 2 maka arah panah pada sisi yang menghubungkan 1 dan 2 dari 1 ke 2
1
2
6
3
5 Contoh-40
4
Dari contoh-40 terlihat bahwa produk 1 lebih disenangi dari pada produk 2, produk 2 lebih disenangi dari pada produk 4 dan produk 4 lebih disenangi dari produk 1, dalam hal ini tidak dapat ditentukan mana yang lebih disukai sesungguhnya. Jadi untuk menentukan peringkat dari produk-produk tersebut dapat ditentukan dari lintasan Hamilton yang ada adalah 13 2 56 4 13 5 62 4 13 6 25 4 maka keenam produk dapat diberi 3 macam peringkat.
Contoh lain adalah traveling salesman problem Misalkan graph berbobot G = peta route antara n kota dengan bobot setiap sisi merupakan jarak antara kedua kota yang bersangkutan. Hendak ditentukan tour ke n kota dengan jarak minimum, melalui tiap kota hanya sekali, dan kembali ke tempat kota asal. Problem ini dapat diperpanjang sebagai mencari sirkuit Hamilton dengan jarak lintasan terdekat.
