silahkan klik link ini :
http://adf.ly/bVqH6
untuk download file ms.word
Graph anti ajaib adalah graph
yang memiliki weigh (W) yang berbeda-beda, namun dengan selisih yang sama.
Contohnya:
Jawab
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:
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
Graph 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:
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:
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
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
Jawab
a)
ADA
lintasan Euler dengan lintasan :
a,b,c,d,e,c,h,b,f,h,e,f,g,a
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
·
TSP dengan 3
kota (1,2,3) hanya mempunyai satu kemungkinan seperti gambar di bawah ini.
TSP 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
·
TSP dengan 4
kota (1,2,3,4) hanya mempunyai 3 kemungkinan seperti gambar di bawah ini.
TSP 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
·
TSP dengan 4
kota (1,2,3,4,5) hanya mempunyai 12 kemungkinan seperti gambar di bawah ini.
TSP 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:
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:
Post a Comment