MENCARI JARAK MINIMUM PADA GRAPH SEMI EULER

Perhatikan graph bobot G pada gambar di atas merepresentasikan suatu jaringan jalan di sekitar kantor pos tertentu. Misalkan titik v5 merepresentasikan kantor pos. Dalam hal ini kantor pos tidak mungkin menelusuri setiap jalan tepat satu kali berawal dan berakhir di kantor pos, karena graph G bukan graph Euler (karena titik v1 dan titik v10 berderajat ganjil). Ini berarti harus ada jalan-jalan yang harus ditelusuri lebih dari satu kali. Untuk menentukan jalan-jalan yang harus ditelusuri lebih dari satu kali agar total jarak yang ditempuh minimum, kita cari lintasan terpendek yang menghubungkan v1 dan titik v1. Dengan menggunakan algoritma Djikstra, diperoleh lintasan terpendek dari titik v1 ke titik v10 adalah P = (v1, v4, v5, v6, v7, v8, v10), seperti tampak pada gambar berikut.

Lintasan terpendek di G adalah dari v1 ke v 10 melewati v1, v4, v5, v6, v7, v8, v10.

Panjang jalan J adalah w(G) + w(P) = 50 + 9 = 59. Dengan demikian, strategi yang dapat dipilih oleh tukang pos agar semua jalan dilewati dan total jarak yang ditempuh minimum adalah mengikuti penelusuran jalan J.

Perhatikan bahwa setiap titik G’ berderajat genap, jadi G’ graph euler. Menggunakan algoritma fleury untuk mengkonstruksikan sirkit-euler yang berawal dan berakhir di titik V5 pagda graph G’; diperoleh sirkit-euler S=(V5,V3,V4,V1,V2,V3,,V1,V4,V9,V5,V4,V5,V6,V2,V7,V6,V8,V7,V10,V8,V9,V10,V8,V7,V6,V5). Ingat sirkit S ini tidak ada di graph G. Jika menelusuri suatu sisi-duplikat di G’ adalah menelusuri ‘sisi yang di duplikat’ di G, maka diperoleh jalan-tutup J=(V5,V3,V4,V1,V2,V3,V1,V4,V9,V5,V4,V5,V6,V2,V7,V6,V8,V7,V10,V8,V9,V10,V8,V7,V6,V5) pada graph G yang memuat sisi G dengan bobot minimum. Jalan tutup J dapat di lihat pada gambar di atas. Perhatikan dalam menelusuri jalan J pada graph G, setiap sisi G pada lintasan P ditelusuri tepat 2 kali dan setiap sisi G yang lain di telusuri tepat 1 kali. Misal, sisi V1V4 pada lintasan P dengan bobot 3, dalam menelusuri jalan J, ditelusuri 2 kali,yaitu:urutan ketiga dari titik V4 ke titik V1 dan urutan ke 7 dariV1 ke V4; sisi V1V4 di label dengan . Contoh yang lain, sisi V8V10 pada lintasan P dengan bobot 1, dalam menelusuru jalan J, ditelusuri 2 kali yaitu; urutan ke-19 dari titik V8 ke titik V10 dan urutan ke-22 dari titik V10 ke titik V8; sisi V8V10 dilabel dengan . Secara lengkap strategi menelusuri jalan J dapat di lihat pada :

Panjang jalan J adalah w (G) + w (P) = 50 + 9 = 59

 

RELATED POST ::

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 August 18, 2011, in teory graph and tagged , , , , . Bookmark the permalink. 4 Comments.

  1. ijin tanya,apa yg dimaksud dengan duplication of vertex?bisa dijelaskan?trims b4//acii_math08

  2. Matematika apa ini bro…?di perkuliahan ya…………?

  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: