ALGORITMA DUA SISI OPTIMAL

Algoritma Penyisipan-titik

INPUT                        : Graph bobot komplit dengan n titik, n > 3

STEP 1            : Pilih sebuah G sebarang untuk membentuk sikel-1 C1 di G.

STEP 2            : Jika sikel-k Ck di G telah terbentuk dan 1 ≤ n < k, maka tentukan sebuah titik vk yang tidak terletak di Ck dan terdekat ke sebuah titik uk di Ck sikel Hamilton yang di kehendaki dan stop.

STEP 3            : Misal Ck+1 adalah sikel-(k+1) yang di dapat dengan menyisipkan titik vk persis sebelum uk di Ck dan kembali ke STEP 2.

Langkah-langkah di atas dapat disajikan secara sistematis sebagai berikut ini :

Algoritma Dua-sisi Optimal

INPUT                        : G graph komplit berbobot dengan n titik

STEP 1            : Misalkan C = (v1, v2, …, vn, v1) sebuah sikel Hamilton di G dengan bobot W = w(v1v2)+w(v2v3)+…+w(vnv1).

STEP 2            : Tulis i = 1.

STEP 3            : Tulis j = i + 2

STEP 4            : Modifikasi Sikel Hamilton C menjadi sikel Hamilton Cij sedemikian hingga Cij = (v1, v2, …, vi, vj, vj-1, …, vi+1, vj+1,vj+2, …, vn, v1).

Misalkan W ij adalah bobot sikel Hamilton Cij .

Jika Wij < W, ganti C dengan Cij dan ganti W dengan Wij , label ulang titik-titik C yang baru dengan v1, v2, …, vn, dan kembali ke STEP 1.

STEP 5            : Tulis j = j + 1.

Jika j ≤ n, kerjakan STEP 4, jika tidak tulis i = i + 1.

Jika i ≤ n-2, kerjakan STEP 3; jika tidak STOP.

Sebagai contoh penerapan algoritma ini, perhatikan kembali graph G berikut :

STEP 1

Misalnya, pertama kita pilih sikel hamilton C = (v1, v2, v3, v4, v5, v1) dengan w(C)=W=2+3+1+2+4=12. Untuk mempermudah, kita beri label C sebagai berikut C = (v1, v2, v3, v4, v5, v1) = (1,2,3,4,5,1)

STEP 2

i=1

STEP 3

j= i + 2 = 3

STEP 4

Konstruksi C13 =(1,3,2,4,5,1) = (v1, v3, v2, v4, v5, v1); W13 = 1+3+2+2+4= 12. Karena W13 ≥ W, maka C tetap.

STEP 5

J = 3+1 = 4 ≤ 5 = n

STEP 4

Konstruksi C14 =(1,4,3,2,5,1) = (v1, v4, v3, v2, v5, v1); W13 = 3+1+3+2+4= 13. Karena W14 ≥ W, maka C tetap.

STEP 5

J = 4+1 = 5 ≤  n

STEP 4

Konstruksi C15 = (1,5,4,3,2,1) = (v1, v5, v4, v3, v2, v1); W15 = 4+2+1+3+2= 12. Karena W15 ≥ W, maka C tetap.

STEP 5

J = 5+1 = 6 >  n

Tulis I = 1+1=2. Karena i=2 ≤ n-2, ke Step 3

STEP 3

J= i + 2 = 2+2 = 4

STEP 4

Konstruksi C24 = (1,2,4,3,5,1) = (v1, v2, v4, v3, v5, v1); W24 = 2+2+1+2+4= 11. Karena W24 < W, maka diperoleh  C yang baru dengan C = C24 = (v1, v2, v4, v3, v5, v1) dan W = W24 = 11. Ke step 1.

STEP 1

Sikel Hamilton yang baru C = (v1, v2, v4, v3, v5, v1) = (1,2,3,4,5,1) dan W = 11.

STEP 2

i= 1

STEP 3

j= i+2 = 3

STEP 4

Konstruksi C13 = (1,3,2,4,5,1) = (v1, v4, v2, v3, v5, v1); W13 = 3+2+3+2+4= 14. Karena W13 ≥ W, maka C tetap.

STEP 5

J = 3+1 = 4 ≤  5=n

STEP 4

Konstruksi C14 = (1,4,3,2,5,1) = (v1, v3, v4, v2, v5, v1); W14 = 1+1+2+2+4= 10. Karena W14= 10 < 10=W, maka diperoleh  C yang baru dengan C = C14 = (v1, v3, v4, v2, v5, v1) dan W = W14= 10. Ke step 1.

STEP 1

Sikel Hamilton yang baru C = (v1, v3, v4, v2, v5, v1) = (1,2,3,4,5,1) dan W = 10.

STEP 2

i= 1

STEP 3

j= i+2 = 3

STEP 4

Konstruksi C13 = (1,3,2,4,5,1) = (v1, v4, v3, v2, v5, v1); W13 = 3+1+3+2+4= 13. Karena W13 ≥ W, maka C tetap.

STEP 5

J = 3+1 = 4 ≤  5=n

STEP 4

Konstruksi C14 = (1,4,3,2,5,1) = (v1, v2, v4, v3, v5, v1); W14 = 2+2+1+2+4= 11. Karena W14 ≥ W, maka C tetap.

STEP 5

J = 4+1 = 5 ≤  n

STEP 4

Konstruksi C15 = (1,5,4,3,2,1) = (v1, v5, v2, v4, v3, v1); W15 = 4+2+2+1+1= 10. Karena W15 ≥ W, maka C tetap.

STEP 5

J = 5+1 = 6 >  n

Tulis I = 1+1=2. Karena i=2 ≤ n-2, ke Step 3

STEP 3

J= i + 2 = 2+2 = 4

STEP 4

Konstruksi C24 = (1,2,4,3,5,1) = (v1, v3, v2, v4, v5, v1); W24 = 1+3+2+2+4= 12. Karena W15 ≥ W, maka C tetap.

STEP 5

J = 4+1 = 5 ≤  n

STEP 4

Konstruksi C25 = (1,2,5,4,3,1) = (v1, v3, v5, v2, v4, v1); W25 = 1+2+2+2+3= 10. Karena W25 ≥ W, maka C tetap.

STEP 5

J = 5+1 = 6 >  n

Tulis I = 2+1=3. Karena i=3 ≤ n-2, ke Step 3

STEP 3

J= i + 2 = 3+2 = 5

STEP 4

Konstruksi C35 = (1,2,3,5,4,1) = (v1, v3, v4, v5, v2, v1); W35 = 1+1+2+2+2= 8. Karena W35= 8 < 10=W, maka diperoleh  C yang baru dengan C = C35 = (v1, v3, v4, v5, v2, v1) dan W = W35= 8. Ke step 1.

STEP 1

Sikel Hamilton yang baru C = (v1, v3, v4, v5, v2, v1) = (1,2,3,4,5,1) dan W = 8.

STEP 2

i= 1

STEP 3

j= i+2 = 3

STEP 4

Konstruksi C13 = (1,3,2,4,5,1) = (v1, v4, v3, v5, v2, v1); W13 = 3+1+2+2+2= 10. Karena W13 ≥ W, maka C tetap.

STEP 5

J = 3+1 = 4 ≤ 5= n

STEP 4

Konstruksi C14 = (1,4,3,2,5,1) = (v1, v5, v4, v3, v2, v1); W14 = 4+2+1+3+2= 12. Karena W14 ≥ W, maka C tetap.

STEP 5

J = 4+1 = 5 ≤  n

STEP 4

Konstruksi C15 = (1,5,4,3,2,1) = (v1, v2, v5, v4, v3, v1); W15 = 2+2+2+1+1= 8. Karena W15 ≥ W, maka C tetap.

STEP 5

J = 5+1 = 6 >  n

Tulis I = 1+1=2. Karena i=2 ≤ n-2, ke Step 3

STEP 3

J= i + 2 = 2+2 = 4

STEP 4

Konstruksi C24 = (1,2,4,3,5,1) = (v1, v3, v5, v4, v2, v1); W24 = 1+2+2+2+2= 9. Karena W24 ≥ W, maka C tetap.

STEP 5

J = 4+1 = 5 ≤  n

STEP 4

Konstruksi C25 = (1,2,5,4,3,1) = (v1, v3, v2, v5, v4, v1); W25 = 1+3+2+2+3= 11. Karena W25 ≥ W, maka C tetap.

STEP 5

J = 5+1 = 6 >  n

Tulis I = 2+1=3. Karena i=3 ≤ n-2, ke Step 3

STEP 3

J= i + 2 = 3+2 = 5

STEP 4

Konstruksi C35 = (1,2,3,5,4,1) = (v1, v3, v4, v2, v5, v1); W35 = 1+1+2+2+4= 10. Karena W35 ≥ W, maka C tetap.

STEP 5

J = 5+1 = 6 >  n

Tulis I = 3+1=3. Karena i=4 > n-2, Maka STOP.

Jadi Sikel Hamilton = (v1, v3, v4, v5, v2, v1) adalah sebuah sikel hamilton ‘mendekati’ optimal di graph G dengan bobot 8. Kenyataannya, = (v1, v3, v4, v5, v2, v1) adalah sikel hamilton optimal pada graph G.

About NICO MATEMATIKA

Welcome to my blog. My name is Nico. Admin of this blog. I am a student majoring in mathematics who dreams of becoming a professor of mathematics. I live in Kwadungan, Ngawi, East Java. Hopefully in all the posts I can make a good learning material to the intellectual life of the nation. After the read, leave a comment. I always accept criticism suggestion to build a better me again .. Thanks for visiting .. : mrgreen:

Posted on June 26, 2011, in teory graph and tagged , , , , , . Bookmark the permalink. 6 Comments.

  1. Otak saya nggak kuat.. Klo algoritma di pemrograman masih mudeng dikit.

    O ya, cara bikin huruf “v” yang rada keatas itu gimana?

  2. wes puyeng ga mudeng *lulusan sma geblek nih gw😦

  1. Pingback: daftar isi « matematika blog for education

LEAVE A COMMENT IN HERE. COMMENTING IN HERE IS ALWAYS AUTO APPROVE. PLEASE NO SPAM!!! BECAUSE I HATE SPAM... THANKS A LOT..... :mrgreen:

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: