Sponsor

Friday, 16 August 2013

Graph Berlabel, Lintasan Euler dan TSP

silahkan klik link ini :
http://adf.ly/bVqH6
untuk download file ms.word



GRAPH BERLABEL

            Graf G disebut graf berlabel jika ruas dan atau simpulnya dikaitkan dengan suatu besaran tertentu. Jika setiap ruas e dari G dikaitkan dengan suatu bilangan non negatif d(e), maka d(e) disebut bobot atau panjang dari ruas e.

Contoh Graph Berlabel
Contoh: simpul menyatakan kota, label pada ruas d(e) menyatakan jarak antar kota.

DERAJAT GRAF


            Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v. Karena setiap ruas dihitung dua kali ketika menentukan derajat suatu graf, maka :
Jumlah derajat semua simpul suatu graf (derajat) = dua kali banyaknya ruas graf (size graf).
            Suatu simpul disebut genap/ganjil tergantung apakah derajat simpul tersebut genap/ganjil. Kalau terdapat self-loop, maka self-loop dihitung 2 kali pada derajat simpul.

Istilah-istilah Graph
·         Derajat simpul, ditulis d(v), adalah banyaknya ruas yang menghubungi simpul tersebut.
·         Simpul ganjil adalah simpul yang berderajat ganjil. Simpul genap adalah simpul yang berderajat genap.
·         Jika terdapat self-loop maka self-loop dihitung 2 kali untuk derajat simpul.
·         Derajat graph adalah jumlah seluruh derajat simpul.
Derajat graph = d(v1)+d(V2)+…+d(vn)
·         Derajat graph juga sama dengan dua kali jumlah ruas(size).
Derajat graph = 2 x size;



Simpul E disebut simpul bergantung/akhir, yaitu simpul berderajat 1. Simpul F disebut simpul terpencil, yaitu simpul yang berderajat 0.
Contoh:
·         d(A) = 2, d(B) = 5, d(C) = 3, d(D) = 3, d(E) = 1, d(F) = 0
·         Derajat graph = 2+5+3+3+1+0 = 14
·         Size graph = 7       Derajat graph = 2 x 7 = 14

 

Graph berlabel ini dibagi menjadi dua kategori yaitu:
a)      Graph berlabel ajaib
Graph berlabel ajaib adalah graph yang memiliki weight (W) atau berat yang sama.
Contoh:
http://4.bp.blogspot.com/-fB3wvfQ-Ug0/UIUr8W17slI/AAAAAAAAATw/jycJFN6HHLE/s320/graph1.bmp
          W1 = 1 + 3 + 5 = 9
          W2 = 3 + 4 + 2 = 9
Bobot W1 dan W2 adalah sama, yaitu sama-sama 9. Maka graph ini disebut graph ajaib.
b)     Graph berlabel anti ajaib
http://2.bp.blogspot.com/--hV-4vVhSHc/UIUsKZZQqtI/AAAAAAAAAT4/r67u8ju0BHg/s320/graph2.bmpGraph anti ajaib adalah graph yang memiliki weigh (W) yang berbeda-beda, namun dengan selisih yang sama. Contohnya:                                         
W1 = 1 + 10 + 3 = 14
W2 = 3 + 8 + 5 = 16
W3 = 5 + 6 + 7 = 18
W4 = 7 + 4 + 9 = 20
W5 = 9 + 2 + 11 = 22
W6 = 11 + 12 + 1 = 24

W1, W2, W3, W4, W5, W6 memiliki selisih yang sama yaitu dua.
GRAF EULER

Lintasan dan Sirkuit Euler
·         Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.
·         Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali..
·         Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).
Contoh:
Description: http://3.bp.blogspot.com/-Crln-jkw9NE/Tnk6vVtWGdI/AAAAAAAAABI/lQuSx32pd4s/s320/Euler%2BGraf.jpg
Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1
Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3
Sirkuit Euler pada graf (c) : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1
Sirkuit Euler pada graf (d) : a, c, f, e, c, b, d, e, a, d, f, b, a
Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler
Atau: (a) dan (b) graf semi-Euler, (c) dan (d) graf Euler , (e) dan (f) bukan graf semi-Euler atau graf Euler
Teorema-teorema:
·         Graf tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali.
·         Graf tidak berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap. (Catatlah bahwa graf yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya).
·         Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat- masuk dan derajat-keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertamamemiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.
·         Lintasan Euler ialah lintasan yang melalui tiap sisi dalam graf tepat sekali .
·         Sirkuit Euler ialah sirkuit yang melalui tiap sisi dalam graf tepat satu kali.
·         Graf yang mempunyai sirkuit Euler disebut graf Euler, sedang graf yang mempunyai lintasan Euler disebut semi Euler.
Contoh:
a)      Apakah Ada Lintasan Euler ?
b)       Apakah ada sirkuit Euler ?

Jawab
a)      ADA lintasan euler dengan lintasan :
a,b,c,d,e,f,g,b,d,f,a,g
b)      Tidak ADA sirkuit Euler.

a)      Apakah ada lintasan Euler ?
b)      Apakah ada Sirkuit Euler ?

Jawab
a)      ADA lintasan Euler dengan lintasan :
a,b,c,d,e,c,h,b,f,h,e,f,g,a
b)      Ada sirkuit euler karena berawal dari simpul a dan berakhir di simpul a









Teorema Untuk Lintasan dan sirkuit euler


·         Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan mempunyai 2 buah simpul berderajat ganjil atau tidak ada simpul berderajad ganjil samasekali.
·         Graf tak berarah G adalah graf Euler jika hanya jika setiap simpul berderajad genap.
·         Graf berarah G memiliki sirkuit Euler jika hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama kecuali 2 simpul, yang pertama memiliki derajad keluar satu lebih besar dari derajad masuk, dan yang kedua memiliki derajad masuk satu lebih besar dari derajad keluar.










TRAVELING SALESMAN PROBLEM

            Traveling Salesman Problem (TSP) adalah suatu permasalahan dimana seorang sales harus melalui semua kota yang ditunjuk dengan jarak yang paling pendek dan setiap kota hanya boleh dilalui satu kali.
            Penyelesaian dalam TSP adalah jalur yang dilalui oleh salesman sesuai dengan batasan di atas. Penyelesaian terbaik adalah jalur dengan jarak terpendek.
            TSP adalah salah satu contoh permasalahan kombinatorial dengan kemungkinan penyelesaian yang sangat banyak.
            Bila dipandang dari sudut komputasinya, algoritma ini dapat diselesaikan dengan cepat walaupun dengan menggunakan algoritma brute force sekalipun, jika kota-kota yang akan dikunjunginya sedikit. Namun, jika kota-kota yang akan dikunjungi banyak, maka algoritma seperti Brute Force tidaklah menjadi pilihan lagi. Sebab, Algoritma Brute Force sendiri memiliki kompleksitas O(n!).
            Salah satu cara untuk menyelesaikan TSP yaitu dengan menggunakan Algoritma Brute Force. Hal yang dilakukan ialah dengan cara mengenumerasi seluruh kemungkinan rute yang akan ditempuh. Contoh:
TSP dengan 3 kota

·         Oval: 2TSP dengan 3 kota (1,2,3) hanya mempunyai satu kemungkinan seperti gambar di bawah ini.


 




·         TSP dengan 3 kota tidak perlu diselesaikan menggunakan komputer

TSP dengan 4 kota

·         Oval: 4Oval: 3Oval: 1Oval: 2Oval: 4Oval: 3Oval: 1Oval: 2Oval: 3Oval: 2TSP dengan 4 kota (1,2,3,4) hanya mempunyai 3 kemungkinan seperti gambar di bawah ini.























 




·         TSP dengan 4 kota tidak perlu diselesaikan menggunakan komputer
TSP dengan 5 kota
·         Oval: 4Oval: 3Oval: 1Oval: 2Oval: 3Oval: 4Oval: 1Oval: 2TSP dengan 4 kota (1,2,3,4,5) hanya mempunyai 12 kemungkinan seperti gambar di bawah ini.

























 




                                                                                                                        . . . . . . .
·         TSP dengan 5 kota mulai perlu diselesaikan menggunakan komputer. Teknik yang dipakai bisa berupa mencoba semua kemungkinan dan dibandingkan jaraknya untuk memperoleh jarak paling pendek

TSP dengan n kota
·         TSP dengan n kota (1,2,3,4,5,…,n) mempunyai(n-1)!/2 kemungkinan.
·         TSP dengan 15 kota mempunyai 14!/2 atau4.3589.1010 kemungkinan. Metode pencarian satu-satu memerlukan waktu yang sangat lama.
·         TSP dengan 20 kota mempunyai 19!/2 atau 6.08 1016 kemungkinan, suatu jumlah yang sangat besar. Dengan menganggap bahwa komputer mampu menyelesaikan 1 Giga (109) proses per-detik maka untuk mencari semua solusi diperlukan 6.08 107 detik atau 1.69.104 jam atau 704 hari. Waktu yang sangat lama.
·         Bagaimana bila TSP dengan 30,40,50 atau 100 kota?

Penyelesaian TSP Dengan Monte Carlo
·         Penyelesaian TSP adalah jalur yang melewati semua kota dan setiap kota hanya dilalui satu kali, hal ini dapat dinyatakan sebagai kombinasi urutan nomor kota, misalkan untuk TSP 6 kota: 1-2-3-4-5-6
·         Penyelesaian dicari secara acak misalkan: 3-2-5-1-6-4, kemudian dihitung total jarak setiap jalur yang dipilih.
·         Untuk mencari penyelesaian yang baru, dilakukan proses update dengan mengubah urutan dari beberapa titik saja (tidak perlu semua titik).
·         Proses pencarian jalur dilakukan secara berulang-ulang hingga diperoleh jalur dengan jarak terpendek.

Catatan:
Beberapa metode telah dikembangkan untuk memecahkan persoalan ini namun belum ditemukan algoritma penyelesaian yang optimal.

Contoh Masalah:
tsp.JPG
Jumlah node (n) ada 5 buah, Jumlah kemungkinan jalur = (n-1)! / 2 Jumlah jalur 4! /2 = 12 buah. Dimisalkan titik asal A dan titik akhir adalah A. Maka jumlah jalur dan panjang lintasannya adalah :

1.      Lintasan 1 = (a b c d e a) atau (a e d c b a) memiliki panjang lintasan = 7 + 7 + 4 + 6 + 9 = 33
2.      Lintasan 2 = (a b c e d a) atau (a d e c b a) memiliki panjang lintasan = 7 + 7 + 3 + 6 + 9 = 32
3.      Lintasan 3 = (a b d c e a) atau (a e c d b a) memiliki panjang lintasan = 7 + 2 + 4 + 3 + 9 = 25
4.      Lintasan 4 = (a b d e c a) atau (a c e d b a) memiliki panjang lintasan = 7 + 2 + 6 + 3 + 5 = 23
5.      Lintasan 5 = (a b e c d a) atau (a d c e b a) memiliki panjang lintasan = 7 + 8 + 3 + 4 + 9 = 31
6.      Lintasan 6 = (a b e d c a) atau (a c d e b a) memiliki panjang lintasan = 7 + 8 + 6 + 4 + 5 = 30
7.      Lintasan 7 = (a c b d e a) atau (a e d b c a) memiliki panjang lintasan = 5 + 7 + 2 + 6 + 9 = 29
8.      Lintasan 8 = (a c b e d a) atau (a d e b c a) memiliki panjang lintasan = 5 + 7 + 8 + 6 + 9 = 35
9.      Lintasan 9 = (a c d b e a) atau (a e b d c a) memiliki panjang lintasan = 5 + 4 + 2 + 8 + 9 = 28
10.  Lintasan 10 = (a d b c e a) atau (a e c b d a) memiliki panjang lintasan = 9 + 2 + 7 + 3 + 9 = 30
11.  Lintasan 11 = (a d b e c a) atau (a c e b d a) memiliki panjang lintasan = 9 + 2 + 8 + 3 + 5 = 27
12.  Lintasan 12 = (a d c b e a) atau (a e b c d a) memiliki panjang lintasan = 9 + 4 + 7 + 8 + 9 = 37

Lintasan yang jaraknya paling pendek adalah : 4 yaitu 23

Kesimpulan:

           Dari hasil ke-12 enumerasi di atas didapatkan panjang jalur lintasan paling minimum yaitu 23.
           Jumlah enumerasi dari algoritma ini ialah (n - 1)! yang akan memerlukan waktu yang sangat lama untuk mendapatkan panjang lintasan paling minimum jika nilai n bernilai sangat besar.





Sumber:
http://bambangirawan.blog.esaunggul.ac.id/files/2012/06/pertemuan-9-10baru1.pdf






 


No comments: