PENYELESAIAN MASALAH CHINESE POSTMAN PADA GRAF CAMPURAN MENGGUNAKAN METODE HEURISTIK BALANS-GENAP
ALI YUDHA ZULFIKAR
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
ABSTRAK ALI YUDHA ZULFIKAR. Penyelesaian Masalah Chinese Postman pada Graf Campuran dengan Menggunakan Metode Heuristik Balans-Genap. Dibimbing oleh FARIDA HANUM dan TONI BAKHTIAR. Salah satu permasalahan dalam menentukan rute optimal yang paling dikenal adalah Chinese Postman Problem (CPP). Di antara sekian banyak CPP, di dalam karya ilmiah ini dibahas mengenai mixed CPP (MCPP), di mana representasi graf dari MCPP itu sendiri memiliki dua jenis sisi, yaitu sisi berarah dan sisi takberarah. Metode dasar yang digunakan dalam menyelesaikan permasalahan ini adalah metode heuristik yang bernama metode balans-genap. Algoritme yang digunakan yakni algoritme Dijkstra dan algoritme van Aardenne-Ehrenfest & de Bruijn yang bertujuan menentukan rute terpendek dan sirkuit Euler. Secara khusus, metode inoutdegree dan largecycle diterapkan untuk memastikan kondisi balans-genap terpenuhi. Pendekatan ini diterapkan dalam penentuan sirkuit Euler yang berhubungan dengan rute terpendek dalam kasus pemasangan instalasi listrik di kota Bogor. Kata Kunci: Balans, Genap, Sirkuit Euler, inoutdegree, largecycle.
ABSTRACT ALI YUDHA ZULFIKAR. Solution of the Chinese Postman Problem for Mixed Graph with Balance-Even Heuristic Method. Under direction of FARIDA HANUM and TONI BAKHTIAR. One of the problems in determining an optimal route is the well-known Chinese Postman Problem (CPP). Among many kinds of CPP, this work discusses the mixed one (MCPP), where the representing graph has two types of edge: directed and undirected edges. We employ a heuristic based method, namely balance-even method, to solve the problem. A series of algorithms such as Dijkstra’s and van Aardenne-Ehrenfest and de Bruijn are used in constructing the shortest path and the Euler circuit. In particular, inoutdegree and largecycle methods are implemented in performing balance-even condition. We apply this approach in determining Euler circuit related to the shortest path in the case of electrical devices installation in the city of Bogor. Keyword: Balance, Even, Euler Circuit, inoutdegree, largecycle.
PENYELESAIAN MASALAH CHINESE POSTMAN PADA GRAF CAMPURAN MENGGUNAKAN METODE HEURISTIK BALANS-GENAP
ALI YUDHA ZULFIKAR
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
Judul Skripsi Nama NIM
: Penyelesaian Masalah Chinese Postman pada Graf Campuran Menggunakan Metode Heuristik Balans-Genap : Ali Yudha Zulfikar : G54070034
Disetujui
Pembimbing I
Pembimbing II
Dra. Farida Hanum, M.Si. NIP: 19651019 199103 2 002
Dr. Toni Bakhtiar, M.Sc. NIP: 19720627 199702 1 002
Diketahui Ketua Departemen
Dr. Berlian Setiawaty, MS NIP: 19650505 198903 2 004
Tanggal Lulus : ………………………………
KATA PENGANTAR Puji dan syukur penulis panjatkan kepada Allah SWT atas segala rahmat dan karunia-Nya serta selawat dan salam kepada Nabi Muhammad SAW sehingga karya ilmiah ini berhasil diselesaikan. Penyusunan karya ilmiah ini tidak lepas dari peranan berbagai pihak. Untuk itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada: 1. Keluargaku tersayang: Mami (terima kasih atas doa, dukungan, kesabaran, kepercayaan, dan kasih sayangnya), Alm. Bapakku yang pasti selalu mendoakan, kakakku (terima kasih atas doa, dukungan, kasih sayang, dan motivasinya), Hanni Alfiyani yang selalu mendoakan dan memberi motivasi, serta keluarga besar baik dari Mami, Bapak maupun dari Hanni Alfiyani (terima kasih atas doanya), 2. Bapak Dodi Priambodo dan keluarga selaku orang tua asuh saya, terima kasih atas dorongan motivasi, doa, serta bantuannya selama perkuliahan, 3. Dra. Farida Hanum, M.Si selaku dosen pembimbing I yang selalu memberi motivasi dan bantuannya untuk menyelesaikan karya ilmiah ini, 4. Dr. Toni Bakhtiar, M.Sc selaku dosen pembimbing II (terima kasih atas semua ilmu, kritik, saran, dan motivasinya), 5. Dr. Ir. Bib Paruhum Silalahi, M.Kom. selaku penguji (terima kasih atas dorongan semangat, ilmu, dan sarannya), 6. segenap dosen Departemen Matematika: Bu Anggi, Bu Teduh, Pak Donny, Pak Hadi, Pak Wayan, Pak Kutha, Pak Prapto, dan lainnya (terima kasih atas semua ilmu yang telah diberikan), 7. staf Departemen Matematika: Pak Yono, Bu Susi, Mas Heri, Pak Bono, Bu Ade, dan Mas Deni, dan lainnya (terima kasih atas bantuan dan motivasinya), 8. sahabat-sahabat saya di Bimbingan Belajar REC, Best Friend, dan DoTa Lover’s yang tidak bisa saya sebutkan satu persatu (terima kasih atas motivasi dan doanya), 9. kakak-kakak Matematika angkatan 41, 42, dan 43 yang menjadi cermin untuk menjadi pribadi yang lebih baik, 10. teman-teman Matematika angkatan 44 seperjuangan yang selalu mengisi semangat, 11. adik-adik Matematika angkatan 45 dan 46 yang terus mendukung agar berkembang, 12. Gumatika yang menunjukkan sebuah hal yang baru, 13. teman-teman TPB: Dodi, Epul, Dudi, Nizar, Auzi, Tina, Juju, Elis (terima kasih atas motivasi, dukungan, dan kebersamaannya), 14. semua pihak yang membantu dalam penyusunan skripsi ini. Semoga karya ilmiah ini bermanfaat bagi dunia ilmu pengetahuan khususnya matematika dan menjadi inspirasi bagi penelitian-penelitian selanjutnya.
Bogor, Juli 2012
Ali Yudha Zulfikar
RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 21 Februari 1989 dari bapak Endang Suganda (Alm) dan ibu Tien Ngatina. Penulis merupakan putra bungsu dari lima bersaudara. Tahun 2001 penulis lulus dari SD Negeri Pengadilan III Bogor, Tahun 2004 lulus dari SMP Negeri 7 Bogor, tahun 2007 penulis lulus dari SMA Rimba Madya Bogor dan pada tahun yang sama diterima sebagai mahasiswa IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis memilih mayor Matematika minor Manajemen Fungsional, Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis menjadi asisten mata kuliah Analisis Numerik (S1) pada semester ganjil tahun akademik 2009-2010 dan 2011-2012. Pada tahun 2010-2011 penulis mengajar di bimbingan belajar yang terdapat di Institut Pertanian Bogor. Selain itu pada tahun yang sama, penulis mengajar privat SD, SMP, dan SMA. Tahun 2009-2012 penulis mendapatkan beasiswa orang tua asuh dari Pertamina. Tahun 2007-2009 dan 2011-2012 penulis mendapatkan beasiswa BBM (Bantuan Belajar Mahasiswa) dari Institut Pertanian Bogor. Penulis aktif di berbagai kegiatan kemahasiswaan. Penulis pernah menjabat sebagai Staf Divisi Sumber Daya Mahasiswa di Himpunan Profesi Gugus Mahasiswa Matematika (Gumatika) Institut Pertanian Bogor pada tahun 2009-2010. Pada tahun 2010-2011 penulis menjabat sebagai Kepala Divisi di tempat yang sama. Penulis pernah menjadi ketua Masa Perkenalan Departemen untuk angkatan 2009 atau angkatan 46. Penulis juga pernah menjadi panitia dan koordinator di berbagai acara kemahasiswaan.
DAFTAR ISI Halaman
DAFTAR GAMBAR ................................................................................................................. ix DAFTAR LAMPIRAN .............................................................................................................. x I
PENDAHULUAN 1.1 Latar Belakang ............................................................................................................ 1 1.2 Tujuan Penulisan ......................................................................................................... 1
II
LANDASAN TEORI 2.1 Teori Graf ................................................................................................................... 1 2.2 Graf Euler ................................................................................................................... 8 2.3 Algoritme van Aardenne Ehrenfest & de-Bruijn ........................................................... 9 2.4 Algoritme Dijkstra ..................................................................................................... 10
III MIXED CHINESE POSTMAN PROBLEM 3.1 Pencarian Solusi MCPP dengan menggunakan Metode Balans-Genap ..................... 11 IV APLIKASI PERMASALAHAN 4.1 Permasalahan Pemasangan Instalasi Listrik ................................................................ 14 4.2 Penyelesaian dengan Metode Balans-Genap ............................................................... 15 V
SIMPULAN DAN SARAN 5.1 Simpulan ................................................................................................................... 19 5.2 Saran ......................................................................................................................... 19 DAFTAR PUSTAKA ....................................................................................................... 20 LAMPIRAN .................................................................................................................... 21
viii
DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
Halaman Graf = ( , )............................................................................................................. 2 Graf berarah = ( , ) ............................................................................................... 2 Graf campuran .............................................................................................................. 2 Graf berbobot ............................................................................................................... 2 Adjacent dan Incident ................................................................................................... 3 Multigraf ...................................................................................................................... 3 Multidigraf ................................................................................................................... 3 Derajat pada graf .......................................................................................................... 3 Graf genap .................................................................................................................... 3 Digraf balans ................................................................................................................ 4 Graf campuran .............................................................................................................. 4 Walk pada graf berarah ................................................................................................. 4 Graf berarah ................................................................................................................. 6 Spanning tree ............................................................................................................... 6 Spanning arborescence ................................................................................................. 6 Graf 2-regular ............................................................................................................... 6 Graf untuk ilustrasi matching ........................................................................................ 6 Graf untuk ilustrasi matching yang perfect .................................................................... 7 Graf berbobot ............................................................................................................... 7 Network ........................................................................................................................ 7 Network dengan kapasitas dan flow ............................................................................... 8 Graf Euler ..................................................................................................................... 8 Graf campuran yang bukan graf Euler ........................................................................... 9 Graf Euler ..................................................................................................................... 9 Digraf Euler .................................................................................................................. 9 Spanning arborescence ................................................................................................. 9 Pelabelan pada sisi berarah ........................................................................................... 10 Graf contoh algoritme Dijkstra ...................................................................................... 10 Solusi path terpendek algoritme Dijkstra dengan verteks awal 3 .................................... 10 Graf Euler kasus Mixed CPP ......................................................................................... 11 Graf campuran .............................................................................................................. 12 Subgraf dari Gambar 31 ................................................................................................ 12 Skema penyelesaian masalah MCPP ............................................................................. 13 Peta lokasi pemasangan instalasi listrik di Bogor Selatan ............................................... 14 Graf kasus Bogor Selatan .............................................................................................. 15 Graf = ( , ) ............................................................................................................ 15 Graf 1 ......................................................................................................................... 16 Graf output 2 = ( , ) ........................................................................................ 17 Graf lengkap ................................................................................................................. 17 Graf output =( , 18 2 ) ..................................................................................... Graf berarah ................................................................................................................. 18 Spanning arborescence digraf kasus Bogor Selatan ....................................................... 18 Digraf MCPP yang sudah dilabeli ................................................................................. 19 Graf MCPP ................................................................................................................... 22 Solusi path terpendek dengan verteks awal 0 = 3 ........................................................ 22 Graf = ( , ) ........................................................................................................... 24 Graf lengkap ................................................................................................................. 26
ix
DAFTAR LAMPIRAN Halaman 1
Penentuan jarak terpendek dengan menggunakan algoritme Dijkstra (verteks
= 3) ...
22
2
Program LINGO 8.0 ....................................................................................................
23
3
Penentuan jarak terpendek dengan menggunakan algoritme Dijkstra ..............................
24
4
Penentuan matching yang perfect dengan bobot minimum .............................................
26
0
x
DAFTAR PUSTAKA Ahuja RK, Magnanti TL, and Orlin JB. 1993. Network Flows: Theory, Algorithms and Applications. New Jersey: Prentice-Hall. Assad AA, Golden BL. 1995. Arc routing methods and applications. Di dalam: Ball MO, Magnanti TL, Monna CL, Nemhauser GL, editor. Handbook in Operations Research and Management Science. Volume 8: Network Routing. North-Holland: Elsevier. Hlm 375-388. Balakrishnan VK. 1997. Schaum’s Outline of Theory and Problems of Graph Theory. New York: McGraw-Hill. Chartrand G, Oellermann OR. 1993. Applied and Algorithmic Graph Theory. New York: McGraw-Hill. Chartrand G, Zhang P. 2009. Chromatic Graph Theory. London: CRC Pr.
Diestel R. 1997. Graph Theory. New York: Springer-Verlag. Eiselt HA, Gendreau M, Laporte G. 1995. Arc routing problem, Part 1: The Chinese Postman Problem. Operations Research 43(2): 231-242. Foulds LR. 1992. Graph Theory Applications. New York: Springer Publishing. Vasudev C. 2006. Graph Theory with Applications. New Delhi: New Age International. Yaoyuenyong K, Charnsethikul P, Chankong V. 2002. A heuristic algorithm for the mixed Chinese postman problem. Optimization and Engineering 3: 157-187.
LAMPIRAN
I PENDAHULUAN 1.1 Latar Belakang Banyak permasalahan pada dunia nyata seperti masalah jaringan dan komunikasi. Salah satu permasalahan jaringan yang sering terjadi yaitu mengenai penyaluran barang antara pihak distributor dan konsumen. Berbagai penyebab terjadinya permasalahan ini, dimulai dari biaya pengiriman, rute penyaluran, banyaknya permintaan dan lain sebagainya. Untuk mengatasi permasalahan tersebut, para ilmuwan khusus di bidang matematika melakukan sebuah penelitian. Para ilmuwan di Cina telah mengemukakan hasil penelitiannya berupa pencarian rute terpendek untuk berbagai kasus, dan diimplementasikannya ke dalam sebuah graf. Salah satu kasus tersebut yaitu The Chinese Postman Problem (CPP). The Chinese Postman Problem (CPP) termasuk ke dalam Arc Routing Problem (ARP). CPP pertama kali dikemukakan oleh Meigu Guan, seorang pakar matematika asal Cina. Kasus CPP berasal dari permasalahan yang terdapat pada kantor pos, yakni menentukan rute yang optimal dalam pengiriman surat, sehingga permasalahan yang muncul adalah bagaimana menentukan jarak minimum dengan kondisi setiap ruas jalan harus dilewati paling tidak satu kali. Namun seiring dengan perkembangan jaman, masalah CPP tidak hanya dapat diterapkan
pada pengiriman surat saja, tetapi juga dalam hal lain seperti pengiriman koran harian, rute bus sekolah, pengambilan sampah, dan lainlain. Graf pada masalah CPP (Chinese Postman Problem) dapat berupa graf berarah atau graf tidak berarah. Graf Mixed Chinese Postman Problem (MCPP) atau disebut juga graf campuran merupakan graf yang terdiri dari sisi yang berarah dan sisi tidak berarah. MCPP dapat dipandang sebagai masalah penentuan sirkuit Euler pada graf yang balans dan genap. Dua syarat tersebut harus terpenuhi agar sirkuit Euler ada. Dalam karya ilmiah ini akan dibahas penentuan sirkuit Euler pada graf campuran menggunakan metode balans-genap. Sumber utama karya ilmiah ini adalah artikel berjudul A Heuristic Algorithm for the Mixed Chinese Postman Problem (Yaoyuenyong et al. 2002). 1.2 Tujuan Penulisan Tujuan dari penulisan karya ilmiah ini adalah : 1. menyelesaikan masalah MCPP dengan algoritme heuristik balans-genap, 2. mengaplikasikan masalah pencarian sirkuit Euler ke dalam masalah penentuan rute pemasangan instalasi listrik.
II LANDASAN TEORI Dalam bab ini akan dibahas tentang teoriteori yang berkaitan dengan bahasan karya ilmiah ini. 2.1 Teori Graf Teori graf lahir pada tahun 1736 melalui tulisan Euler yang berisi tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa. Kurang lebih dua abad setelah lahirnya tulisan Euler tersebut, aktivitas dalam bidang teori graf relatif kecil. Pada tahun 1920-an kegiatan
tersebut muncul kembali dipelopori oleh D. Konig yang mengumpulkan hasil-hasil pemikiran para ahli matematika tentang teori graf termasuk hasil pemikirannya sendiri, kemudian dikemasnya dalam bentuk buku yang diterbitkan pada tahun 1936. Dalam periode yang sangat singkat, teori graf kini mengalami perkembangan yang sangat pesat. Definisi 1 (Graf) Suatu graf adalah pasangan terurut ( , ) dengan , atau biasa disebut ( ), adalah himpunan berhingga dan takkosong
2
dari elemen graf yang disebut verteks (node, point), sedangkan , atau biasa disebut ( ), adalah himpunan pasangan tak terurut yang menghubungkan dua elemen subset dari yang disebut sisi (edge, line). Setiap sisi { , } pada biasanya dinotasikan dengan atau . (Chartrand & Zhang 2009)
merupakan himpunan sisi-sisi tidak berarah pada . (Yaoyuenyong et al. 2002)
:
1
7 5
8
2
6
9
Definisi 2 (Order dan size graf) Banyaknya verteks dari suatu graf disebut order dan banyaknya sisi pada suatu graf disebut size dari graf.
3 4
Gambar 3 Graf campuran.
:
Pada Gambar 3, sisi 1 , 9 , 4 dan 6 merupakan sisi berarah, sisi 2 , 3 , 5 , 7 , dan 8 merupakan sisi yang tidak berarah. Gambar 1 Graf
= ( , ).
Pada Gambar 1 diperlihatkan bahwa = , , , dan = {{ , }, { , }, { , }}. Order dari graf pada Gambar 1 ialah 4 dan size-nya ialah 3. Definisi 3 (Graf berarah/digraf) Graf berarah adalah pasangan terurut ( , ) dengan himpunan takkosong yang hingga, dan himpunan pasangan terurut yang menghubungkan elemen-elemen di . Elemen-elemen dari disebut sisi berarah (arc). Sisi berarah ( , ) dinyatakan dengan garis berarah dari ke .
Definisi 5 (Graf/digraf berbobot) Suatu graf = , atau digraf = , dikatakan berbobot jika terdapat sebuah fungsi : atau : (dengan adalah himpunan bilangan real) yang memberikan sebuah bilangan real, disebut bobot, pada setiap sisi di atau sisi berarah di . Setiap bobot dengan atau dinotasikan dengan . (Foulds 1992)
:
8 7
12 10
(Chartrand & Zhang 2009) Gambar 4 Graf berbobot.
:
Bobot tiap sisi untuk graf pada Gambar 4 adalah = 8, = 12, = 7, = 10.
Gambar 2 Graf berarah
= ( , ).
Pada Gambar 2 diperlihatkan bahwa = , , , dan = {( , ), ( , ), ( , )}. Definisi 4 (Graf campuran) Graf campuran = ( , ) merupakan graf yang memiliki dua jenis sisi, yakni sisi yang berarah dan tidak berarah. merupakan himpunan sisi-sisi berarah pada dan
Definisi 6 (Adjacent dan incident) Misalkan dan verteks pada graf . Verteks dikatakan tetangga (adjacent) dari jika ada sisi yang menghubungkan verteks dan , yaitu = . Himpunan semua tetangga dari verteks dinotasikan dengan ( ). Jika = adalah sisi pada graf maka dikatakan incident dengan verteks dan . (Chartrand & Zhang 2009)
3
:
:
2 3
1 6
4 5
Gambar 7 Multidigraf. Gambar 5 Adjacent dan incident. Ilustrasi adjacent dan incident diperlihatkan pada Gambar 5. Verteks adjacent dengan , , dan . Verteks incident dengan 2 tetapi tidak incident dengan 4 . Definisi 7 (Graf lengkap) Suatu graf yang ber-order dengan setiap verteks pada adjacent dengan verteks lainnya disebut graf lengkap, dinotasikan dengan . (Chartrand & Oellermann 1993)
Definisi 9 (Derajat/degree) Derajat suatu verteks adalah banyaknya sisi yang incident dengan verteks , dan dinotasikan dengan deg atau ( ). Jika banyaknya simpul yang incident dengan verteks adalah bilangan ganjil, maka dikatakan berderajat ganjil. Jika banyaknya simpul yang incident dengan verteks adalah bilangan genap, maka dikatakan berderajat genap. (Vasudev 2006)
:
Pada Gambar 5 diperlihatkan bahwa setiap verteks adjacent dengan verteks lainnya, sehingga graf pada Gambar 5 merupakan graf lengkap. Definisi 8 (Multigraf/multidigraf) Suatu graf/digraf dikatakan multigraf atau multidigraf bila graf/digraf tersebut memiliki lebih dari satu sisi/sisi berarah yang incident dengan satu pasang verteks. (Foulds 1992) Ilustrasi multigraf dapat dilihat pada Gambar 6 berikut.
Gambar 8 Ilustrasi derajat pada graf. Pada Gambar 8 terlihat bahwa verteks , , dan berderajat genap, sedangkan verteks dan berderajat ganjil. Definisi 10 (Graf genap) Suatu graf dikatakan graf genap, jika setiap verteksnya berderajat genap. (Eiselt et al. 1995)
: :
Gambar 9 Graf genap. Gambar 6 Multigraf. Gambar 6 merupakan contoh multigraf karena verteks dan dihubungkan oleh lebih dari satu sisi. Ilustrasi multidigraf bisa dilihat pada Gambar 7 berikut.
Ilustrasi graf genap bisa dilihat pada Gambar 9, karena pada Gambar 9 setiap verteks berderajat genap. Definisi 11 (Derajat masuk/in-degree) Pada graf berarah, in-degree suatu verteks , yang dinotasikan dengan ( ), adalah
4
banyaknya sisi berarah yang berakhir di verteks . (Vasudev 2006) Pada Gambar 2 diperlihatkan derajat masuk tiap verteksnya = 0, = 1, = 1, = 1. Definisi 12 (Derajat keluar/out-degree) Pada graf berarah, out-degree suatu verteks , yang dinotasikan dengan + ( ), adalah banyaknya sisi berarah yang dimulai pada verteks . (Vasudev 2006) Pada Gambar 2 diperlihatkan derajat keluar tiap verteksnya + = 2, + = + + 0, = 0, = 1. Definisi 13 (Digraf balans) Suatu digraf dikatakan balans jika setiap verteks pada digraf tersebut memiliki = 0, dengan adalah selisih dari derajat masuk dengan derajat keluar verteks . (Diestel 1997)
:
Definisi 15 (Graf campuran genap) Suatu graf campuran dikatakan graf genap jika underlying graph-nya berupa graf genap. (Assad & Golden 1995)
:
Gambar 11 Graf campuran. Pada Gambar 11, graf tersebut berupa graf genap dengan underlying graph-nya bisa dilihat pada Gambar 9. Definisi 16 (Jalan/walk) Walk pada suatu graf adalah barisan berhingga, = atau +1 +1 = yang dimulai dari +1 suatu verteks dan berakhir pada suatu verteks juga, sehingga setiap sisi di dalam barisan harus incident dengan verteks sebelum dan sesudahnya. (Chartrand & Zhang 2009) Definisi 17 (Walk berarah) Walk berarah pada suatu digraf adalah walk yang sesuai dengan arah sisinya atau tidak berlawanan arah. (Vasudev 2006)
: Gambar 10 Ilustrasi digraf balans.
2 3
1 4
Digraf pada Gambar 10 adalah digraf balans karena setiap verteks memiliki = 0. Definisi 14 (Underlying graph) Jika suatu graf didapat dengan cara menghapus semua arah dari sisi berarah pada digraf , maka graf tersebut adalah underlying graph dari digraf . (Vasudev 2006) Ilustrasi underlying graph bisa dilihat dari Gambar 9 dan Gambar 10. Graf pada Gambar 9 merupakan underlying graph dari digraf pada Gambar 10.
5
Gambar 12 Graf berarah. Ilustrasi walk berarah pada suatu digraf bisa dilihat pada Gambar 12. = 2 4 adalah walk berarah. Definisi 18 (Trail) Trail pada suatu graf adalah walk dengan semua sisi dalam barisannya tidak berulang. (Chartrand & Zhang 2009) Ilustrasi trail bisa dilihat pada Gambar 5, = adalah trail. 3 5 4
5
Definisi 19 (Path) Path pada suatu graf adalah walk yang setiap verteks pada barisannya hanya muncul satu kali. (Vasudev 2006) Ilustrasi path bisa dilihat pada Gambar 5, yaitu = 2 4 5 . Definisi 20 (Path berarah) Path berarah pada suatu digraf adalah walk berarah dengan semua verteks dalam barisannya tidak berulang. (Vasudev 2006)
Ilustrasi cycle bisa dilihat pada Gambar 8. Graf pada Gambar 8 memiliki cycle = . Definisi 25 (Terhubung/connected) Suatu graf disebut terhubung (connected) jika untuk setiap verteks dari terhubung. Verteks dengan dikatakan terhubung jika ada setidaknya satu path dari verteks ke verteks . (Vasudev 2006)
Ilustrasi path berarah bisa dilihat pada Gambar 12. = adalah path 2 4 5 berarah.
Definisi 26 (Digraf terhubung) Suatu digraf dikatakan terhubung (connected) jika underlying graph-nya terhubung. (Chartrand & Oellermann 1993)
Definisi 21 (Sirkuit) Pada graf tidak berarah, sirkuit adalah trail tertutup yang takkosong. (Chartrand & Zhang 2009)
Definisi 27 (Subgraf) Suatu graf dikatakan subgraf dari graf jika ( ) ( ) dan ( ) ( ). (Chartrand & Oellermann 1993)
Ilustrasi sirkuit bisa dilihat pada Gambar 5, yaitu = 3 6 2 .
Graf pada Gambar 1 merupakan subgraf dari graf pada Gambar 8.
Definisi 22 (Sirkuit berarah) Pada suatu digraf, sirkuit berarah adalah walk berarah yang tertutup sehingga barisannya dimulai dan diakhiri pada verteks yang sama dan tidak ada sisi yang diulang. (Vasudev 2006)
Definisi 28 (Spanning subgraph) Suatu subgraf dikatakan spanning subgraph jika subgraf tersebut mengandung semua verteks pada graf . (Vasudev 2006)
Ilustrasi sirkuit berarah bisa dilihat pada Gambar 12, yaitu = 2 1 3 . Definisi 23 (Semisirkuit) Pada suatu digraf, semisirkuit adalah sirkuit pada underlying graph , tetapi bukan merupakan sirkuit berarah pada digraf tersebut. (Vasudev 2006)
Graf pada Gambar 1 merupakan spanning subgraph dari graf pada Gambar 4. Definisi 29 (Tree pada graf) Suatu graf terhubung yang tidak memiliki cycle disebut tree. (Chartrand & Zhang 2009) Graf pada Gambar 1 merupakan tree.
Ilustrasi semisirkuit bisa dilihat pada Gambar 12, yaitu = 3 1 2 .
Definisi 30 (Tree pada digraf) Suatu digraf terhubung yang tidak memiliki cycle disebut tree pada digraf. (Chartrand & Zhang 2009)
Definisi 24 (Cycle) Pada graf tidak berarah, cycle adalah path tertutup yang takkosong. (Chartrand & Zhang 2009)
Ilustrasi tree untuk digraf dapat dilihat pada Gambar 2.
6
Definisi 31 (Spanning tree) Suatu spanning tree adalah spanning subgraph yang merupakan tree. (Vasudev 2006)
:
2 3
1 4
15 merupakan spanning arborescence dari digraf pada Gambar 7, dengan akar arborescence-nya di .
Definisi 34 (Graf r-regular) Sebuah graf merupakan graf r-regular, atau graf regular berderajat r, jika setiap verteks pada memiliki derajat r. (Chartrand & Oellermann 1993)
5
Gambar 13 Graf berarah.
:
:
2
4 5
Gambar 14 Spanning tree. Digraf pada Gambar 14 adalah spanning tree dari digraf pada Gambar 13. Definisi 32 (Arborescence) Graf berarah disebut arborescence jika a.
tidak memiliki sirkuit berarah maupun semisirkuit. b. Pada terdapat tepat satu verteks yang memiliki = 0.
Gambar 16 Graf 2-regular. Pada Gambar 16, setiap verteks memiliki derajat 2 atau graf regular berderajat 2. Definisi 35 (Matching) Matching pada sebuah graf merupakan subgraf 1-regular, yaitu berupa himpunan sisi-sisi yang tidak adjacent. (Chartrand & Oellermann 1993)
: 4
1 7
Verteks
disebut akar arborescence. (Vasudev 2006)
2
3 6 5
Definisi 33 (Spanning arborescence) Spanning arborescence pada digraf adalah spanning tree yang berupa arborescence. (Vasudev 2006)
Gambar 17 Graf untuk ilustrasi matching. = { 1 , 2 , 3 } adalah salah satu matching pada graf di Gambar 17. Definisi 36 (Matching yang Perfect) Jika adalah sebuah graf ber-order yang memiliki matching berkardinalitas /2, maka matching tersebut dikatakan matching yang perfect. (Chartrand & Oellermann 1993)
:
Gambar 15 Spanning arborescence. Ilustrasi spanning arborescence bisa dilihat pada Gambar 15. Digraf pada Gambar
7
pada , maka = ( , )= adalah kapasitas sisi berarah . (Chartrand & Oellermann 1993)
: 2
1
: 3
5
2
2
5
3
4
2
Gambar 18 Graf untuk ilustrasi matching yang perfect.
Gambar 20 Network.
Graf pada Gambar 18 ber-order 6 dan = { 1 , 3 , 5 } merupakan matching yang berkardinalitas 3, sehingga adalah matching yang perfect.
Network pada Gambar 20 menunjukkan bahwa , =5 dan , = 2. Source ( ) pada Gambar 20 memiliki derajat masuk nol dan sink ( ) pada Gambar 20 memiliki derajat keluar nol.
Definisi 37 (Matching berbobot minimum) Matching berbobot minimum merupakan matching dengan jumlah bobot pada sisinya adalah minimum. (Chartrand & Oellermann 1993)
: 6
2
Definisi 39 (Flow / arus) Suatu flow pada suatu network dengan digraf = ( , ) adalah suatu + pemadanan {0} yang memadankan setiap sisi = ( , ) dengan bilangan real taknegatif, sehingga memenuhi kondisi sebagai berikut : 1.
2 1
3 1 2
Gambar 19 Graf berbobot. Matching yang perfect pada graf Gambar 19 hanya 1 = { , , . , , } dengan bobot 10 dan , , , } 2 = { , , dengan bobot 6. Jadi, 2 adalah matching yang perfect dengan bobot minimum. Definisi 38 (Network) Secara umum, network merupakan sebuah digraf atau graf berarah =( , ) dengan dua verteks spesial yaitu verteks yang disebut source dan verteks yang disebut sink, serta memiliki fungsi pada yang bernilai integer taknegatif yang disebut kapasitas. Jika = ( , ) adalah sebuah arc
6
( ) ( ) untuk setiap sisi di dinamakan kendala kapasitas.
2.
(, )= { :( , )
}
yang
(, ) { :( , )
}
untuk semua , yang dinamakan kendala konservasi. (Chartrand & Oellermann 1993) Nilai = (, )= pada sisi dapat dipandang sebagai banyaknya komoditas yang diangkut pada sisi tersebut, sedangkan kendala konservasi menyatakan bahwa total arus yang masuk ke suatu verteksantara (yaitu verteks selain verteks dan ) sama dengan total arus yang keluar dari verteks tersebut.
8
berkaitan dengan graf Euler yang digunakan dalam karya ilmiah ini.
: (2,1)
(3,2) (2,5)
(5,3) (5,2)
Gambar 21
(6,5)
Network dengan kapasitas dan flow.
Definisi 41 (Sirkuit Euler) Sirkuit Euler adalah sirkuit yang melewati semua sisi pada graf tepat satu kali. (Vasudev 2006)
:
1
Pada Gambar 21 diberikan contoh network berikut kapasitas dan flow sisi berarah ( , ). Sebagai contoh, sisi berarah ( , ) memiliki kapasitas 5 dan flow 2.
2
3
4
5 6
Gambar 22 Graf Euler. Definisi 40 (Minimum Cost Flow) Diberikan network dengan digraf = , . Misalkan adalah biaya yang diperlukan yang melalui arc ( , ) dan adalah kapasitas yang melalui arc ( , ) . Minimum cost flow merupakan suatu permasalahan dalam menentukan flow dengan biaya minimum pada suatu graf berarah. Formulasi matematikanya secara umum sebagai berikut min
= (, )
Kendala = () { :( , )
}
0
{ :( , )
}
(, ) (Ahuja et al. 1993)
Nilai ( ) menyatakan banyaknya penawaran (bila ( ) > 0) atau permintaan (bila ( ) < 0), dengan . 2.2 Graf Euler Leonhard Euler (1707-1783) adalah seorang peneliti yang lahir di Swiss. Ia dipandang sebagai salah satu matematikawan terbesar sepanjang masa. Leonhard Euler menyumbangkan berbagai penemuan penting di bidang yang beragam seperti kalkulus dan teori graf. Dalam penelitiannya di bidang teori graf, Euler mengenalkan penemuan yang paling terkenal yaitu graf Euler. Berikut ini akan dijelaskan beberapa definisi dan teorema yang
Ilustrasi sirkuit Euler bisa dilihat pada Gambar 22. Sirkuit Euler pada graf salah satunya = 1 3 4 6 5 2 . Definisi 42 (Graf/digraf Euler) Graf atau digraf yang memiliki sirkuit Euler disebut graf atau digraf Euler. (Vasudev 2006) Graf pada Gambar 22 merupakan graf Euler, karena graf tersebut memiliki sirkuit Euler. Teorema 1 campuran)
(Graf
Euler
pada
graf
Misalkan diberikan graf campuran =( , ), dengan himpunan sisi tak berarah dan himpunan sisi berarah. Graf campuran memiliki sirkuit Euler jika dan hanya jika a. terhubung dan genap b. untuk setiap ( ), berlaku |
,
,
|
,
dengan , adalah banyaknya sisi berarah yang berawal dari suatu verteks di dan berakhir di suatu verteks di , sedangkan , merupakan banyaknya sisi tidak berarah yang menghubungkan verteks di dengan verteks di , dan = \ . (Assad & Golden 1995) Graf pada Gambar 23 berikut tidak memiliki sirkuit Euler, walaupun syarat (a) sudah terpenuhi, namun syarat (b) tidak terpenuhi.
9
Misalkan = 1 , maka = 2,3,4,5,6 , sehingga nilai , = 0, , = 2, , = 0, dan , , = 0 2 >0= , , berarti terdapat ( ), sehingga berlaku , , > , Jadi syarat (b) tidak dipenuhi.
:
Banyak algoritme yang dapat digunakan dalam pencarian sirkuit Euler dalam suatu digraf. Salah satu dari algoritme itu adalah algoritme van Aardenne-Ehrenfest & de Bruijn (Balakrishnan 1997). Berikut ini akan dibahas langkah-langkah algoritme tersebut. Langkah 0. Diberikan digraf .
4 5
3
2.3 Algoritme van Aardenne-Ehrenfest & de Bruijn
Langkah 1. Dibangun sebuah spanning arborescence dari digraf yang berakar di . 6
1
2
Langkah 2. Sisi berarah yang keluar dari dan verteks-verteks lain diurutkan dan dilabeli sedemikian hingga sisi berarah terakhir yang dilabeli adalah sisi berarah pada arborescence.
Gambar 23 Graf campuran yang bukan graf Euler. Graf pada Gambar 24 berikut merupakan graf terhubung dan genap (syarat (a) terpenuhi).
: 1
3
2
Gambar 24 Graf Euler.
Langkah 3. Dimulai dari sembarang verteks, sisi berarah dengan label terendah yang belum dilewati dipilih untuk sampai ke verteks berikutnya. Prosedur ini dilanjutkan hingga semua sisi berarah telah dilewati. Berikut ini contoh sederhana untuk mengimplementasikan algoritme van Aardenne-Ehrenfest & de Bruijn pada sebuah digraf Euler. Langkah 0. Diberikan digraf Euler seperti pada Gambar 25.
Tabel 1 Penentuan syarat (b) berdasarkan graf pada Gambar 24 , {1} {2} {3} {1,2} 1,3 {2,3} {1,2,3}
{2,3} {1,3} {1,2} {3} {2} {1} {1,2,3}
0 1 1 1 0 1 0 0
, 1 0 1 1 1 0 0 0
Dari Tabel 1, dapat disimpulkan bahwa untuk setiap ( ), berlaku | , , | , . Jadi kriteria (b) pada Teorema 1 juga dipenuhi. Akibatnya mempunyai sirkuit Euler dan contoh sirkuit Eulernya adalah 2 3 1 2.
2
1
4
, 1 1 0 0 1 1 0 0
3
1
2
3
2
3
2 4
2
5
Gambar 25 Digraf Euler. Langkah 1. Spanning arborescence dari graf pada Gambar 25 yang berawal di verteks 1 adalah sebagai berikut : 1
2
3
5
4
Gambar 26 Spanning arborescence.
10
Langkah 2. Semua sisi berarah diurutkan dan dilabeli dimulai dari verteks 1 secara sembarang dengan label terakhir adalah label untuk sisi berarah yang dipakai di arborescence, sehingga label digraf menjadi seperti berikut. L2 1
2
L1 L2
L1
L1
L2 L1
L2 5
3
c. ditentukan = min{ ( )| }. Jika yang dipilih sebagai verteks dengan = , maka merupakan jarak antara 0 dengan , dan +1 , d. { +1 } dan { +1 }, e. + 1. Jika = 1, proses dihentikan; lainnya kembali ke langkah b. (Chartrand & Oellermann 1993) Berikut ini diberikan contoh penggunaan algoritme Dijkstra pada graf tidak berarah.
L2 4
Gambar 27 Pelabelan pada sisi berarah.
Diberikan graf berbobot berikut :
:
Langkah 3. Sirkuit Euler yang diperoleh, misalkan dimulai dari verteks 1, adalah : 1 4 2 5 1 2 3 4 5 1, dengan total bobot 21.
5 6
4
2
7
4
12
8
4
2
2 8
1
4
Solusi sirkuit Euler yang diperoleh tidak hanya seperti di atas. Jika dimulai dari verteks lain, maka yang dilaluinya pun berbeda namun dengan total bobot yang sama. 2.4 Algoritme Dijkstra Algoritme ini bisa digunakan untuk mencari path terpendek atau jarak terpendek pada graf atau digraf atau graf campuran yang tidak berbobot maupun yang berbobot pada graf ber-order . Misalkan diberikan graf berbobot = ( , ) dengan himpunan = {1,2,3, . } dan bobot pada tiap verteksnya taknegatif. Pada setiap langkah dalam algoritme didefinisikan sebuah variabel PARENT(v) yang menyatakan verteks yang mendahului verteks v pada path terpendek yang telah diperoleh. Variabel PARENT(v) diperbaharui jika ditemukan path yang lebih pendek. Misalkan adalah himpunan semua verteks dari yang jaraknya dengan 0 sudah ditentukan. Langkah-langkah algoritme penentuan path terpendek yang dimulai dari verteks ialah sebagai berikut.
1
5
6
5
6 3
2
3
Gambar 28 Graf contoh algoritme Dijkstra. Akan ditentukan jarak terpendek dari satu verteks ke verteks lainnya. Misalkan verteks awalnya adalah verteks 3, maka dengan algoritme Dijkstra akan diperoleh path terpendek dari verteks 3 menuju verteks lain seperti pada Gambar 29 (penghitungan lebih lengkap dapat dilihat pada Lampiran 1).
: 1
5
6 7
4
2 4
1 8
8 a. inisialisasikan sebuah verteks awal 0 dengan jarak 0), 0 = 0, ( { 0 }, { 0 }, dan jarak verteks lainnya bernilai untuk semua { 0 }, PARENT 0 ; jika = 1, maka proses dihentikan; lainnya, proses dilanjutkan. b. untuk setiap , sehingga ( ), diperiksa: Jika + ( ), maka proses dilanjutkan; lainnya, + ( ) dan PARENT( ) ,
6
2
3
5
3 Gambar 29 Solusi path terpendek algoritme Dijkstra dengan verteks awal 3. Misalkan dicari jarak terdekat dari verteks 3 ke verteks 1 pada graf Gambar 29, maka path-nya adalah = 3 4 1 dengan jarak 8.
III MIXED CHINESE POSTMAN PROBLEM Permasalahan Chinese Postman Problem (CPP) merupakan permasalahan dalam pencarian rute terpendek dengan biaya minimum dan dalam kondisi setiap jalan harus dilewati paling tidak satu kali. Permasalahan tersebut dapat dinyatakan sebagai masalah menemukan sirkuit Euler yaitu rute yang melewati tiap sisinya tepat satu kali pada suatu graf Euler. Masalah CPP pertama kali dikemukakan oleh Meigu Guan atau Kwan Meiko, seorang pakar matematika dari universitas Shangtun, Cina. Tak heran jika permasalahan ini dinamakan Chinese Postman Problem karena memang berasal dari Cina. CPP memiliki banyak jenis yaitu UCPP (undirected CPP) / CPP yang tidak berarah, DCPP (directed CPP) / CPP yang berarah, WPP (Windy Postman Problem), MCPP (mixed CPP)/ CPP dengan graf campuran, dan HPP (hierarchical CPP). Kasus Mixed Chinese Postman Problem melibatkan graf campuran yang memiliki sisi berarah dan sisi tidak berarah. Gambar 30 merupakan contoh graf untuk Mixed Chinese Postman Problem. MCPP dapat diselesaikan dengan beberapa metode heuristik (Yaoyuenyong et al. 2002), salah satunya ialah metode balans-genap.
Gambar 30 Graf Euler kasus Mixed CPP.
3.1 Pencarian Solusi MCPP Metode Balans-Genap
dengan
Metode balans-genap merupakan salah satu metode heuristik yang dikembangkan oleh Christofides, yaitu metode mixed2 (Yaoyuenyong et al. 2002). Berikut langkahlangkah metode balans-genap.
Langkah 1. INOUTDEGREE. Tujuan : membuat seluruh verteks pada graf menjadi balans yakni + = . Input : = ( , ), dengan adalah himpunan sisi tidak berarah dan himpunan sisi berarah. Output : 2 = ( , ) dan himpunan . ialah himpunan sisi berarah dan sisi tidak berarah asli maupun tambahan. ialah himpunan sisi tidak berarah. ialah himpunan sisi berarah dan tidak berarah tambahan. (a) Dikonstruksi subgraf dari , yaitu = , dengan mengabaikan sisi tak berarah dari . Pada graf , dihitung + = , . (b) Dari graf dikonstruksi graf baru 1 = ( , 1 2 ), dengan 1 himpunan sisi berarah yang diperoleh dari sisi-sisi tak berarah di dan 2 diperoleh dari sisi berarah di . Langkah-langkah pembentukan graf 1 adalah sebagai berikut : 1. Untuk setiap sisi tidak berarah { , } pada , dibentuk 4 sisi berarah di 1 yaitu : i. sebuah sisi berarah ( , ) dengan biaya dan kapasitas takhingga, ii.sebuah sisi berarah ( , ) dengan biaya dan kapasitas takhingga, iii.sebuah sisi berarah ( , ) dengan biaya nol dan kapasitas 1, iv.sebuah sisi berarah ( , ) dengan biaya nol dan kapasitas 1. Empat jenis sisi berarah ini merupakan anggota himpunan sisi berarah 1 . 2. Untuk sembarang sisi berarah ( , ) pada , dibentuk sebuah sisi berarah yang sama ( , ) pada 1 dengan biaya sebesar dan kapasitas takhingga. Sisi berarah jenis ini merupakan anggota himpunan sisi berarah 2 . 3. Ditentukan solusi permasalahan minimum cost flow pada 1 dengan diperoleh dari langkah (a). Misalkan , , , , dan berturut-turut merupakan banyaknya flow pada sisi berarah , , ( , ), ( , ) , ( , ) , dan ( , ). Formulasi matematika masalah minimum cost flow adalah sebagai berikut :
12
Minimumkan + (, )
( ,)
1
2
terhadap ( |( , )
1
|( , )
2
+
)+ = ( )
|( , )
2
1 dan 1 , , , , dan dengan = {1,2,3,
0 , }.
(c) Dibentuk graf baru 2 = ( , ) dan sebuah himpunan dengan tahapantahapan sebagai berikut: 1. Inisialisasi = , = , dan = . 2. Jika + = 1, masukkan sebanyak sisi berarah ( , ) ke dalam himpunan dan masukkan sebanyak sisi berarah ( , ) ke dalam himpunan . Selainnya, masukkan sisi tidak berarah { , } ke dalam . 3. Sebanyak sisi berarah ( , ) dan sisi berarah ( , ) dimasukkan ke dalam himpunan dan . 4. Sebanyak sisi berarah ( , ) dimasukkan ke dalam himpunan dan . Langkah 2. LARGECYCLE. Tujuan : membuat seluruh verteks pada graf 2 menjadi verteks yang berderajat genap. Input : 2 = ( , ) Output : =( , 2) (a) Jika ada verteks berderajat ganjil pada 2 , proses dilanjutkan ke langkah (b). Selain itu proses dilanjutkan ke langkah (f) dan = 2. (b) Dibentuk suatu graf lengkap 3 dengan jarak/bobot antarverteks diperoleh dari panjang path terpendek antara kedua verteks tersebut pada graf 4 = , (bukan graf 1 ). (c) Dicari matching yang perfect dan berbobot minimum pada graf 3 dan ditentukan yang merupakan solusi berupa himpunan sisi tidak berarah yang diperoleh dari permasalahan matching tersebut. (d) 2 = (e) Graf merupakan solusi MCPP. (Yaoyuenyong et al. 2002)
Graf =( , 2 ) merupakan graf solusi MCPP. Karena graf balans dan genap, maka sesuai dengan Teorema 1, graf tersebut memiliki sirkuit Euler. Dalam karya ilmiah ini, untuk menentukan sirkuit Euler digunakan algoritme van Aardenne-Ehrenfest & de-Bruijn. Sebelumnya graf yang masih berupa graf campuran harus diubah terlebih dahulu menjadi graf berarah atau digraf = ( , ). Penentuan arah pada setiap sisi { , } dilakukan sedemikian rupa sehingga digraf yang baru tetap merupakan digraf yang balans. Contoh pengubahan menjadi digraf.
graf
campuran
: 8 16
6
13
5
14
7
15
7 11
12
17 9
4
5
6
8
10
1
18 4
19
2 1
3
3
2
Gambar 31 Graf campuran. Graf campuran pada Gambar 31 merupakan graf yang genap dan balans. Untuk menentukan arah pada dua sisi, misalkan {4,3}, maka satu sisi diubah menjadi sisi berarah (3,4) dan satu sisi lainnya menjadi sisi berarah (4,3) seperti terlihat pada Gambar 32 berikut. : 5
12 5
9
4
1
19 4
3
1
2
Gambar 32 Subgraf dari Gambar 31.
13
Begitu seterusnya untuk sisi-sisi lain yang masih belum berarah.
Pada Gambar 33 diberikan skema tahapan penyelesaian MCPP.
Graf campuran berbobot =( , )
tidak
Konstruksi graf = ( , ) dan hitung = + ()
Balans
I N O U T D E G R E E
Konstruksi graf 1 dengan mengubah edge menjadi 4 macam sisi berarah
ya Minimum Cost Flow Diperoleh
dan
Graf baru 2 = , adalah graf balans
Genap
Algoritme van AardenneEhrenfest & de Bruijn
ya
tidak L A R G E C Y C L E
Penentuan verteks berderajat ganjil pada graf 2 = ( , )
Pengubahan sisi tak berarah menjadi sisi berarah
Konstruksi graf lengkap 3 dari verteks berderajat ganjil di 2
=( ,
Graf genap
Diperoleh sirkuit Euler
2)
Algoritme Dijkstra Penentuan bobot sisi-sisi pada graf
2
=
+
3
Diperoleh Penentuan matching yang perfect berbobot minimum di
3
Gambar 33 Skema penyelesaian masalah MCPP.
IV APLIKASI PERMASALAHAN Listrik merupakan kebutuhan yang sangat penting, termasuk bagi warga Bogor. Perumahan, perkantoran, pabrik-pabrik bahkan tempat umum hampir selalu menggunakan fasilitas ini setiap harinya. Pemerintah daerah telah menyuplai pasokan listrik ke setiap kawasan Bogor. Di setiap kawasan itu terdapat satu gardu induk dengan banyak tiang pancang listrik bertegangan tinggi.
Dalam pemasangan instalasi listrik, PLN selaku pihak terkait harus melalui setiap ruas jalan. Kemudian PLN harus menguhubungkan kabel-kabel ke tiang pancang listrik yang sudah tersedia di pertigaan atau perempatan jalan. Maka dari itu, PLN harus merumuskan bagaimana cara menentukan jalur tependek dalam pemasangan instalasi listrik yang sesuai dengan posisi tiang pancang. Pada karya ilmiah ini akan dibahas rute pemasangan instalasi listrik di daerah Bogor Selatan.
7
6 5
1
8
4
Keterangan Tiang pancang listrik
Gardu induk
3 8
2 3 8
Gambar 34 Peta lokasi pemasangan instalasi listrik di Bogor Selatan. (www.googlemaps.co.id) 4.1 Permasalahan Listrik
Pemasangan
Instalasi
Sketsa pada Gambar 34 merupakan peta dari kondisi letak gardu induk dan tiang pancang listrik bertegangan tinggi. Jalan utama adalah jalan yang diberi nama, sedangkan yang tidak ada namanya merupakan jalan pendek atau blok. Lokasi tiang diperlihatkan dengan gambar “bulat”.
Pada Gambar 35, bobot pada setiap sisi { , } atau sisi berarah ( , ) merupakan jarak dari verteks ke verteks . Jarak diperoleh dari perkiraan dan pembulatan jarak sebenarnya dengan satuan kilometer. Model tersebut dapat dibuat menjadi graf sebagai berikut.
15
:
Gintung dan berakhir pada tempat yang sama. v. Besarnya daya listrik tidak diperhitungkan.
5 1
5
4
6
2
7
4
8
4
12 2
4
2
1
6
6 3 3
8
5
2
Gambar 35 Graf kasus Bogor Selatan. Tabel 2 Penjelasan setiap verteks pada graf kasus Bogor Selatan Verteks 1
2
3 4
5 6
7
8
4.2 Penyelesaian dengan Metode BalansGenap
Keterangan Lokasi tiang di pertigaan jalan Gang Aut dan jalan Surya Kencana Lokasi tiang di perempatan jalan Padjajaran, jalan Siliwangi, dan jalan Lawang Gintung Tempat awal dan akhir dalam pemasangan jaringan listrik Lokasi tiang di pertigaan jalan Pahlawan, jalan Dreded, dan jalan Gang Aut Lokasi tiang di pertigaan jalan Pulo Empang dan jalan Pahlawan Lokasi tiang di pertigaan jalan Pulo Empang dan jalan Surya Kencana Lokasi tiang di pertigaan jalan Padjajaran dan jalan Baranang Siang Lokasi tiang di PAKUAN
Asumsi yang digunakan dalam permasalahan ini sebagai berikut: i. Blok atau jalan pendek digabung dengan jalan utama menjadi satu jalan. ii. Setiap jalan harus dilewati agar warga di sekitar jalan tersebut mendapatkan pasokan listrik. iii. Jalan yang berupa edge/sisi merupakan jalan dengan dua jalur yang tidak dipisahkan dengan batas jalan (contohnya pada jalan Pahlawan), sedangkan jalan yang berupa arc/sisi berarah merupakan jalan dengan satu jalur atau dipisahkan dengan batas jalan. iv. Pemasangan instalasi listrik dimulai pada gardu induk di pertigaan jalan Lawang
Diberikan graf =( , ) dengan = {{2,8}, {3,4}, {3,5}, {4,5}, {5,6}, {5,7}, {7,8}} dan ={(1,2), (1,4), (2,3), (2,7), (6,1), (6,7), (7,2), (8,1)} seperti pada Gambar 35. Langkah 1, INOUTDEGREE. (a) Graf = , dari graf pada Gambar 35 ialah: : 6
2
5
7
4
8
2
4
2
1
8
6 3
3
Gambar 36 Graf Dari
Gambar +
1 2 3 4
2 2 1 1
36, ialah : 2=0 2=0 0=1 0=1
2
= ( , ). diperoleh 5 6 (7) 8
0 0 2 0
= 0=0 2= 2 1=1 1= 1
(b) Dibentuk graf baru 1 dari graf dengan cara sebagai berikut : 1. Sisi tidak berarah pada Gambar 35 ialah {2,8}, {3,4}, {3,5}, {4,5}, {5,6}, {5,7}, dan {7,8}. Dari setiap sisi tersebut, dibentuk 4 sisi berarah pada graf 1 . 2. Sisi berarah dari graf pada Gambar 35 ialah (1,2), (1,4), (2,3), (2,7), (6,1), (6,7), (7,2), dan (8,1). Setiap sisi berarah ini digambarkan kembali di 1 . Dari Langkah 1 dan 2 diperoleh graf 1 sebagai berikut:
16
:
5
5
7
1
6
2
4
4 4
4
2
8
8
2
1
12
6
6
5
2
3
3
8
Gambar 37 Graf
1.
Keterangan : : sisi berarah ( , ) dan ( , ) dengan biaya dan kapasitas takhingga, : sisi berarah ( , ) dan ( , ) dengan biaya nol dan kapasitas 1, : sisi berarah ( , ) dengan biaya dan kapasitas takhingga.
i. ii. iii.
3. Formulasi masalah minimum cost flow ialah sebagai berikut: Minimumkan 5
28
10 5 3
+5
53
57
+4
+5 +8
23
54
27
34
+4
+4
75
+4
+6
43
+ 10
35
+
56
+
+
+4
87
+6
45
78 61
+4
67
65
+8
+
14
+
28 12
(
+
34 35
(
43 45
(
53 54
12 ) 82
61
+
72 43
+
+
54 )) 35
+
57
75 ))
65
56
+
65
56
+
28
81
=0
82
+
12
+2
14
72
+2
81
23
+
+
45 ) +
34 23 43 14 53 56
43
+(
27
34
65
+(
53
45
54 +
+
54 56
45 65
75
87 )) + 78
82
+
28
+ +(
57
72
+
67
87
)) +
=0
78 81
61
+
78 27
+(
82
+ +
67 87
28
28
1,
82
1,
34
1,
43
1,
35
1,
53
1,
45
1,
54
1,
56
1,
65
1,
57
1,
75
1,
78
1,
87
1
34
0,
43
0,
45
0,
54
0,
56
0,
65
0,
78
0,
87
0,
82
0,
28
0,
35
0,
53
0,
57
0,
75
0,
61
0,
67
0,
72
0,
27
0,
12
0,
14
0,
= +
=1
= 1
+
35
=1 35
+
57
87
+
=1 +(
75
(
=0
53 )) 34
75
78
dengan kendala (
57
( +6
82
(
+
2
17
0,
23 34
0,
81
0,
45
0,
57
0,
43
0,
28
0,
54
0,
75
0,
35
0,
2:
0,
82 53
5
0,
56
0,
65
0,
78
0,
87
0
2. Hasil yang diperoleh dengan program LINGO 8.0 di Lampiran 2 ialah: 35 = 1 & 53 = 0 35 + 53 = 1 = 1 & = 0 + 45 54 45 54 = 1 56 = 1 & 65 = 0 65 + 56 = 1 78 = 1 & 87 = 0 78 + 87 = 1
2
7
4 4
Dengan program LINGO 8.0 (Lampiran 2), diperoleh 56 = 1 56 = 1 = 1 35 45 = 1 = 1 78 (Variabel lain bernilai nol) (c) Akan dibentuk sebuah graf baru ). 2 = ( , 1. Inisialisasi = , = , dan = . = { 1,2 , 1,4 , 2,3 , 2,7 , 6,1 , 6,7 , 7,2 , (8,1)}
6
1
5
4 2
4
8 2
1
6
6 3
5 2
3
Gambar 38 Graf output
8
2
=( ,
).
Langkah 2. LARGECYCLE. (a) Verteks yang berderajat ganjil pada graf 2 adalah {2,3,4,5,7,8}. (b) Dibentuk suatu graf lengkap 3 dengan himpunan verteksnya adalah verteksverteks berderajat ganjil pada Langkah (a). 3:
2
Sisi yang ditambahkan ke dalam himpunan berturut-turut ialah sisi berarah 3,5 , 4,5 , 5,6 , dan (7,8), sehingga himpunan menjadi = { 1,2 , 1,4 , 2,3 , 2,7 , 3,5 , 4,5 , 5,6 , 6,1 , 6,7 , 7,2 , 7,8 , (8,1)}
3
8
4
7
5
Karena 43
28
1, dan
+ 57
82
1,
+
75
34 + 1, maka
ke dalam himpunan ditambahkan sisi tidak berarah 2,8 , 3,4 , {5,7}, sehingga = { 2,8 , 3,4 , 5,7 }. 3. Karena 56 = 1, maka ditambahkan satu sisi berarah 5,6 ke dalam himpunan dan , sehingga = { 1,2 , 1,4 , 2,3 , 2,7 , 3,5 , 4,5 , 5,6 , 5,6 , 6,1 , 6,7 , 7,2 , 7,8 , (8,1)}, = { 5,6 }. 4. Dari hasil yang diperoleh LINGO 8.0 (Lampiran 2), tidak ada sisi ( , ) 2 yang ditambahkan ke dalam himpunan dan , sehingga diperoleh graf = ( , ) seperti pada gambar 2 berikut:
Gambar 39 Graf lengkap. (c)
Pencarian path terpendek pada graf 3 (detail penghitungan dapat dilihat di Lampiran 3).
(d) Dari graf 3 diperoleh bobot dari sisi { , } dengan , ( 3 ), sebagai berikut.
18
Tabel 3 Bobot ( ) setiap sisi { , }, dengan , ( 3) Sisi { , } Bobot ( ) 4 {4,5} 4 {7,8} 5 {2,8} 5 {5,7} 6 {3,4} 9 {4,7} 9 {5,8} 9 {2,7} 10 {3,5} 13 {4,8} 14 {2,5} 15 {3,7} 18 {2,4} 19 {3,8} 24 {2,3}
: 5 6
1
5
2
7
4 4
4 2
4
8
6
6 3
8
2
1
5 2
3
=( ,
Gambar 40 Graf Output
2 ).
Hasil pengubahan edge menjadi arc dapat dilihat pada Gambar 41. :
Bobot pada Tabel 3 diperoleh dari pencarian path terpendek (Lampiran 3) dari graf pada Gambar 39. Dari Tabel 3, dipilih sisi yang membentuk matching yang perfect dengan total bobot minimum. Karena banyaknya verteks pada 3 adalah 6, maka matching yang perfect berisi 3 sisi. Dari Lampiran 4 diperoleh matching yang perfect dan berbobot minimum ialah { 2,8 , 3,4 , 5,7 } dengan total bobot 16, sehingga diperoleh sebagai berikut
8 16
2
(f)
2
=
+
= { 2,8 . 3,4 , 4,3 , 5,7 , 7,5 , 8,2 } =( , diberikan pada 2) Gambar 40. Graf sudah merupakan graf yang balans dan genap, sehingga mempunyai sirkuit Euler.
Untuk mencari sirkuit Euler pada graf , digunakan algoritme van Aardenne-Ehrenfestde Bruijn. Sebelumnya, edge atau sisi pada Gambar 40 harus diubah terlebih dahulu menjadi arc atau sisi berarah sedemikian sehingga digrafnya tetap merupakan digraf yang balans. Sisi-sisi pada Gambar 40, yaitu sisi 3,4 , 5,7 , dan 2,8 , berturut-turut diubah menjadi (3,4), (4,3), (5,7), (7,5), (2,8), dan (8,2).
14
7
15
7 11
12
17 9
4
6
8
10
1
5
18 4
19
2 1
3
3
2
Gambar 41 Graf berarah.
= { 2,8 , 3,4 , 5,7 }. (e)
6
13
5
Pencarian sirkuit Euler pada Gambar 41 dilakukan dengan algoritme van AardenneEhrenfest-de Bruijn. Spanning arborescence dari graf berawal dari 3 adalah sebagai berikut : 1
5
6
2 7
4
4 8
1
4
12 6
6 2 3
Gambar 42 Spanning arborescence digraf kasus Bogor Selatan.
19
Hasil dari pelabelan dengan algoritme van Aardenne-Ehrenfest-de Bruijn untuk kasus Bogor Selatan dapat dilihat pada Gambar 43.
digraf dengan verteks awal di (3) adalah 3 4 5 6 1 4 3 5 7 2 8 1 2 7 5 6 7 8 2 3 dengan total jarak 88.
Dari Gambar 43 dapat ditarik kesimpulan bahwa sirkuit Euler yang bisa dibentuk dari : L2
L2
L3 L1
5
7 6
L2
L1 L1
L1
L2
L3
L2
4
L1
L1
1
8
L1 L2
L2
3
L3
2
L2
L1
Gambar 43 Digraf MCPP yang sudah dilabeli.
V SIMPULAN DAN SARAN 5.1 Simpulan
5.2 Saran
CPP tidak hanya dapat diterapkan pada graf berarah ataupun tidak berarah. Dalam karya ilmiah ini CPP diterapkan pada graf campuran atau graf mixed (MCPP). Dalam karya ilmiah ini, untuk memperoleh solusi dari graf campuran, digunakan metode heuristik balans-genap. Kemudian dalam penentuan sirkuit Euler digunakan algoritme van Aardenne-Ehrenfest-de Bruijn.
Penerapan dalam karya ilmiah ini masih sangat sederhana, hal ini dapat dilihat dari banyaknya verteks. Maka dari itu, permasalahan pemasangan instalasi listrik dalam karya ilmiah ini masih dapat diselesaikan secara manual. Bagi yang ingin melanjutkan karya ilmiah ini, disarankan mencoba metode lain atau membuat program guna menyelesaikan permasalahan yang lebih kompleks.
Penerapan masalah MCPP pada karya ilmiah ini adalah dalam kasus pemasangan instalasi listrik di daerah Bogor Selatan. Dengan metode balans-genap ditemukan rute perjalanan terpendek yang melewati setiap jalan minimal satu kali.
22
Lampiran 1 Penentuan jarak terpendek dengan menggunakan algoritme Dijkstra
:
5 6
1
5
4
2
7
4
8
4
12 2
4
2
1
6
8
6 2
3
3
5
Gambar 44 Graf MCPP.
Tabel 4 Penentuan path terpendek dimulai dari verteks
0
=3
= -) -)
-) (3,3)
0
(9,2) (8,4)
( , ) menyatakan : 1
= (
0,
-) (6,3)
-) (12,3)
-) -)
-) -)
-) -)
3 2
(6,3)
(12,3) (10,4) (10,4) (10,4)
-) -) (12,1) (12,1)
(11,2) (11,2) (11,2) (11,2)
(8,2) (8,2) (8,2)
4 1 8 5
(11,5)
(11,2) (11,2)
) dan
=
( )
6
5
7
4 4
1
2
8
6
8
5 3
2
3
Gambar 45 Solusi path terpendek dengan verteks awal
0
= 3.
6 7
23
Lampiran 2 Program LINGO 8.0 MODEL : ! Objective function; MIN = 6*x34+6*x43+4*x45+4*x54+x56+x65 +4*x78+4*x87+5*x82+5*x28+10*x35 +10*x53+5*x57+5*x75+4*x61+2*x67 +8*x72+8*x27+6*x12+2*x14+3*x23+ 2*x81; !subject to; (x14+x12)-(x61+x81)=0; (x28-x82+x28a-x82a)+(x23+x27)(x12+x72)=0; ((x34-x43+x34a-x43a)+(x35-x53+ x35a-x53a))-x23=1; ((x43-x34+x43a-x34a)+(x45-x54+ x45a-x54a))-x14=1; ((x53-x35+x53a-x35a)+(x54-x45+ x54a-x45a)+(x56-x65+x56ax65a)+(x57-x75+x57a-x75a))=0; (x65-x56+x65a-x56a)+ (x61+x67)=-2; ((x75-x57+x75a-x57a)+(x78-x87+ x78a-x87a))+x72-(x67+x27)=1; ((x87-x78+x87a-x78a)+(x82-x28+ x82a-x28a))+x81=-1; x28a<=1;x82a<=1; x34a<=1;x43a<=1; x35a<=1;x53a<=1; x45a<=1;x54a<=1; x56a<=1;x65a<=1; x57a<=1;x75a<=1; x78a<=1;x87a<=1; END Global optimal solution found at iteration: 0 Objective value: 1.000000
Var X34 X45 X56 X78 X82 X35 X57 X61 X67 X72
Value 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Reduced Cost 6.000000 4.000000 0.000000 4.000000 5.000000 10.000000 5.000000 3.000000 3.000000 8.000000
X27 X12 X14 X23 X81 X28 X28A X82A X43 X34A X43A X53 X35A X53A X54 X45A X54A X65 X56A X65A X75 X57A X75A X87 X78A X87A
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000
8.000000 8.000000 4.000000 3.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Row Slack or Surplus Dual Price 1 1.000000 -1.000000 2 0.000000 2.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 1.000000 8 0.000000 0.000000 9 0.000000 0.000000 10 1.000000 0.000000 11 1.000000 0.000000 12 1.000000 0.000000 13 1.000000 0.000000 14 0.000000 0.000000 15 1.000000 0.000000 16 0.000000 0.000000 17 1.000000 0.000000 18 0.000000 1.000000 19 1.000000 0.000000 20 1.000000 0.000000 21 1.000000 0.000000 22 0.000000 0.000000 23 1.000000 0.000000
24
Keterangan : X28A = X43A = X45A = X65A = X75A =
28 ,
X82A = X35A = 45 , X54A = 65 , X28A = 75 , X78A = 43 ,
82 ,
34 ,
35 ,
X34A = X53A = 54 , X56A = 28 , X57A = 78 , X87A =
53 , 56 , 57 , 87 .
Lampiran 3 Penentuan jarak terpendek dengan menggunakan algoritme Dijkstra 3:
5 6
1
5
7
4
4 8
4
12
1
6 5 2
3
=
Gambar 46 Graf
,
.
Tabel 5 Penentuan path terpendek dimulai dari verteks
0
=2
= 0
-) -) -) -) (26,5) (26,5)
-) -) -) -)
-) -) -) (14,7)
(18,5) (18,5)
(24,4) ( , ) menyatakan = (
-) -) -) -)
-) -) (9,8)
-) (5,2)
2 8 7 5
(15,5)
6 4 3
0,
) dan
=
( )
Tabel 6 Penentuan path terpendek dimulai dari verteks
0
=3
= -)
0
-)
-)
-)
-)
-)
3
-) -) -) -) -) (24,8) ( , ) menyatakan
(6,3)
(12,3) (10,4)
-) -) (11,5)
-) -) (15,5) (15,5)
-) -) -) -) (19,7)
4 5 6 7 8 2
= (
0,
) dan
=
( )
25
Tabel 7 Penentuan path terpendek dimulai dari verteks
0
=4
= -) -) -) -)
-) (6,4) (6,4) (6,4)
0
-) (4,4)
-) -) (5,5)
-) -) (18,8) ( , ) menyatakan
-) -) (9,5) (9,5)
-) -) -) -)
4 5 6 3
(9,5)
-) (13,7)
7 8 2
= (
0,
) dan
=
( )
Tabel 8 Penentuan path terpendek dimulai dari verteks
0
=5
= -) -)
-) (12,5)
-) (4,4)
-) -) -) (14,8)
(12,4) (10,4) (10,4) (10,4)
(4,4)
(14,8) ( , ) menyatakan
0
-) (1,5)
-) (5,5)
-) -)
5 6
(5,5) (5,5)
-) -) (9,7)
4 7 8 3 2
= (
0 , ) dan
=
( )
Tabel 9 Penentuan path terpendek dimulai dari verteks
0
=7 =
-)
-)
-)
-) -) (5,7) -) -) (5,7) (17,5) (9,5) (17,5) (9,5) (15,4) (15,4) ( , ) menyatakan = ( 0 , ) dan =
-) -) (6,5)
-) (9,8) (9,8) (9,8) (9,8)
-)
-)
0
( )
-)
7
(4,7)
8 5 6 4 2 3
26
Lampiran 4 Penentuan Matching yang perfect dengan bobot minimum Tabel 10 Bobot ( ) setiap sisi { , },dengan , ( ) Sisi { , } Bobot ( ) : 4 {4,5} 4 {7,8} 5 {2,8} 5 {5,7} 6 {3,4} 9 {4,7} 9 {5,8} 9 {2,7} 10 {3,5} 13 {4,8} 14 {2,5} 15 {3,7} 18 {2,4} 19 {3,8} 24 {2,3}
2 3
8
4
7
5
Gambar 47 Graf lengkap.
Dari Gambar 47 akan ditentukan matching yang perfect dengan total bobot minimum. Tabel 10 menunjukkan bobot sisi yang terdapat pada Gambar 47. Karena pada Gambar 47 hanya terdapat 6 verteks, maka matching perfect yang dapat dibentuk sebanyak 3 sisi adalah sebagai berikut.
: 24
:
2
3
8
2
8
3
6
7
4
: 5
3
4 4
2
8
13 4
7 5
5
14 15
4
5
7 5
(a) (b) (c) Pada Gambar (a) matching perfect yang dapat dibentuk adalah 1 ={{2,3},{4,5},{7,8}} dengan total bobot 32. Gambar (b) matching perfect yang dapat dibentuk adalah 2 ={{3,4},{5,7},{2,8}} dengan total bobot 16. Sedangkan pada Gambar (c), matching perfect yang dapat dibentuk adalah 3 ={{2,5},{3,7},{4,8}} dengan total bobot 42. : 24
:
2
3
8
2 3
:
2
5 8
13
3
15
8
14 6
4
7 5
5
4
7
4
5
4 4
7 5
(d) (e) (f) Pada Gambar (d) matching perfect yang dapat dibentuk adalah 4 ={{2,3},{4,8},{5,7}} dengan total bobot 42. Gambar (e) matching perfect yang dapat dibentuk adalah
27
5 ={{2,8},{3,7},{4,5}} dengan total bobot 24. Sedangkan pada Gambar (f), matching perfect yang dapat dibentuk adalah 6 ={{2,5},{3,4},{7,8}} dengan total bobot 24.
:
:
2
:
2
2
5 9
19 3
18
3
8
8
3
8
13
14
15
10 9 4
9
4
7 5
4
7
4
7
5
5
(g) (h) (i) Pada Gambar (g) matching perfect yang dapat dibentuk adalah 7 ={{2,5},{3,8},{4,7}} dengan total bobot 42. Gambar (h) matching perfect yang dapat dibentuk adalah 8 ={{2,7},{3,5},{4,8}} dengan total bobot 32. Sedangkan pada Gambar (i), matching perfect yang dapat dibentuk adalah 9 ={{2,4},{3,2},{5,8}} dengan total bobot 42. :
:
2
:
2
2
9
18 3
10
4
18
3
8
8
3
8
6
9 9
4
4
7 5
4
7
4
9 7
5
5
(j) (k) (l) Pada Gambar (j) matching perfect yang dapat dibentuk adalah 10 ={{2,4},{3,5},{7,8}} dengan total bobot 32. Gambar (k) matching perfect yang dapat dibentuk adalah 11 ={{2,7},{3,4},{5,8}} dengan total bobot 24. Sedangkan pada Gambar (l), matching perfect yang dapat dibentuk adalah 12 ={{2,3},{4,7},{5,8}} dengan total bobot 36. :
:
2
18
19
19
3
8
:
2
2
5
9
3
8
3
8
10 4
7 5
5
4
7
4
5
4
9 7 5
(m) (n) (o) Pada Gambar (m) matching perfect yang dapat dibentuk adalah 13 ={{2,4},{3,8},{5,7}} dengan total bobot 42. Gambar (n) matching perfect yang dapat dibentuk adalah 14 ={{2,7},{3,8},{4,5}} dengan total bobot 32. Sedangkan pada Gambar (o), matching perfect yang dapat dibentuk adalah 15 ={{2,8},{3,5},{4,7}} dengan total bobot 24. Jika dilihat dari Gambar (a) sampai dengan Gambar (o), maka sisi matching yang perfect dengan bobot minimum adalah 2 ={{3,4},{5,7},{2,8}} dengan total bobot 16.
