Matematika Diskrit
Makalah “Menentuan Jarak Terpendek, dan Tapak Euler dalam graf”
Nama
: Kelvin Sebastian
NIM
: 1313003
Departemen Teknologi Informasi INSTITUT TEKNOLOGI HARAPAN BANGSA 2014
1
ABSTRAK
Makalah ini membahas tentang salah satu aspek penting dalam sejarah perkembangan ilmu matematika yaitu studi dan aplikasi Konigsberg Bridge Problem (Teka-Teki Jembatan Konigsberg) yang berawal muncul dari penduduk sebuah kota bernama yang dahulu bernama Konigsberg di Jerman. Adalah Leonard Euler, seorang pakar matematika yang mencoba mempelajari teka-teki tersebut dari sudut pandang matematis dan akhirnya mengemukakan sebuah teorema yang kini banyak digunakan dalam berbagai permasalahan, yaitu teorema graf. Graf yang memiliki komponen dasar berupa simpul dan sisi, yang kemudian dapat membentuk graf terbuka dan graf tertutup dengan sejumlah lintasan dan sirkuit, telah mengahpus tanda tanya besar dalam penyelesaian Teka-Teki Jembatan Konigsberg dan berbagai masalah yang serupa dengannya. Makalah ini membahas tentang persoalan lintasan terpendek suatu graf dengan algoritma dijkstra. Lintasan terpendek merupakan bagian dari teori graf. Jika diberikan sebuah graf berbobot, masalah jarak terpendek adalah bagaimana kita mencari sebuah jalur pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut. Persoalan ini adalah persoalan optimasi, dimana kita akan mencari solusi penyelesaian yang paling efektif dari masalah penentuan lintasan terpendek pada suatu graf. Saat ini banyak sekali algortima-algoritma yang dapat digunakan untuk menyelesaikan persoalan penentuan lintasan terpendek (shortest path problem) dari suatu graf. Solusi yang didapat dari penelusuran algoritma tersebut dapat diberi nama Pathing Algorithm. Ada dua algortima yang cukup terkenal yang bisa digunakaan untuk menyelesaikan persoalan lintasan terpendek, yaitu Algoritma Dijkstra dan Algoritma Bellman-Ford. Tetapi pada kesempatan ini kita hanya akan membahas tentang algoritma dijkstra. Algoritma Dijkstra merupakan salah satu algoritma yang digunakan untuk memecahkan permasalahan lintasan terpendek yang terdapat pada suatu graf . Algoritma ini digunakan pada graf berbobot dengan syarat bobot dari masing-masing sisi haruslah bernilai positif (>=0).
2
KATA PENGANTAR
Segala puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa, karena anugerah-Nya penulis berhasil menyelesaikan makalah ini di dalam mata pelajaran Matematika Diskrit. Karya tulis ini berjudul “Menentuan Jarak Jerpendek, Jembatan Konigsberg dan Tapak Euler dalam graf”.
Penulis menyadari bahwa karya tulis ini masih kurang sempurna, baik dari segi materi maupun sistematika pembahasannya. Hal ini dikarenakan terbatasnya waktu, pengetahuan, pengalaman dan kemampuan yang penulis miliki.
Selama proses penelitian dan pembuatan makalah ini, penulis telah banyak menerima bantuan dari berbagai pihak, baik berupa bimbingan, saran maupun dorongan. Pada kesempatan ini penulis ingin menyampaikan rasa berterimakasih secara khusus kepada :
1. I Putu Agus Eka Pratama, S.T, M.T selaku pembimbing dan dosen dalam mata kuliah Matematika Diskrit. 2. Teman-teman yang telah membantu dalam penyusunan makalah ini.
Harapan penulis, semoga makalah ini bermanfaat bagi pembaca dalam pengetahuan graf. Penulis juga meminta maaf apabila ada kesalahan-kesalahan dalam pembuatan karya tulis ini. Penulis bersedia menerima kritik, dan saran, karena bagi penulis, kritik dan saran sangat penting dalam perbaikan-perbaikan di masa depan.
Bandung, 23 November 2014 Salam Hangat,
Penulis
3
DAFTAR ISI Abstraksi ..........………………………………………………………....
2
Kata Pengantar ...………………………………………………………..
3
Daftar Isi ………………………………………………………………..
4
BAB I …………………………………………………………………..
5
1. Pendahuluan 1.1 Latar Belakang ……………………………………………..
5
1.2 Rumusan Masalah ………………………………………….
6
1.3 Tujuan Penelitian …………………………………………...
6
1.4 Manfaat Penelitian …………………………………..……..
6
1.5 Sistematika Penulisan ……………………………………...
7
BAB II …………………………………………………………………..
8
2.1 Graf 2.1.1 Pengertian Graf ……………………….….…………………
8
2.1.2 Sejarah Graf …………………………….....………………..
8
2.1.3 Definisi Graf …………………………….……………….....
9
2.2 Lintasan dan Sirkuit Euler …….…………………………………
11
2.3 Lintasan Terpendek …..…………………………………………..
12
BAB III …………………………………………………………………
14
3.1 Jenis Peneletian ………………..………………………………...
14
3.2 Teknik Analisis Data 3.2.1 Sirkuit Euler ……………………………………………….
13
3.2.2 Lintasan Terpendek …………………………………...…..
16
3.2.3 Persoalan Tukang Pos Cina ………………………...……..
18
3.2.4 Persoalan Perjalanan Pedagang ……………………………
19
BAB IV ………………………………………………………………....
21
Lintasan Terpendek …..……………………………………………..
21
BAB V ………………………………………………………………….
23
5. Kesimpulan 5.1 Lintasan Terpendek …………………………………..……
23
5.1 Sirkuit Euler …………………………………………..…...
24
6 Saran ...............................................................................................
25
Daftar Pustaka ………………………………………………………….
26 4
BAB I PENDAHULUAN
1.1 Latar Belakang Teori graf lahir pada tahun 1736 melalui tulisan Euler yang berisi tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa. Kurang lebih seratus tahun setelah lahirnya tulisan Euler tersebut tidak ada perkembangan yang berarti dengan teori graf. Tahun 1847, G.R. Kirchoff (1824-1887) berhasil mengembangkan teori pohon (Theory of trees) yang digunakan dalam persoalan jaringan listrik. Sepuluh tahun kemudian, A.Cayley (1821-1895) juga menggunakan konsep pohon untuk menjelaskan permasalahan kimia yaitu hidrokarbon. Pada masa Kirchoff dan Cayley juga telah lahir dua hal penting dalam graf. Salah satunya berkenaan dengan konjektur empat warna, yang menyatakan bahwa untuk mewarnai sebuah atlas cukup dengan menggunakan empat warna sedemikian sehingga tiap negara yang berbatasan akan memiliki warna yang berbeda. Para ahli teori graf berkeyakinan bahwa orang yang pertama kali mengemukakan masalah empat-warna adalah A.F.Mobius (1790-1868) dalam salah satu kuliahnya di tahun 1840. Sepuluh tahun kemudian, A.Demorgan (1806-1871) kembali membahas masalah ini bersama ahli-ahli matematika lainnya di kota London. Dengan demikian tulisan Demorgan dianggap sebagai referensi pertama berkenaan dengan masalah empat-warna. Masalah empat-warna ini menjadi sangat terkenal setelah Cayle mempublikasikannya tahun 1879 dalam Proceeding of the Royal Geographic Society volume pertama. Hal ini yang penting untuk membicarakan sehubungan dengan perkembangan teori graf adalah apa yang dikemukakan oleh Sir W.R. Hamilton (1805-1865). Pada tahun 1895 dia berhasil menemukan suatu permainan yang kemudian dijualnya ke sebuah pabrik mainan di Dublin. Permainan tersebut dari kayu berbentuk
5
dodecahedron beraturan yakni berupa sebuah polyhedron dengan 12 muka dan 20 pojok. Tiap muka berbentuk sebuah pentagon beraturan dan tiap pojoknya dibentuk oleh tiga sisi berbeda. Tiap pojok dari dodecahedron tersebut dipasangkan dengan sebuah kota terkenal seperti London, New York, Paris, dll. Masalah dalam permaianan ini adalah kita diminta untuk mencari suatu rute melalui sisi-sisi dari dodecahedron sehingga tiap kota dari 20 kota yang ada dapat dilalui tepat satu kali. Walaupun saat ini masalah tersebut dapat dikategorikan mudah, akan tetapi pada saat itu tidak ada seorang pun yang bisa menemukan syarat perlu dan cukup dari eksistensi rute yang dicari. Kurang lebih setengah abad setelah Hamilton, aktivitas dalam bidang teori graf dapat dikatakan relatif kecil. Pada tahun 1920-an kegiatan tersebut muncul kembali yang dipelopori oleh D.Konig. Konig berupaya mengumpulkan hasil-hasil pemikiran para ahli matematika tentang teori graf termasuk hasil pemikirannya sendiri, kemudian dikemasnya dalam bentuk buku yang di terbitkan pada tahun 1936. Buku tersebut dianggap sebagai buku pertama tentang teori graf. 1.2 Rumusan Masalah Permasalahan yang akan dibahas dalam tugas akhir ini adalah : 1. Bagaimana mencari jarak terpendek pada sebuah jalur ? 2. Bagaimana menentukan Tapak Euler pada sebuah graf ? 1.3 Tujuan Penelitian Tujuan yang ingin dicapai : 1. Mengetahui jarak terpendek pada sebuah jalur. 2. Menentukan Tapak Euler pada suatu graf. 1.4 Manfaat Penelitian Manfaat yang diharapkan dari hasil penelitian ini adalah bisa mengetahui jarak
terpendek / menentukan rute terpendek dari suatu tempat ke tempat yang lain, menghemat biaya (ongkos) perjalanan dan menghemat
waktu dalam sebuah
perjalanan dalam kehidupan sehari-hari. Menggunakan Tapak Euler biasanya untuk
6
mengetahui apakah kita bisa berjalan dari satu titik ke titik semula di mana kita mulai, dan bisa mengetahui / menemukan rute yang melintasi setiap rute satu kali saja sama dengan menemukan tapak Euler.. 1.5 Sistematika Penulisan Agar penulisan karya tulis ini lebih terarah, mudah mengerti, dan dipahami, maka digunakan sistematika pembahasan yang terdiri dari empat bab. Masing – masing bab dibagi ke dalam beberapa subbab dengan rumusan sebagai berikut : BAB I. PENDAHULUAN Dalam bab ini dijelaskan latar belakang, rumusan masalah, tujuan penelitian, batasan masalah, manfaat penelitian, hipotesis dan sistematika penulisan.
BAB II . LANDASAN TEORI Bagian ini terdiri atas konsep- konsep (teori - teori) yang mendukung bagian pembahasan, konsep – konsep tersebut antara lain : membahas tentang pengertian graf, jarak terpendek, Tapak Euler, dan Jembatan Konigsberg.
BAB III . METODE PENELITIAN Pada bagian ini terdiri atas jenis penelitian dan menganalisis data yang diperoleh dan merupakan sebuah jawaban atas pernyataan masalah.
BAB IV . PEMBAHASAN Pembahasan berisi tentang bagaimana menentukan jarak terpendek pada sebuah jalur, menentukan Tapak Euler pada suatu graf, mencari solusi Jembatan Konigsberg. BAB V . PENUTUP Pada bab ini akan dibahas tentang kesimpulan akhir penelitian dan beberapa saran.
7
BAB II LANDASAN TEORI
2. GRAF 2.1 Teori Graf Teori Graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek dinyatakan sebagai noktah, bulatan, atau titik. Sedangkan hubungan antara objek dinyatakan dengan garis. Graf sederhana (simple graf) adalah Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. Graf tak-sederhana (unsimplegraf/multigraf) adalah Graf yang mengandung ruas ganda atau gelung dinamakan graf tak-sederhana (unsimple graf atau multigrapf).
2.2 Sejarah Graf Menurut cacatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali menggunakan graf (tahun 1736). Di kota Konigsberg (sebelah timur negara bagian Prussia, Jerman), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai. Ada tujuh buah jembatan yang menghubungkan daratan yang dibelah oleh sungai tersebut. Masalah jembatan Konigsberg adalah : apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula? Sebagian penduduk kota sepakat bahwa memang tidak mungkin memalui setiap jembatan itu hanya sekali dan kembali lagi ke tempat asal mula keberangkatan, tetapi dengan cara coba-coba. Tahun 1736, seorang matematikawan Swiss, L.Euler, adalah orang pertama yang berhasil menemukan jawaban masalash itu dengan pembuktian yang sederhana. Ia memodelkan masalah ini ke dalam graf. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakan sebagai titik (noktah) yang disebut simpul (vertex) dan jembatan dinyatakan sebagai garis yang disebut sisi
8
(edge). Setiap titik diberi label huruf A,B,C,dan D. Graf yang dibuat oleh Euler diperlihatkan pada gambar berikut.
Gambar : Jembatan Konigsberg
Jawaban yang di kemukakan Euler adalah : orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya genap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh, simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin di lakukan perjalanan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut. Kelak kita akan membahas lebih mendalam mengenai derajat dan sirkuit pada pemabahasan selanjutnya.
2.3 Definisi Graf Graf G didefinisikan sebagai pasangan himpunan (V,E), yang dalam hal ini: V = himpunan berhingga dan tidak kosong dari simpul-simpul (vertices atau node) = {
v1 , v2 ,..., vn } dan E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. = { e1 , e2 ,..., en } atau dapat ditulis singkat notasi G = (V, E )Simpul pada graf dapat dinomori dengan huruf, seperti v, w,…,dengan bilangan
asli 1, 2, 3,…, atau
gabungan keduanya. Sedangkan sisi yang menghubungkan simpul v i dengan simpul
v j dinyatakan dengan pasangan ( vi , v j ) atau dengan lambang e1 , e 2 ,... . Dengan kata lain, jika e adalah sisi yang menghubungkan simpul v i dengan simpul v j , maka e dapat 9
ditulis sebagai : e = ( vi , v j ) secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dwimatra yang dihbungkan dengan sekumpulan garis (sisi). Berikut adalah contoh gambar graf : 1
1 ce 2
3
e2
2
e3
e4 3
e6
e5 4
e7 4
(a)
(b)
1 e4
e1 2
3
e3
e2
e8
e6 e5
e7 4
(c) Gambar : Graf sederhana (a), Graf Ganda (b), Graf semu (c)
Pada Gambar 3, G1 adalah graf dengan V = { 1, 2, 3, 4 } E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
G2 adalah graf dengan V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } = { e1, e2, e3, e4, e5, e6, e7} G adalah graf dengan 3
V = { 1, 2, 3, 4 }
10
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4),(3,3) } = { e1, e2, e3, e4, e5, e6, e7, e8} 2. Lintasan dan Sirkuit Euler Lintasan yang melalui masing-masing sisi dalam graf tepat satu kali disebut lintasan Euler. Jika lintasan tersebut adalah lintasan tertutup, maka lintasan tertutup tersebut disebut sirkuit Euler. Contoh seperti pada gambar berikut: Lintasan Euler : 3, 1, 2, 3, 4, 1
1
2
Tidak ada sirkuit Euler
Gambar : Lintasan Euler 3
4
Untuk membuat graf G yang mempunyai lintasan Euler harus dipenuhi kondisi : 1. Graf terhubung. 2. Graf tidak mempunyai simpul derajat ganjil sama sekali atau mempunyai 2 buah simpul berderajat ganjil.
Untuk membuat graf G yang mempunyai sirkuit Euler harus dipenuhi kondisi : 1. Graf terhubung. 2. Semua simpul berderajat genap. Graf berarah G mempunyai lintasan Euler jika G terhubung dan setiap simpul mempunyai derajat masuk dan derajat keluar sama kecuali 2 simpul. Yang pertama memiliki derajat keluar satu lebih besar dari derajat masuk dan yang kedua memiliki derajat masuk satu lebih besar dari derajat keluar. Graf berarah G mempunyai sirkuit Euler jika hanya jika G terhubung dan setiap simpul mempunyai derajat masuk dan derajat keluar sama.
11
3. Lintasan Terpendek (Shortest Path) Persoalan mencari lintasan terpendek di dalam graf merupakan persoalan optimasi yang klasik. Graf yang diacu adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota / tempat, waktu pengiriman pesan, ongkos pembangunan dan sebagainya. Kata “terpendek” pada persoalan lintasan terpendek berarti minimasi dari bobot pada suatu lintasan di dalam graf. Contoh terapan pencarian lintasan terpendek. Misalkan simpul pada graf dapat merupakan kota dan sisi menyatakan jalan yang menghubungkan dua buah kota. Bobot sisi graf dapat menyatakan jarak antara dua buah kota atau rata-rata waktu tempuh antara dua buah kota. Apabila terdapat lebih dari satu lintasan dari kota A ke kota B, maka persoalan lintasan terpendek di sini adalah menentukan jarak terpendek atau waktu tersingkat dari kota A ke kota B. Terdapat beberapa jenis persoalan lintasan terpendek, antara lain : a. Lintasan terpendek antara dua buah simpul tertentu. b. Lintasan terpendek antara semua pasangan simpul. c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain. d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu. Gambar 5 menyatakan kondisi tetang 6 buah kota dengan jarak lintasan yang menghubungi kota – kota tersebut.
45 1
50
2
10
5
40 20
15
10
3
15
20
4
35 30
3
6
Gambar : Lintasan Terpendek
12
1 0 ∞ 20 ∞ ∞ ∞
1 2 3 4 5 6
2 45 0 ∞ 20 ∞ ∞
3 10 15 0 ∞ ∞ ∞
4 40 ∞ 15 0 30 3
5 45 10 ∞ 35 0 ∞
6 ∞ ∞ ∞ ∞ ∞ 0
Tabel 1 Ilustrasi matriks mengenai lintasan terpendek
Sampai saat ini, sudah banyak algoritma untuk mencari lintasan terpendek yang pernah ditulis orang. Algoritma lintasan terpendek yang paling terkenal adalah algoritma Dijkstra (sesuai nama penemunya). Aslinya, algoritma Dijkstra diterapkan untuk mencari lintasan terpendek pada graf berarah. Misalkan sebuah graf berbobot dengan n buah simpul dinyatakan dengan matriks ketetanggaan
M = mij , yang dalam hal ini, mij = bobot sisi (i, j)
(pada graf tak berarah
mij = m ji ). mii = 0
mij = , jika tidak ada sisi dari simpul i ke simpul j Selain matriks M, kita menggunakan larik S = [ s i ] yang dalam hal ini, s i = 1, jika simpul i termasuk ke dalam lintasan terpendek s i = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek
dan larik / tabel D = [ d i ] yang dalam hal ini d i = panjang lintasan dari simpul awal s ke simpul j
Algoritma : urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis.
13
BAB III METODOLOGI PENELITIAN
3.1 Jenis Penelitian 3.1.1 Penelitian Kualitatif Penelitian kualitatif merupakan penelitian yang bersifat ilmiah dan juga sistematis sebagaimana penelitian kuantitatif sekalipun dalam pemilihan sample tidak seketat dan serumit penelitian kuantitatif. Dalam memilih sample penelitian kualitatif menggunakan teknik non probabilitas, yaitu suatu teknik pengambilan sample yang tidak didasarkan pada rumusan statistik tetapi lebih pada pertimbangan subyektif peneliti dengan didasarkan pada jangkauan dan kedalaman masalah yang ditelitinya. Lebih lanjut pada penelitian kualitatif tidak ditujukan untuk menarik kesimpulan suatu populasi melainkan untuk mempelajari karakteristik yang diteliti, baik itu orang ataupun kelompok sehingga keberlakukan hasil penelitian tersebut hanya untuk orang atau kelompok yang sedang diteliti tersebut.
3.2
Teknik Analisis Data 3.2.1
Sirkuit Euler
Pertama, Euler menunjukkan bahwa pilihan rute di dalam setiap daratan tidak relevan. Satu-satunya fitur penting dari rute adalah urutan jembatan menyeberang. Hal ini memungkinkan dia untuk merumuskan masalah dalam hal abstrak (meletakkan dasar-dasar teori graph ), menghilangkan semua fitur kecuali daftar massa tanah dan jembatan yang menghubungkan mereka. Dalam istilah modern, masing-masing satu menggantikan massa tanah dengan sebuah "abstrak titik "atau node, dan masingmasing jembatan dengan koneksi abstrak, sebuah"tepi ", yang hanya berfungsi untuk merekam yang sepasang simpul (massa tanah) yang dihubungkan dengan jembatan itu. Struktur matematika yang dihasilkan disebut graph.
Karena hanya informasi koneksi yang relevan, bentuk representasi bergambar grafik mungkin terdistorsi dengan cara apapun, tanpa mengubah grafik itu sendiri.
14
Hanya keberadaan (atau kekurangan) dari tepi antara setiap pasangan node adalah signifikan. Sebagai contoh, tidak masalah apakah tepi digambar lurus atau melengkung, atau apakah satu node adalah ke kiri atau kanan lain. Selanjutnya, Euler mengamati bahwa (kecuali pada titik akhir dari berjalan), setiap kali salah satu titik masuk dengan jembatan, satu daun titik dengan jembatan. Dengan kata lain, selama yang berjalan pada grafik, jumlah kali memasuki simpul nonterminal sama dengan berapa kali satu daun itu. Sekarang, jika setiap jembatan dilalui tepat satu kali, itu berarti bahwa, untuk setiap massa tanah (kecuali mungkin untuk yang dipilih untuk mulai dan selesai), jumlah jembatan menyentuh daratan bahkan (setengah dari mereka, pada khususnya traversal, akan dilalui "menuju" daratan tersebut; setengah lainnya, "jauh" dari itu). Namun, keempat massa tanah dalam masalah asli tersentuh oleh ganjil jembatan (satu disentuh oleh 5 jembatan, dan masing-masing tiga lainnya disentuh oleh 3). Karena, paling tidak, dua massa tanah dapat berfungsi sebagai titik akhir dari jalan putatif, proposisi berjalan kaki melintasi jembatan setiap kali mengarah ke kontradiksi. Dalam bahasa modern, Euler menunjukkan bahwa kemungkinan berjalan melalui grafik, melintasi setiap sisi tepat satu kali, tergantung pada derajat dari simpul-simpul. Derajat dari sebuah node adalah jumlah edge menyentuhnya. argumen Euler menunjukkan bahwa kondisi yang diperlukan untuk berjalan dari bentuk yang diinginkan adalah bahwa grafik dihubungkan dan memiliki tepat nol atau dua simpul berderajat ganjil. Kondisi ini ternyata juga cukup-hasil dinyatakan oleh Euler dan kemudian dibuktikan oleh Carl Hierholzer. Seperti jalan-jalan sekarang disebut jalur Euler atau jalan Euler untuk menghormatinya. Selanjutnya, jika ada node derajat ganjil, maka setiap path Euler akan dimulai pada salah satu dari mereka dan berakhir pada yang lain. Karena grafik yang sesuai dengan Königsberg historis memiliki empat node derajat aneh, ia tidak dapat memiliki jalur Euler.
Untuk membuat graf G yang mempunyai lintasan Euler harus dipenuhi kondisi : 1. Graf terhubung. 2. Graf tidak mempunyai simpul derajat ganjil sama sekali atau mempunyai 2 buah simpul berderajat ganjil.
15
Gambar : (Lintasan Euler)
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.
Untuk membuat graf G yang mempunyai sirkuit Euler harus dipenuhi kondisi : 1. Graf terhubung. 2. Semua simpul berderajat genap.
Gambar : (Sirkuir 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.
3.2.2
Lintasan Terpendek (Shortest Path)
Persoalan mencari lintasan terpendek di dalam graf merupakan persoalan optimasi yang klasik. Graf yang diacu adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan
16
jarak antar kota / tempat, waktu pengiriman pesan, ongkos pembangunan dan sebagainya. Kata “terpendek” pada persoalan lintasan terpendek berarti minimasi dari bobot pada suatu lintasan di dalam graf.
Graf berbobot (weighted graph),
Lintasan terpendek: lintasan yang memiliki total bobot minimum.
Contoh aplikasi: 1. Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota 2. Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer.
Terdapat beberapa jenis persoalan lintasan terpendek, antara lain: a.
Lintasan terpendek antara dua buah simpul tertentu.
b.
Lintasan terpendek antara semua pasangan simpul.
c.
Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
d.
Lintasan terpendek abtara dua buah simpul yang melalui beberapa simpul tertentu.
Uraian persoalan Diberikan graf berbobot G = (V, E) dan sebuah simpul a. Tentukan lintasan terpendek dari a ke setiap simpul lainnya di G. Asumsi yang kita buat adalah bahwa semua sisi berbobot positif. 45 1
50
2
10
5
40 20
15
10
3
15
20
4
35 30
3
6
Gambar : Lintasan
17
Simpul Asal 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6
Simpul Lintasan Terpendek Tujuan 3 1→3 4 1→3→4 2 1→3→4→2 5 1→5 6 tidak ada 5 2→5 1 2→3→1 3 2→3 4 2→3→4 6 tidak ada 1 3→1 2 3→4→2 4 3→4 5 3→4→5 6 tidak ada 1 4→2→3→1 2 4→2 3 4→2→3 5 4→5 6 tidak ada 1 5 → 4 → 2 → 3 →1 2 5→4→2 3 5→4→2→3 4 5→4 6 tidak ada 1 6 → 4 → 2 → 3 →1 2 6→4→2 3 6→4→2→3 4 6→4 5 6→4→2→5 Tabel 2 Ilustrasi Lintasan Terpendek
Jarak 10 25 45 45 10 35 15 30 20 35 15 50 55 20 35 35 85 50 65 30 53 23 38 3 33
3.2.3 Persoalan Tukang Pos Cina (Chinese Postman Problem) Dikemukakan oleh Mei Gan (berasal dari Cina) pada tahun 1962. Masalahnya adalah sebagai berikut: seorang tukang pos akan mengantar surat ke alamat-alamat sepanjang jalan di suatu daerah. Bagaimana ia merencanakan rute perjalanannya supaya ia melewati setiap jalan tepat sekali dan kembali lagi ke tempat awal keberangkatan.
18
B 2
8 8
1
4
3
A
C
4
D 2
6 F
5
E
Gambar : Persoalan Tukang Pos
=> menentukan sirkuit Euler di dalam graf. Proses yang dilalui oleh tukang pos : A→ B → C → D → E → F → C → E → B → F → A Lintasan yang dilalui tukang pos: A, B, C, D, E, F, C, E, B, F, A. 2 + 8 + 1 + 2 + 5 + 4 + 4 + 8 + 3 + 6 = 43 3.2.4 Persoalan Perjalanan Pedagang (Travelling Salesperson Problem - TSP) Diberikan sejumlah kota dan jarak antar kota. Tentukan sirkuit terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. => menentukan sirkuit Hamilton yang memiliki bobot minimum. Aplikasi TSP: 1. Pak Pos mengambil surat di kotak pos yang tersebar pada n buah lokasi di berbagai sudut kota. 2. Lengan robot mengencangkan n buah mur pada beberapa buah peralatan mesin dalam sebuah jalur perakitan. 3. Produksi n komoditi berbeda dalam sebuah siklus. Jumlah sirkuit Hamilton di dalam graf lengkap dengan n simpul: (n - 1)!/2. n = titik dalam sebuah graf
19
a
12
b
5
10
9 8
d
15
c
Gambar : Sirkuit Terpendek / Halminton
Graf di atas memiliki (4 – 1)!/2 = 3 sirkuit Hamilton, yaitu: I1 = (a, b, c, d, a) atau (a, d, c, b, a) ==> panjang = 10 + 12 + 8 + 15 = 45 I2 = (a, c, d, b, a) atau (a, b, d, c, a) ==> panjang = 12 + 5 + 9 + 15 = 41 I3 = (a, c, b, d, a) atau (a, d, b, c, a) ==> panjang = 10 + 5 + 9 + 8 = 32 a
12
12 5
10
d
a
b
9
10
8 15
c
d
15
a
b
c
d
b 5
9 8 c
Jadi, sirkuit Hamilton terpendek adalah I3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang sirkuit = 10 + 5 + 9 + 8 = 32.
20
BAB IV PENGOLAHAN DATA
1.
Lintasan Terpendek (Shortest Path)
(Algoritma lintasan terpendek dari simpul a ke semua simpul lain ) Langkah 0 (inisialisasi): - inisialisasi si = 0 dan di = mai untuk i = 1, 2, ..., n Langkah 1: - isi sa dengan 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi sudah pasti terpilih) - isi da dengan (tidak ada lintasan terpendek dari simpul a ke a) Langkah 2, 3, 4, 5, 6 n-1: - cari j sedemikian sehingga sj = 0 dan dj = min{d1, d2, ..., dn} - isi sj dengan 1 - perbarui di, untuk i = 1, 2, 3, …, n dengan: di (baru) = min{di (lama), dj + mji }. 45 1
50
2
10
5
40 20
15
10
3
15
20
4
35 30
3
6
Gambar : Lintasan Terpendek
Menentukan lintasan terpendek dari simpul 1 ke semua simpul lain.
21
Lelaran
Simpul yang dipilih
Lintasan
S
S
S
S
S
S
1
2
3
4
5
6
Inisial
-
-
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
2
3
1,3
1
0
1
0
0
0
3
4
1,3,4
1
0
1
1
0
0
4
2
1,3,4,2
1
1
1
1
0
0
5
5
1,5
1
1
1
1
1
0
D
D
D
D
D
D
1
2
3
4
5
6
0
50 (1,2) 50 (1,2) 50 (1,2) 45 (1,3,4,2) 45 (1,3,4,2) 45 (1,3,4,2)
10 (1,3) 10 (1,3) 10 (1,3) 10 (1,3) 10 (1,3) 10 (1,3)
40 (1,4) 40 (1,4) 25 (1,3,4) 25 (1,3,4) 25 (1,3,4) 25 (1,3,4)
45 (1,5) 45 (1,5) 45 (1,5) 45 (1,5) 45 (1,5) 45 (1,5)
(1,6) (1,6) (1,6) (1,6) (1,6) (1,6)
Tabel 3 Ilustrasi Algoritma Lintasan Terpendek
Jadi, lintasan terpendek dari: 1 ke 3 adalah 1, 3 dengan panjang = 10 1 ke 4 adalah 1, 3, 4 dengan jarak = 25 1 ke 2 adalah 1, 3, 4, 2 dengan jarak = 45 1 ke 5 adalah 1, 5 dengan jarak = 45 1 ke 6 tidak ada
22
BAB V KESIMPULAN
5. Kesimpulan 5.1 Lintasan Terpendek (Shortest Path) Pada lintasan terpendek kita bisa mengetahui rute atau jalur yang paling efisien (terpendek) dari suatu tempat ke tempat lainnya, kita pun bisa mempersingkat waktu dengan menggunakan jalur yang efisien, dan juga bisa menghemat biaya atau ongkos transportasi. Biasanya pada lintasan terpendek menggunakan algoritma yang digunakan untuk memecahkan permasalahan lintasan terpendek yang terdapat pada suatu graf. Algoritma ini digunakan pada graf berbobot dengan syarat bobot dari masing-masing sisi haruslah bernilai positif ( >=0 ). Dalam mencari lintasan terpendek, algoritma yang paling banyak digunakan orang ialah algoritma Dijkstra, karena kerjanya paling efisien dan tidak membutuhkan waktu yang banyak. Algoritma Dijkstra :
M = mij , yang dalam hal ini, mij = bobot sisi (i, j)
(pada graf tak berarah
mij = m ji ). mii = 0
mij = , jika tidak ada sisi dari simpul i ke simpul j Selain matriks M, kita menggunakan larik S = [ s i ] yang dalam hal ini, s i = 1, jika simpul i termasuk ke dalam lintasan terpendek s i = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek
dan larik / tabel D = [ d i ] yang dalam hal ini d i = panjang lintasan dari simpul awal s ke simpul j
23
5.2 Sirkuit Euler Untuk membuat graf G yang mempunyai lintasan Euler harus memenuhi 2 syarat yaitu : Graf terhubung, dan Graf tidak mempunyai simpul derajat ganjil sama sekali atau mempunyai 2 buah simpul berderajat ganjil. Sebuah graf disebut terhubung jika graf tersebut hanya terdiri atas satu bagian (satu komponen) maka graf itu disebut graf terhubung. Sementara untuk membuat graf G yang mempunyai sirkuit Euler harus memenuhi 2 syarat yaitu : Graf terhubung, dan semua simpul berderajat genap. Graf berarah G mempunyai lintasan Euler jika G terhubung dan setiap simpul mempunyai derajat masuk dan derajat keluar sama kecuali 2 simpul. Yang pertama memiliki derajat keluar satu lebih besar dari derajat masuk dan yang kedua memiliki derajat masuk satu lebih besar dari derajat keluar. Graf berarah G mempunyai sirkuit Euler jika hanya jika G terhubung dan setiap simpul mempunyai derajat masuk dan derajat keluar sama.
Gambar : (Lintasan Euler)
Gambar : (Sirkuir Euler)
24
6 SARAN Dalam penarikan kesimpulan dalam teori graf, banyak hal yang harus di perhatikan agar penarikan kesimpulan dapat di lakukan dengan benar. Kepada para pembaca yang kelak ingin membuat makalah atau karya tulis mengenai teori graf,di sarankan agar lebih mau membaca dan mempelajari tentang teori graf. Penulis sangat menyadari bahwa karya tulis ini masih jauh dari sempurna, oleh karena itu, penulis sangat mengharap kritik dan saran yang membangun dari para pembaca, agar penulis dapat memperbaiki di waktu yang akan datang
25
DAFTAR PUSTAKA
Tirta Seputro, Theresia. 1995. Teori Graf. Jakarta : Erlangga Di kutip dari : http://nurhayati15.blogspot.com/2012/01/teka-teki-jembatan-konisberg.html http://indigomenulis.blogspot.com/2011/11/jembatan-konigsberg.html http://nic.unud.ac.id/~lie_jasa/Diskrit%20II%20Pertemuan%20XI%20dan%20XII.pd f Sutarno, Heri. 2000. Matematika Distrik. Bandung : Universitas Pendidikan Indonesia Tri Baskoro, Edy. 2007. Matematika Distrik. Bandung : Institut Teknologi Bandung.
26
