VISUALISASI GRAF DAN ALGORITMA-ALGORITMA DALAM TEORI GRAF MENGGUNAKAN BEBERAPA PAKET SOFTWARE

Prosiding Seminar Nasional Aplikasi Sains & Teknologi (SNAST)2014 Yogyakarta, 15 November 2014

ISSN: 1979-911X

VISUALISASI GRAF DAN ALGORITMA-ALGORITMA DALAM TEORI GRAF MENGGUNAKAN BEBERAPA PAKET SOFTWARE Yudi Setyawan1 Jurusan Matematika Fakultas Sains Terapan IST AKPRIND YOGYAKARTA e-mail :[email protected]

1

ABSTRACT Graph theory is a branch of mathematics frequently used to solve real problems because they can be understood, formulated and solved easier when stated as graph forms. The development of graph theory is done by scientist from diverse area along with their needs. As a result, there are new terminologies and concepts where they often use different terms for the same meaning and vice versa. Basically problems in graph theory relate to the existence of a certain property or extreem value of a graph. Graph properties are easier to study if it is drawn or visualized. To find extreem values of a graph, usually one makes use of a certain algorithm and both of them mostly are not easy to do. This research serves the use of softwares to visualize graphs and generate algorithms related to graph theory. Open source or shareware softwares such as Graph Magics, Gephi dan Graphviz are used. Research concludes that those softwares are very useful to visualize graphs and generate graph algorithms as well and noted that each of them has advantages and disadvantages. Graph Magics can be used to draw and edit graphs easily and it is equipped with various algorithms. Gephi is a suitable software to visualize big graphs fast and its results are nice and beatiful. Graphviz can be use to visualize various graphs, however the understanding of programming is required. Keywords: graph visualization and algorithm, Graph Magics, Gephi, Graphviz PENDAHULUAN Teori graf merupakan cabang ilmu yang relatif baru, karena baru mulai dikembangkan pada awal abad ke delapan belas. Namun demikian, perkembangan cabang ilmu ini sangat pesat. Hal ini disebabkan oleh manfaat teori graf yang sangat luas, dapat dikatakan bahwa semua cabang ilmu lain dapat memanfaatkannya. Bidang kedokteran dan biologi, teori graf dapat digunakan untuk menjelaskan pola kode genetika makhluk hidup (Seffens, W., 2002). Di bidang elektronika dan komputer, graf banyak sekali dimanfaatkan seperti untuk pengembangan jaringan berjalan (mobile adhoc networks-MANETs). Konsep-konsep graf seperti ketersambungan (connectivity), kesebandingan (scalability), penentuan jalur dan topologi (routing and topology) banyak dimanfaatkan untuk pengembangan jaringan mobile ad hoc yang ekonomis dan tangguh (M. A. Rajan et al., 2008 dan Shrinivas, S., G. et. al., 2010). Konsep tentang struktur pohon (tree) dalam graf sering digunakan dalam analisis data biologi dan arkeologi guna merepresentasikan pembagian satu spesies menjadi dua atau lebih spesies, atau pemecahan satu artefak menjadi beberapa artefak. Dalam bidang manajemen, masalah penjadwalan skala besar juga dapat diselesaikan secara lebih mudah dengan graf. Di lain pihak, teori graf berkembang melalui pendefinisian konsep-konsep baru yang diturunkan berdasarkan konsep-konsep yang sudah ada serta kebutuhan praktis sehingga keterkaitan antar konsep-konsep tersebut semakin kompleks dan muncullah teorema-teorema. Beberapa teorema mungkin dapat dibuktikan dengan cara sederhana, namun banyak juga teorema yang pembuktiannya memerlukan algoritma tertentu yang seringkali tidak mudah dipahami, apalagi oleh pengguna berlatar belakang matematika kurang kuat. Melalui visualisasi dengan software komputer, pemahaman konsep dan algoritma teori graf dapat menjadi lebih mudah. Mengingat pentingnya teori graf bagi bidang ilmu lain, maka sudah seharusnya pemahaman tentang konsep-konsep dan algoritma-algoritma dalam teori graf dibuat lebih mudah dan praktis. Masalah ini dapat diatasi dengan penyediaan software komputer atau paket program yang sesuai dengan kebutuhannya. Meskipun terdapat banyak software komputer yang bersifat umum seperti Matlab, Maple (Ebrahimi, M.A. et al., 2006), yang dapat digunakan untuk menyelesaikan berbagai permasalahan dalam teori graf, hal ini kurang praktis dan memerlukan biaya karena software tersebut C-259


ISSN: 1979-911X

bersifat proprietary. Oleh karena itu perlu dicari software berukuran kecil, bersifat open source atau shareware namun sesuai dengan kebutuhan. Beberapa software open source khusus untuk teori graf dapat ditemukan dengan mudah di internet seperti Graph Magics, Graphviz, Gephi, GraphTea, Graphalg, Gograph, Connectivity dan sebagainya, sedangkan software open source umum yang dapat digunakan adalah seperti Scilab dan Maxima. Beberapa software teori graf tersebut dapat dimanfaatkan untuk mempermudah pemahaman konsep-konsep teori graf, menggambarkan/memvisualisasikan sebuah graf, menentukan sifat-sifat graf, maupun melakukan algoritma-algoritma dalam teori graf. Berdasarkan alasan tersebut, dipilih beberapa software komputer yang cocok digunakan untuk membantu pemahaman konsep dan algoritma dalam teori graf dan selanjutnya dikaji pemanfaatannya untuk membantu menyelesaikan beberapa permasalahan dalam teori graf terutama yang berkaitan dengan visualisasi dan algoritma graf. Dengan demikian diharapkan penyampaian pemahaman konsep dan algoritma dalam teori graf dapat dilakukan dengan lebih mudah melalui pemberian contoh-contoh nyata. Selain itu, software tersebut dapat dimanfaatkan untuk membantu menyelesaian permasalahan nyata yang sering dihadapi sehingga dapat memberikan kontribusi nyata dalam pembelajaran dan penelitian teori graf serta lebih memperkenalkan software-software yang dapat digunakan dalam pembelajaran dan penelitian teori graf. PEMBAHASAN Graf terdiri atas himpunan simpul V dan himpunan sisi E dengan setiap sisi memiliki ujungujung yang berupa simpul. Graf dapat digunakan untuk merepresentasikan berbagai macam sistem nyata, dengan simpul menyatakan unsur dalam sistem tersebut dan unsur-unsur yang saling berhubungan digambarkan dengan adanya sisi yang menghubungkan unsur-unsur itu. Dalam sejarahnya, graf digunakan oleh Euler untuk memecahkan masalah jembatan Konigsberg. Masalah jembatan Konigsberg merupakan teka-teki yakni dari salah satu tempat tertentu apakah kita dapat berjalan dengan melalui ke tujuh jembatan itu masing-masing tepat satu kali.

Gambar 1. Jembatan Konigsberg Banyak orang sudah mencoba melakukannya dengan berbagai cara namun tidak ada yang berhasil. Hal ini menarik Leonard Euler untuk memecahkan masalah tersebut dengan menggunakan konsep yang sekarang dikenal sebagai teori graf. Jika setiap tempat diwakili oleh simpul dan setiap jembatan diwakili oleh sisi, maka masalah tersebut dapat digambarkan sebagai graf dengan empat simpul dan tujuh sisi seperti Gambar 2 berikut.

Gambar 2. Representasi masalah jembatan Konigsberg sebagai graf Dalam representasi graf dari masalah jembatan Konigsberg ternyata keempat simpul tersebut semuanya memiliki derajat ganjil. Dengan latar belakang matematika yang dimilikinya, Euler membuktikan bahwa kita tidak mungkin pergi dari suatu simpul tertentu dengan melalui ke tujuh sisi dari graf itu masing-masing tepat satu kali dan kembali ke simpul awal. Euler membuktikan bahwa ini dilakukan jika sebanyak-banyaknya ada dua simpul dengan derajat ganjil, yakni simpul awal dan simpul akhir. Dalam perkembangan teori graf, konsep ini dikenal dengan trail Euler (Eulerian trail). C-260


ISSN: 1979-911X

Sebagai cabang matematika terapan yang banyak digunakan untuk menyelesaikan masalah nyata dalam berbagai bidang, konsep-konsep dalam teori graf biasanya muncul sesuai dengan kebutuhan dan kenyataan yang terjadi pada bidang tersebut. Seiring perkembangan kebutuhan masing-masing bidang ilmu, dikembangkan konsep-konsep atau istilah baru. Hal pertama yang perlu diperhatikan adalah masalah pendefinisian dari konsep-konsep tersebut karena definisi yang tepat dapat menjelaskan secara lebih dalam tentang apa yang dimaksudkannya. Hal ini perlu ditekankan karena di lapangan sering ditemukan dua istilah berbeda untuk menyatakan satu konsep. Istilah yang paling pokok dalam graf yakni vertex dan edge. Beberapa padanan atau terjemahan yang sering digunakan untuk vertex adalah node yang biasa diterjemahkan menjadi simpul, titik, atau tijung. Sedangkan edge sering disebut dengan arc dan diterjemahkan sebagai sisi, tepi, atau garis. Graf G = G(V,E) = G(V(G),E(G)) adalah sistem yang terdiri atas himpunan simpul V = V(G) dan himpunan sisi E=E(G), dengan E⊆VxV. Graf dibedakan menjadi graf tak berarah dan graf berarah. Dalam graf tak berarah, sisi e=(vi,vj) dapat ditulis secara singkat dengan e=vivj saja. Dalam pembahasan ini seluruh graf diasumsikan tak berarah, kecuali apabila dinyatakan khusus. Dua buah simpul vi dan vj dikatakan adjacent (bertetangga) jika vivj=e∈E. Dalam hal ini dikatakan bahwa e berinsiden dengan vi dan vj. Untuk suatu v∈V, himpunan tetangga v didefinisikan dengan N(v)={w∈V:vw∈E} dan derajat v didefinisikan dengan d(v)=|N(v)|. Maksimum dan minimum derajat simpul-simpul dalam G berturut-turut disimbulkan dengan Δ(G) dan δ(G). Graf G disebut regular dengan derajat r atau dikatakan r-regular jika Δ(G)=δ(G)=r. Graf H disebut subgraf dari graf G jika V(H) ⊆V(G) dan E(H) ⊆E(G). Graf F=F(V2,E2) disebut induced subgraph (subgraf yang dibangkitkan oleh) G=G(V,E) jika V2⊆V dan memenuhi: ∀v1,v2∈V2, v1v2∈E⇒ v1v2∈E2. Dalam suatu graf G=G(V,E) selalu berlaku handshaking lemma yakni∑ 2| |. Akibatnya jumlah semua derajat dari simpul-simpulnya selalu genap. Jadi banyak simpul berderajat ganjil juga selalu genap. Lebih lanjut lagi, jika G regular dan |V|=n, maka |E|=nr/2. Graf G disebut lengkap jika setiap simpul selalu adjacent dengan simpul-simpul lainnya, sehingga jumlah sisi dari graf lengkap berukuran n adalah n(n-1)/2. Graf G=G(V,E) disebut bipartit jika V dapat dipartisi menjadi dua himpunan tak kosong dan saling asing V1 dan V2 sedemikian hingga setiap sisi e dari G dapat dinyatakan dengan e=v1v2 dengan v1∈V1 dan v2∈V2. Dalam hal ini V1 dan V2 disebut partisi dari V. Jika dalam graf bipartit G setiap simpul dalam suatu partisi adjacent dengan setiap simpul dalam partisi lainnya maka G disebut bipartit lengkap dan disimbulkan dengan Km,n, dimana m dan n berturut-turut adalah banyak anggota dari V1 dan V2. Jika sisi-sisi dari graf diberikan bobot maka disebut graf terbobot. Pada prakteknya bobot dapat mewakili jarak atau waktu tempuh dari kedua simpul. Graf G(V,E), walk atau langkah merupakan pasangan berurutan yang berselang-seling antara simpul-simpul v di V dan sisi-sisi e di E, yang dimulai dan diakhiri dengan simpul, dimana setiap sisi berinsiden dengan simpul-simpul di depan dan dibelakangnya dan simpul serta sisi boleh muncul lebih dari satu kali. Apabila dalam suatu walk tidak ada sisi yang muncul lebih dari dua kali, maka walk itu disebut trail atau jejak. Suatu trail yang simpul awalnya sama dengan simpul akhir disebut sirkuit atau tour atau kalang. Suatu trail yang memiliki semua simpul berbeda disebut path atau lintasan. Suatu kalang yang semua simpulnya berbeda kecuali simpul awal dan simpul akhirnya disebut cycle atau daur. Suatu trail yang melewati seluruh sisi dalam graf G tepat satu kali disebut trail Euler. Lintasan Hamilton adalah lintasan dalam graf G yang melalui semua simpul dari G. Menentukan eksistensi dari trail Euler dan lintasan Hamilton dari graf G merupakan suatu hal yang menarik. Dalam graf yang sederhana (tidak berarah, tanpa loop dan tidak multiple edges), hanya ada satu sisi yang menghubungkan dua simpul yang berinsiden. Karena itu, untuk menyatakan suatu langkah, trail, sirkuit, lintasan, atau daur, hanya perlu dituliskan simpul-simpul yang dilewatinya secara terurut. Graf G dikatakan tersambung (connected) jika untuk setiap pasang simpul v dan w dari V(G) terdapat lintasan yang ujung-ujungnya adalah simpul v dan w. Jika tidak demikian, maka G disebut tak tersambung. Suatu graf tak tersambung terdiri dari beberapa graf tersambung maksimal yang disebut komponen. Suatu graf tersambung dan tidak memiliki daur disebut pohon (tree). Berikut ini adalah contoh dari Walk, trail, sirkuit, path, dan cycle dalam graf G. Misal G adalah graf seperti di bawah ini:

C-261


ISSN: 1979-911X

Gambar 3. Graf G terhubung dengan sembilan simpul Berdasarkan graf G di atas, maka himpunan terurut simpul-simpul (v1,v2,v4,v5,v2, v5) adalah suatu walk. Himpunan terurut simpul-simpul (v1,v2,v4,v5,v2,v3) adalah suatu trail. Himpunan terurut simpul-simpul (v1,v2,v4,v5,v2,v3,v1) adalah suatu kalang. Himpunan terurut simpul-simpul (v1,v2,v4,v5,v3) adalah suatu lintasan. Himpunan terurut simpul-simpul (v1,v2,v4,v5,v3,v2) adalah suatu daur. Himpunan terurut simpul-simpul (v7,v4,v9,v7,v5,v4,v2,v5,v3,v2,v1,v3,v6,v5,v8,v7,v6,v8,v9) adalah suatu trail Euler. Lintasan (v1,v2,v4,v9,v7,v8,v6,v5,v3) adalah suatu lintasan Hamilton. Subgraf H dari graf G disebut subgraf penjangkau atau perentang (spanning subgraph) jika H memuat semua simpul dari G. Tree atau pohon T disebut pohon penjangkau atau perentang (spanning tree) dari graf terhubung G jika T suatu subgraf perentang dari G. Jika G graf terhubung yang terbobot, yakni graf dimana sisi-sisinya diberikan bobot tertentu, maka dapat dicari pohon penjangkau yang memiliki total bobot minimum (minimum spanning tree).

Gambar 4. Graf penjangkau dari G

Gambar 5. Pohon penjangkau dari G

Pemanfaatan teori graf di dunia nyata banyak digunakan untuk menyelesaikan permasalahan eksistensi, non eksistensi dan ekstrematilas dari yang sederhana sampai yang kompleks dan bersifat terbuka. Beberapa permasalahan yang berkaitan dengan eksistensi misalnya masalah eksistensi trail Euler dan daur Hamilton, pelabelan simpul atau sisi dengan sifat tertentu, dekomposisi dan packing suatu graf tertentu atas daur dan pohon. Masalah ekstremalitas dalam teori graf banyak menarik minat para praktisi karena biasanya berkaitan dengan persoalan optimasi dari permasalahan nyata, misalnya tentang bilangan warna pada bidang, maksimum ukuran graf lengkap dengan bilangan warna p, matching (penjodohan) dan himpunan independen maksimum dari suatu graf dan sebagainya. Banyak masalah open problems terkait eksistensi dan ektremalitas dalam teori graf. Dengan demikian penelitian dalam teori graf terus dikembangkan dengan berbagai cara baik analitis maupun numeris dengan bantuan komputer melalui algoritma yang diciptakan. Dalam teori graf dikenal banyak algoritma untuk menjawab permasalahan terkait ekstremalitas atau untuk menunjukkan eksistensi suatu sifat. Beberapa algoritma yang ditemui dalam teori graf misalnya algoritma Brent (Brent, R.P., 1980) dan Floyd (Knuth, D., E., 1969), untuk menentukan adanya daur dalam graf. Algoritma untuk penjodohan maksimum misalnya algoritma Hopcroft-Karp (Hopcroft,J., E., 1973), dan algoritma Hungaria untuk penjodohan sempurna. Dalam masalah pewarnaan, digunakan coloring algorithm. Untuk menentukan pohon penjangkau minimum dapat digunakan algoritma Boruvska, Kruskal (Kuskal, J., 1956, Proceeding of AMS pp 48-50), Prim atau algoritm balik-hapus (reverse-delete algorithm). Untuk masalah jaringan berkapasitas ada algoritma Ford-Fulkerson, Edmons-Karp, Dinic, Karger dan push-relabel algorithm. Untuk menemukan lintasan terpendek digunakan algoritma Bellman-Ford, Dijkstra, Floyd-Warshall atau Johnson. Untuk menyelesaikan masalah penjaja keliling (traveling salesman problem) tersedia algoritma tetangga terdekat (nearest neighbor) dan algoritma Christofides. Algoritma ini muncul dari masalah praktis untuk menentukan jarak terpendek dari tempat A ke tempat B dimana ada beberapa alternatif ruas jalan yang dapat ditempuh. Masalah ini dapat C-262


ISSN: 1979-911X

direpresentasikan dengan penentuan lintasan terpendek antara dua buah simpul dalam suatu graf terbobot. Sebagai contoh, apabila dimiliki graf terbobot seperti berikut:

Gambar 6 Graf terbobot G dengan 9 simpul Bagaimana menentukan lintasan terpendek dari simpul 1 ke simpul 9? Untuk itu dapat digunakan beberapa algoritma seperti algoritma Dijkstra. Simpul 1 disebut simpul sumber dan simpul 9 disebut simpul tujuan. Langkahnya adalah: 1. Setel jarak ke simpul sumber sama dengan nol dan jarak ke simpul-simpul lainnya sama dengan tak hingga. 2. Di antara semua simpul yang belum diproses, temukan satu simpul yang memiliki jarak minimum dan namakan sebagai i. Jika i merupakan simpul tujuan, maka jarak minimum/lintasan terpendek simpul sumber ke simpul tujuan sudah ditemukan dan selesai. Jika bukan, maka tandai simpul tersebut dan lanjutkan ke langkah 3. (jika jarak ke semua simpul yang belum diproses sama dengan tak hingga maka tidak ada lintasan dari simpul sumber ke simpul tujuan) 3. Periksa semua simpul j yang belum terproses dan berinsiden dengan simpul i. Jika jarak terpendek ke simpul j lebih besar dari jarak terpendek ke i ditambah bobot sisi antara ke dua simpul tersebut, maka jarak/lintasan terpendek ke j diperbarui dengan nilai tersebut dan tandai bahwa simpul itu telah dicapai dari i. 4. Kembali ke langkah 2. Algoritma dalam graf dapat dimanfaatkan untuk penyelesaian masalah praktis sehari-hari di berbagai bidang. Agar pemakai teori graf dapat memanfaatkan algoritma dengan mudah, perlu disediakan paket program yang bersifat user friendly. Banyak paket program untuk menyelesaikan permasalahan dalam teori graf baik yang bersifat proprietary maupun open source. Paket tersebut ada yang merupakan bagian dari paket software umum seperti paket atau toolbox seperti Networks dan GraphTheory yang merupakan salah satu toolbox dari software Maple. Dalam software Matlab dapat digunakan toolbox Matgraph atau Bioinformatics. Namun demikian ada beberapa paket program berukuran kecil yang khusus dibuat untuk menyelesaikan masalah-masalah dalam graf. Paket-paket tersebut antara lain Graph Magics, Gephi, Graphviz, Graphalg, Connectifity, dan Gograph. Berikut ini dibahas beberapa paket program yang tersedia untuk penyelesaian masalah graf serta contoh penggunaannya. Graph Magics merupakan software teori graf yang bersifat shareware dan dikembangkan oleh Dumitru Ciubatii. Softaware ini dapat didownload di www.graph-magics.com. Graph Magics dapat menyusun, memodifikasi dan melakukan operasi dan algoritma graf. Tersedia tool graph generator dan algoritma-algoritma seperti lintasan terpendek, pohon penjangkau minimum, max flow-min cut, lintasan Euler dan Hamilton. Software ini cocok digunakan dalam belajar teori graf. Visualisasi graf yang bagus dapat disimpan dalam file atau dicetak. Untuk membuat suatu graf baru dimulai dengan membuat file baru (pilih menu File Æ New), menambahkan simpul baru (klik icon “ +”), serta menambah/menghapus sisi-sisi sesuai keinginan kita. Untuk menambah/menghapus sisi antara dua simpul atau lebih, lakukan ctrl+klik simpul-simpul tersebut, klik kanan, dan pilih opsi yang sesuai. Apabila diperlukan dapat juga ditambahkan bobot atau kapasitas dari sisi-sisinya.

C-263


ISSN: 1979-911X

Gambar 7 Tampilan program Graph Magics dengan menu dan sub menunya Hasil yang diperoleh dapat diedit simpul, sisi, bobot dan kapasitas sisi, serta layoutnya. Pilihan layout yang tersedia adalah free, circle, bipartit, tree dan grid dilakukan dengan perintah Graph Æ Vertices Layout Æ pilihan layout. Graf yang baru juga dapat dibuat dengan menggunakan fasilitas Generate. Untuk menggenerate graf, klik File Æ Generate a New Graph Æ isi jumlah simpul, jumlah sisi, jenis graf dan pilihannya Æ Generate Æ pilih editor dan append to existing graph Æ klik export Æ klik OK. Proses pengeditan simpul, sisi, bobot dan kapasitas sisi dapat dilakukan melalui data grafnya dengan memilih menu View Data atau Graph-Data, kemudian ubah nilainya dan refresh grafnya.

Gambar 8 Graf yang dibuat dengan menempatkan simpul secara bebas dan layout circle

(a)

(b)

Gambar 9 (a) Pilihan jumlah simpul dan sisi, bobot dan kapasitas sisi, serta jenis graf (b) Graf yang dibuat dengan menggunakan fasilitas Generate dengan pilihan (a) Gephi merupakan sotware yang dapat digunakan untuk memvisualiasikan graf atau jaringan yang berukuran besar. Software ini cocok untuk pengguna graf di bidang manajemen dan pemasaran (Walia, L and Bhatia, P.S., 2012). Software ini bersifat open source dan user friendly. Tersedia menumenu File, Workspace, View, Tool, Window, Plugins dan Help yang mudah digunakan. Graf yang dibuat dengan Gephi dapat direkayasa sehingga memiliki tampilan bentuk dan warna yang menarik dan hasilnya dapat diekspor dalam file pdf, PNG atau SVG. Gephi dapat membuka contoh graf yang ada, mengimpor graf atau mengenerate graf sendiri. Contoh Graf Les Miserables yang menggambarkan hubungan tokoh-tokoh dalam novel les Miserables: C-264


ISSN: 1979-911X

Gambar 10 Graf Les Miserables Untuk melihat beberapa karakteristik dari graf, pilih sub menu Statistics dari menu Window dan klik Run. Statistik yang tersedia adalah average degree, average weighted degree, nerwork diameter, graph density, dan sebagainya.

Gambar 11 Beberapa pilihan untuk melihat karakteristik dari graf dengan Gephi. Gephi dapat mengimport graf dari spigot atau database. Untuk menggenerate graf dengan sifat tertentu, klik menu File Æ generate Æ pilihan graf (random atau dinamic graf). Berikut ini contohnya:

Gambar 12 Graf random dengan 200 simpul yang digenerate dengan Gephi Graphviz merupakan software open source yang baik untuk memvisualisasikan masalah jaringan dengan ukuran sampai satu juta simpul. Karena itu cocok digunakan di bidang jaringan, basis data, bioinformatika, rekayasa perangkat lunak, bahasa dan alat pemrograman, dan machine learning. Graphviz dapat didownload di www. Graphviz.org. Graphviz dapat menggambarkan dan mengedit graf sesuai keinginan. Untuk keperluan itu perlu dipelajari pemrogramannya karena Graphviz menggunakan pemrograman berbasis text. Berikut contohnya: C-265


Program digraph { 1 -> 2; 1 -> 3; }

Visualisasi

Program graph { 1 -- 2; 1 -- 3; }

ISSN: 1979-911X

Visualisasi

Gambar 13 kode program dan visualisasi graf berarah dan tak berarah dengan 3 simpul Untuk menggambarkan graf yang lebih detil, dapat dilakukan dengan menuliskan programnya berdasar panduan penggunaan (user guide) yang dapat kita peroleh di website Graphviz. Algoritma graf dengan menggunakan Software Graph Magics merupakan software yang dilengkapi dengan banyak algoritma. Dengan Graph Magics dapat ditentukan nilai tertentu dari graf dengan memilih algoritma yang sesuai. Beberapa algoritma yang dapat dilakukan dengan menggunakan Graph Magics adalah Shortest path algorithm, Minimal Spanning tree, Trail Euler, Lintasan Hamilton, dan Chinese Postman Problem. Misal ingin ditentukan shortest path dari simpul 1 ke simpul 9 dalam graph G berikut.

Gambar 14 Graf terbobot G dengan 9 simpul, simpul 1 : simpul sumber dan simpul 2 : simpul tujuan Setelah graf G digambarkan, simpul sumber dan simpul tujuan harus ditandai terlebih dahulu dengan mengklik kanan simpulnya dan memilih set/unset as start vertex (untuk simpul sumber) atau set/unset as end vertex (untuk simpul tujuan). Selanjutnya tinggal dipilih algoritmanya dengan mengklik Graph Æ Find Æ Shortest Path (From start to end vertex). Hasilnya akan ditunjukkan seperti berikut:

Gambar 15 lintasan terpendek dari simpul 1 ke simpul 9. Terlihat bahwa lintasan (1,2,4,7,9) merupakan lintasan terpendek dari simpul 1 ke simpul 9 dengan total jarak/bobot 2+1+4+4=11. Nilai ini juga dapat dilihat jika diklik pilihan View Data:

Gambar 16 Tampilan data dari lintasan terpendek dalam G C-266


ISSN: 1979-911X

Jika ingin dicari semua lintasan terpendek dari simpul 1 ke simpul-simpul lainnya, maka dapat dilakukan dengan menset simpul 1 sebagai start vertex dan dipilih algoritmanya: Graph Æ Find Æ All Shortest paths: Data panjang lintasan terpendek dari simpul 1 ke simpul-simpul lainnya juga dapat ditampilkan

Gambar 17 Lintasan terpendek dari simpul 1 ke simpul-simpul lainnya Minimal Spanning tree Graph magics juga memiliki algoritma untuk menentukan minimal spanning tree dari suatu graf. Untuk mencari minimal spanning tree dari graf G di atas, pilih menu Graf Æ Find Æ Minimal Spanning Tree. Untuk menampilkan data bobot dari minimal spanning tree tersebut, klik Graph Data.

Gambar 18 minimal spanning tree dari graf G dan data bobotnya Trail Euler Dalam Graph Magics, istilah trail Euler disamakan dengan lintasan Euler. Untuk mencari trail Euler dengan Graph Magics, caranya juga mudah. Pilih menu Graph Æ Find Æ Eulerian Path/Circuit

Gambar 19 Trail Euler dari dan data sisi-sisi dari trail Euler G Lintasan Hamilton Untuk mencari lintasan Hamilton, pilih menu Graph Æ Find Æ Hamitonian Path. Hasilnya adalah seperti berikut:

Gambar 20 Lintasan Hamilton beserta data lintasan Hamilton dari G Chinese Postman Problem Salah satu permasalahan nyata yang sangat terkenal adalah Chinese Postman Problem, yakni masalah tentang bagaimana seorang tukang pos menemukan jalur (kalang) terpendek yang harus dilewati berawal dari kantor pos menuju ke semua alamat tujuan dan kembali ke kantor pos lagi (atau langsung ke rumahnya). Dengan menggunakan Graph Magics, pilih menu Graph Æ Find Æ Chinese C-267


ISSN: 1979-911X

Postman Problem. Untuk melihat jalur mana yang harus dilewati dapat dilihat dengan klik Graph Data.

Gambar 21 Jalur (kalang) terpendek dari simpul 1 ke simpul-simpul lainnya dan kembali ke simpul 1 beserta data urutan simpul-simpul yang dilewati KESIMPULAN Dari penelitian yang telah dilakukan diperoleh beberapa kesimpulan. Teori graf perlu dipelajari dan dikembangkan karena dapat digunakan untuk menyelesaikan beberapa permasalahan nyata dalam berbagai bidang. Untuk mempermudah dalam memahami istilah, konsep, teorema dalam teori graf dibutuhkan software yang dapat digunakan untuk memvisualisasikan graf serta melakukan algoritma dalam graf dengan mudah. Ada berbagai software open sorce yang dapat digunakan untuk visualisasi dan algoritma dalam teori graf. Software-software Graph Magics, Gephi dan Graphviz dapat dimanfaatkan untuk mengatasi permasalahan tersebut. DAFTAR PUSTAKA Bass, D.W., 2002, Hamilton Decompositions and (n/2)-Factorizations of Hypercubes, Journal of Graph Algorithms and Applications vol. 6, no. 3, pp. 174–194 (2002) Brent, R.P., 1980, An Improved Monte Carlo Factorization Algorithm, BIT 20 (1980), pp 176-184. Ciubatii, D., 2013, Graph Magics, http://www.graph-magics.com/index.php, diakses 14 Februari 2013. Ebrahimi, M.A. et al., 2006, A Graph Theory Package for Maple, Part II: Graph Coloring, Graph Drawing, Support Tools, and Networks, Department of Mathematics, Simon Fraser University Burnaby, BC, Canada, V5A 1S6 Guerrieri, B., Solving the Traveling Salesman Problem, Florida A&M University Hopcrof, J., E., and R.M. Karp, An n2.5 Algorithm for Maximum Matchings in Bipartite Graphs, SIAM Journal of Computing, Vol. 2, No. 4, 1973, 225-231 Knuth, D., E., 1969, The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley. Kuskal, J., 1956, Proceeding of the American Mathematical Society pp 48-50 (1956). Lacey, L.L.,2004, Max Flow-Min Cut, Schenectady County Community College, Schenectady, NY, USA. Mawata, C., P., Graph Theory Lessons, 2013, http://www.mathcove.net/petersen/lessons, diakses 18 Februari 2013. Rajan, M. A., M. Girish Chandra, Lokanatha C. Reddy, Prakash Hiremath, 2008, Concepts of Graph Theory Relevant to Ad-hoc Networks, Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. III (2008) Seffens, W., 2002, Graph Theory Patterns in the Genetic Codes, Forma, 17, 309–320, 2002 Shrinivas, S., G. et.al., 2010,Applications of Graph Theory in Computer Science an Overview, International Journal of Engineering Science and Technology Vol. 2(9), 2010, 4610-4621. Walia, L and Bhatia, P.S., 2012, Data Visualization with Gephi, Vinot Gupta Scchool of Managemen, IIT Karagpur .............., 2013, Graphviz -Graph Visualization Software, http://graphviz.org/, diakses 14 Februari 2013. C-268

VISUALISASI GRAF DAN ALGORITMA-ALGORITMA DALAM TEORI GRAF MENGGUNAKAN BEBERAPA PAKET SOFTWARE

Recommend Documents