PERANCANGAN ALGORITMA KETERHUBUNGAN SUATU GRAF DAN PENERAPANNYA DALAM PENGATURAN ARUS LALU LINTAS JALAN RAYA Nama Mahasiswa : Darill Muflih Arief NRP : 1207100069 Jurusan : Matematika FMIPA-ITS Pembimbing I : Drs. Sumarno, DEA. Pembimbing II : Drs. Soetrisno, MI.Komp.
Abstrak Graf merupakan topik yang banyak mendapat perhatian, karena banyak masalah yang bisa diselesaikan dengan graf. Graf digunakan untuk merepresentasikan sistem diskrit dan hubungan antara objek-objek tersebut. Salah satu masalah diskrit pada graf adalah keterhubungan. Aplikasi keterhubungan graf dapat diterapkan dalam sistem lalu lintas jalan raya. Sistem lalu lintas jalan raya haruslah memiliki keterhubungan yang kuat antara satu jalan dengan jalan yang lain sehingga terdapat suatu lintasan untuk setiap tempat yang dilalui. Pada tugas akhir ini dirancang algoritma untuk mengecek status keterhubungan suatu graf. Algoritma dirancang dengan memperhatikan arah busur pada masing-masing simpul. Jumlah eksekusi algoritma berbanding lurus dengan banyaknya busur pada graf. Akan tetapi, untuk menentukan jumlah maksimum eksekusi mengacu pada banyaknya simpul pada graf. Algoritma tersebut kemudian diimplementasikan ke bahasa JavaScript dan diaplikasikan dengan membuat abstraksi graf dari arus lalu lintas pada jalan raya. Keywords: Graf, Algoritma keterhubungan, JavaScript
1. Pendahuluan Graf adalah salah satu bidang dalam ilmu matematika. Graf sering digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek objek tersebut. Representasi visual dari graf dapat dilakukan dengan menyatakan objek sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Graf merupakan topik yang banyak mendapat perhatian, karena representasinya sangat berguna untuk aplikasi yang luas. Dari masalah yang terdapat pada berbagai disiplin ilmu dapat diselesaikan dengan membuat representasi grafnya. Salah satu masalah diskrit pada graf adalah masalah keterhubungan, yaitu apakah suatu graf merupakan graf terhubung atau graf tak terhubung. Suatu graf terhubung yang memiliki arah juga harus dicek lagi apakah merupakan graf terhubung kuat atau tidak. Informasi mengenai keterhubungan suatu graf merupakan suatu informasi yang sangat penting untuk memecahkan masalahmasalah lainnya. Lalu lintas merupakan gerak kendaraan di ruang lalu lintas yang telah disediakan. Ruang lalu lintas darat salah satunya adalah jalan raya. Dalam sistem lalu lintas jalan raya, sangatlah penting memiliki suatu lintasan yang terhubung satu sama lain. Selain itu, diperlukan suatu manajemen arus lalu lintas yang bisa menjangkau seluruh bagian yang dilalui oleh jalan raya tersebut. Banyak cara dalam memanajemen arus lalu lintas jalan raya, antara lain dengan memberikan rambu-rambu, traffic light, dan bisa juga dengan mengubah arah arus lalu lintas. Preprint submitted to Elsevier
Dalam kebijakan mengubah arah lalu lintas, baik dengan mengganti arah suatu jalan maupun menjadikan jalan yang pada awalnya dua arah menjadi satu arah, memerlukan suatu pertimbangan yang matang. Salah satu pertimbangan yang paling mendasar adalah dengan mengecek apakah jalan tersebut masih terhubung secara kuat atau tidak setelah perubahan arah tersebut dilakukan. Pada tugas akhir ini, suatu sistem lalu lintas jalan raya diabstraksi ke dalam bentuk graf dan akan dicek status keterhubungannya dengan algoritma yang telah dirancang sebelumnya. Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis. 2. Dasar Teori 2.1. Graf Secara matematis graf didefinisikan sebagai pasangan himpunan G(V, E) dimana V adalah himpunan hingga tidak kosong dari simpul (vertex) V dan E himpunan berhingga sisi (edge). Maka graf G = (V, E), dimana : V = {v1 , v2 , · · · vm } E = {e1 , e2 , · · · en } Sebuah graf G berisikan dua himpunan yaitu himpunan berhingga tak kosong V(G) dari obyek-obyek yang disebut simpul dan himpunan berhingga (mungkin kosong) E(G) yang elemen-elemennya disebut sisi sedemikian hingga setiap elemen e dalam E(G) merupakan pasangan tak berurutan dari January 26, 2012
simpul-simpul di V(G). Himpunan V(G) disebut himpunan simpul G, dan himpunan E(G) disebut himpunan sisi G. Misalkan u dan v adalah dua simpul di G dan e = {u, v} (sering ditulis e = uv) adalah sebuah sisi G. Kita katakan simpul u dan simpul v berhubungan langsung (adjacent) di G; sisi e menghubungkan (joining) simpul u dan simpul v di G; u dan v simpul-simpul ujung sisi e; sisi e terkait (incident) dengan simpul v dan juga simpul u. [1] Definisi tersebut menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial.
dari simpul u ke simpul v dapat digambarkan dengan kurva sederhana berarah dari simpul u ke simpul v. Misalnya, graf berarah C=({v1 , v2 , v3 , v4 }, {(v1 , v2 ), (v1 , v3 ), (v3 , v4 ), (v4 , v2 ), (v2 , v3 )}) dapat dipresentasikan dalam bentuk figural seperti tampak pada Gambar 1(c). Demikian pula dengan graf berarah B=(V(H), E(H)) dengan V(H)={v1 , v2 , v3 , v4 } dan E(H)={(v1 , v3 ), (v3 , v4 ), (v4 , v2 ), (v2 , v1 ), (v2 , v3 )} dapat direpresentasikan secara figural seperti tampak pada Gambar 1(b). Sebagai contoh, graf berarah pada Gambar 1(b) adalah graf terhubung lemah karena graf dasarnya, yaitu graf pada Gambar 1(a) terhubung. Karena tidak ada lintasan berarah dari simpul v4 ke simpul v1 pada graf berarah B, maka graf berarah B tidak terhubung kuat. Sedangkan graf berarah pada Gambar 2.1(c) adalah graf berarah terhubung kuat. Jelaslah bahwa setiap graf berarah terhubung kuat pasti graf berarah tersebut terhubung lemah, tetapi sebaliknya tidak berlaku. Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum subgraf yang terhubung kuat. Graf berarah disebut terhubung kuat jika untuk setiap pasangan simpul a dan b terdapat lintasan dari a ke b serta dari b ke a. Komponen terhubung kuat pada graf berarah merupakan subgraf terhubung kuat maksimal pada suatu graf. Komponen ini membentuk partisi dari graf.
2.2. Graf Berarah (directed graph atau digraph) Graf berarah adalah graf yang sisinya memiliki orientasi arah. Sisi berarah lebih dikenal dengan sebutan busur (arc). Simpul yang tidak bertanda disebut juga simpul asal atau inisial vertex sedangkan simpul yang ditunjuk oleh tanda panah disebut juga simpul terminal atau terminal vertex. Sebuah graf berarah D adalah suatu pasang berurutan dari dua himpunan V(D) yaitu himpunan berhingga tak kosong yang anggota-anggotanya yang disebut simpul dan E(D) yaitu himpunan berhingga (boleh kosong) yang anggotanya-anggotanya disebut busur sedemikian hingga setiap busur merupakan pasangan berurutan dari dua simpul di V(D). Jika v1 dan v2 adalah dua simpul pada graf berarah D dan e (v1 , v2 ) sebuah busur D, maka e disebut busur-keluar dari simpul v1 dan e disebut busur-menuju simpul v2 . Untuk efisiensi, busur e = (vi , v j ) sering ditulis (i, j). [1] Misalkan D sebuah graf berarah dan v ∈ V(D). Derajatkeluar simpul v, dilambangkan od(v), adalah banyaknya busur pada graf berarah D yang keluar dari simpul v. Sedangkan, derajat-masuk simpul v, dilambangkan id(v), adalah banyaknya busur D yang menuju ke simpul v. [4] Dengan menggunakan konsep lintasan berarah dan konsep graf dasar dari suatu graf berarah kita definisikan konsep keterhubungan pada graf berarah. Ada dua macam keterhubungan pada graf berarah D yaitu terhubung lemah dan terhubung kuat. Graf berarah D dikatakan terhubung lemah jika graf dasarnya terhubung, sedangkan dikatakan terhubung kuat jika untuk setiap dua simpul vi dan v j di D terdapat lintasan berarah dari vi ke v j dan atau sebaliknya. [1]
2.3. Representasi Graf Berarah dalam Matriks Cara menyatakan graf berarah dalam matriks sebenarnya tidak jauh berbeda dengan cara menyatakan graf tak berarah dalam suatu matriks. Perbedaannya hanya terletak pada keikutsertaan informasi tentang busur (arah garis) yang terdapat dalam graf berarah. [4]
Gambar 2: Graf Berarah Terhubung
Salah satu cara merepresentasikan suatu graf berarah adalah dengan matriks hubung. Misalkan G adalah graf berarah yang terdiri dari n simpul tanpa garis paralel. Matriks hubung yang sesuai dengan graf G adalah matriks bujur sangkar n × n, M = (mi j ) dengan ( 1, jika ada busur dari vi ke v j mi j = 0, jika tidak ada busur dari vi ke v j Untuk lebih jelasnya akan diberikan contoh representasi matriks hubung dari graf berarah. Gambar 2.2 merupakan graf berarah yang terhubung. Graf G adalah sebuah graf berarah dengan representasi matriks hubung
Gambar 1: (a) Graf dasar dari graf berarah (b) maupun (c), (b) Graf berarah terhubung lemah (c) Graf berarah terhubung kuat.
Secara figural setiap simpul dari suatu graf berarah digambarkan dengan sebuah noktah, sedangkan setiap busur 2
v1 v2 v3 v1 0 1 1 v2 1 0 0 v3 0 0 0 v 0 1 0 M = 4 v5 0 0 1 v6 0 0 0 v7 0 0 0 v8 0 0 0 Apabila terdapat loop v1 ), maka mii = 1.
v4 v5 v6 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 pada simpul
v7 v8 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 vi (seperti pada simpul
2. Implementasi (pelaksanaan) algoritma Pada tahap ini dilakukan implementasi algoritma yang telah dirancang sebelumnya. 3. Aplikasi (penerapan) Pada tahap ini dilakukan abstraksi model data arah jalan raya ke dalam bentuk graf dan dikenakan algoritma yang telah diimplementasi sebelumnya. 4. Pengujian dan evaluasi Pada tahap ini dilakukan pengujian serta evaluasi dari implementasi dan aplikasi yang telah dilakukan. 5. Penarikan kesimpulan Pada tahap ini dilakukan penarikan kesimpulan berdasarkan hasil implementasi, aplikasi dan evaluasi.
2.4. Algoritma Pencarian Pertama secara Mendalam (Depth First Search) Algoritma Depth First Search (DFS) mencari solusi dengan mengunjungi simpul akar, lalu simpul-simpul yang bertetangga dengan simpul akar (setingkat di bawahnya), terus sampai simpul paling dalam pada bagian tersebut. Setelah itu, dicari simpul yang telah dikunjungi pada tingkat terdekat dan terdalam, lalu simpul yang bertetangga dengan simpul ini dikunjungi, demikian seterusnya sampai seluruh simpul telah dikunjungi. [2]
4. Perancangan Algoritma dan Implementasi 4.1. Ide Dasar Ide dasar dari algoritma ini adalah algoritma pencarian pertama secara mendalam yaitu menelusuri lintasan dari setiap simpul serta mendapatkan simpul-simpul yang dilaluinya. Pada graf berarah terhubung, jika setiap simpul pada graf G memiliki lintasan ke setiap simpul di G, maka graf G terhubung kuat. Jika terdapat satu simpul saja yang tidak memiliki lintasan ke salah satu simpul pada graf G, maka graf tersebut bukan merupakan graf terhubung kuat. Berikut akan disajikan 2 algoritma untuk mengecek status suatu graf dengan menelusuri busur-busur pada setiap simpul, kemudian salah satunya diimplementasikan dan diaplikasikan dalam pengaturan arus lalu lintas jalan raya. 4.2. Algoritma Status Keterhubungan Suatu Graf
Gambar 3: Ilustrasi Urutan Kunjungan Simpul pada algoritma DFS
4.2.1. Algoritma I Algoritma untuk mengecek status keterhubungan suatu graf ini dilakukan dengan cara menelusuri lintasan dari setiap simpul pada graf. Ada beberapa tahap yang harus dilakukan untuk mengetahui status keterhubungan suatu graf.
Dari Gambar 3, dapat dilihat bahwa dengan algoritma DFS, setiap anak simpul pertama yang bertetangga dengan simpul akar dikunjungi sampai tingkat terdalamnya lebih dahulu, lalu seluruh simpul pada subpohon tersebut, sebelum simpul lain yang juga bertetangga dengan simpul akar. Jika algoritma DFS dapat mencari komponen kuat pada graf berarah. Graf berarah disebut terhubung kuat jika untuk setiap pasangan simpul A dan B terdapat lintasan dari A ke B serta dari B ke A. Komponen terhubung kuat pada graf berarah merupakan subgraf terhubung kuat maksimal pada suatu graf. Komponen ini membentuk partisi dari graf.
1. Inisialisasi (a) Input merupakan graf terhubung berarah. (b) n sebagai banyaknya simpul. (c) m sebagai banyaknya busur. 2. Representasi matriks dari graf (a) Dibuat matriks D dengan ukuran n x n. (b) Matriks ( D diisi dengan aturan 1, jika ada busur dari vi ke v j di j = 0, jika tidak ada busur dari vi ke v j Apabila terdapat loop pada simpul vi , maka dii = 1. 3. Operasi baris (a) Baris pertama dioperasikan dengan baris yang menjadi kolom bernilai 1 pada baris tersebut. (b) Operasi baris yang digunakan adalah operasi penjumlahan biner yaitu 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, dan 0+0 = 0 (dik ← dik +d jk dengan k sebagai indeks kolom)
3. Metode Penelitian Pada bagian ini dibahas langkah-langkah yang dilakukan dalam menyelesaikan Tugas Akhir ini. Langkah-langkah untuk menyelesaikan Tugas Akhir adalah sebagai berikut: 1. Perancangan algoritma Pada tahap ini dilakukan perancangan algoritma untuk mengetahui status keterhubungan suatu graf. 3
v1 v2 v3 v4 v5 v1 1 1 1 0 1 v2 0 0 1 0 0 D = v3 0 0 0 1 0 v4 0 0 0 0 1 v5 0 0 0 1 0 Pada baris ke-2 terdapat elemen bernilai 1 pada kolom dioperasikan juga ke-3, maka baris ke-1 dengan baris ke-3 1 1 1 0 1 + 0 0 0 1 0 = 1 1 1 1 1 , sehingga didapat matriks hasil operasi v1 v2 v3 v4 v5 v1 1 1 1 1 1 v2 0 0 1 0 0 D = v3 0 0 0 1 0 v4 0 0 0 0 1 v5 0 0 0 1 0 Pada baris ke-3 terdapat elemen bernilai 1 pada kolom ke-4, maka baris ke-1 dioperasikan juga dengan baris ke-4 1 1 1 1 1 + 0 0 0 0 1 = 1 1 1 1 1 , sehingga didapat matriks hasil operasi v1 v2 v3 v4 v5 v1 1 1 1 1 1 v2 0 0 1 0 0 D = v3 0 0 0 1 0 v4 0 0 0 0 1 v5 0 0 0 1 0 Pada baris ke-4 terdapat elemen bernilai 1 pada kolom ke-5, maka baris ke-1 dioperasikan juga dengan baris ke-5 1 1 1 1 1 + 0 0 0 1 0 = 1 1 1 1 1 , sehingga didapat matriks hasil operasi v1 v2 v3 v4 v5 v1 1 1 1 1 1 v2 0 0 1 0 0 D1 = v3 0 0 0 1 0 v4 0 0 0 0 1 v5 0 0 0 1 0 Pada baris ke-5 terdapat elemen bernilai 1 pada kolom ke4. Namun, karena baris ke-4 sudah dioperasikan dengan baris ke-4 maka operasi baris tidak dilakukan. Hal yang serupa dilakukan terhadap baris-baris yang memiliki elemen bernilai 1. Operasi yang dilakukan terhadap baris ke-2 adalah operasi dengan baris ke-3, baris ke-4, dan baris ke-5 sehingga didapat matriks hasil operasi v1 v2 v3 v4 v5 v1 1 1 1 1 1 v2 0 1 1 1 1 D2 = v3 0 0 0 1 0 v4 0 0 0 0 1 v5 0 0 0 1 0 Pada baris ke-3 terdapat elemen bernilai 1 pada kolom ke-4, maka baris dioperasikan baris ke 4 ke-3 dengan 0 0 0 1 0 + 0 0 0 0 1 = 0 0 0 1 1, kemudian dilanjutkan operasi dengan baris ke-5, 0 0 0 1 1 + 0 0 0 1 0 = 0 0 0 1 1, sehingga didapat matriks hasil operasi
(c) Jika pada baris yang dioperasikan terdapat lagi kolom yang bernilai 1, maka baris tersebut dioperasikan lagi dengan baris yang menjadi kolom bernilai 1 pada baris tersebut (rekursif). (d) Operasi dilakukan dengan meninjau tiap-tiap baris pada matriks. 4. Pengecekan kondisi berhenti Operasi baris berhenti jika seluruh baris pada matriks telah selesai ditinjau. 5. Penentuan Status (a) Didapat matriks akhir hasil operasi baris yang merepresentasikan keterhubungan serta lintasan yang mungkin dari tiap-tiap simpul. (b) Jika elemen-elemen pada matriks akhir bernilai 1 semua, maka matriks tersebut merepresentasikan sebuah graf terhubung kuat. 1 1 1 1 1 1 1 1 1 1 D = 1 1 1 1 1 . 1 1 1 . . . .. 1 1 1 ··· 1 (c) Jika terdapat elemen bernilai 0 pada matriks akhir, maka matriks tersebut merepresentasikan sebuah graf yang tidak terhubung kuat. Matriks hasil akhir merepresentasikan lintasan (simpul yang dilalui) dari tiap-tiap simpul. Untuk membuat graf terhubung kuat adalah dengan menambahkan busur (dari simpul yang belum memiliki lintasan ke semua simpul) ke salah satu busur yang memiliki lintasan ke semua simpul (barisnya bernilai 1 semua).
Gambar 4: Graf Berarah Terhubung
Untuk ilustrasi diberikan graf D seperti pada Gambar 4 dengan representasi matriks : v1 v2 v3 v4 v5 v1 1 1 0 0 1 v2 0 0 1 0 0 D = v3 0 0 0 1 0 v4 0 0 0 0 1 v5 0 0 0 1 0 Dilakukan operasi baris pada baris pertama dengan baris yang menjadi kolom bernilai 1 pada baris pertama. Baris ke-1 1 1 0 0 1 dioperasikan dengan baris ke-2 0 0 1 0 0 , didapat matriks hasil operasi 4
v1 v2 v3 v4 v5 v1 1 1 1 1 1 v2 0 1 1 1 1 D3 = v3 0 0 0 1 1 v4 0 0 0 0 1 v5 0 0 0 1 0 Baris ke-4 dioperasikan dengan baris ke-5 0 0 0 0 1 + 0 0 0 1 0 = 0 0 0 1 1, sehingga didapat matriks hasil operasi v1 v2 v3 v4 v5 v1 1 1 1 1 1 v2 0 1 1 1 1 D4 = v3 0 0 0 1 1 v4 0 0 0 1 1 v5 0 0 0 1 0 dan baris ke-5 baris ke-4 dioperasikan dengan 0 0 0 1 0 + 0 0 0 0 1 = 0 0 0 1 1, sehingga didapat matriks hasil operasi v1 v2 v3 v4 v5 v1 1 1 1 1 1 v2 0 1 1 1 1 D5 = v3 0 0 0 1 1 v4 0 0 0 1 1 v5 0 0 0 1 1 Setelah semua baris yang memiliki elemen bernilai 1 dioperasikan, didapat matriks akhir yang merepresentasikan lintasan dari tiap-tiap simpul v1 v2 v3 v4 v5 v1 1 1 1 1 1 v2 0 1 1 1 1 D = v3 0 0 0 1 1 v4 0 0 0 1 1 v5 0 0 0 1 1 Dari matriks akhir tersebut dapat disimpulkan bahwa graf tersebut bukan merupakan graf terhubung kuat karena setelah dilakukan algoritma operasi baris, masih ada elemen yang bernilai 0 yang menandakan bahwa terdapat simpul yang tidak memiliki lintasan ke simpul lainnya.
Gambar 5: Pelabelan Simpul va , a = 1
(e) Label - diberikan pada simpul awal busur masuk simpul va . (f) Misalkan vc adalah simpul awal busur masuk simpul vc , label - diberikan juga pada simpul awal busur masuk simpul vc . (g) Pelabelan (label -) dilanjutkan terhadap semua simpul yang mungkin diberi label - sesuai dengan aturan pada poin (e).
Gambar 6: Pelabelan Seluruh Simpul Pada Graf
3. Pengecekan kondisi berhenti Pelabelan berhenti jika sudah tidak ada lagi simpul dan busur yang ditinjau (Gambar 6). 4. Penentuan Status (a) Didapat label ±, +, atau - pada masing-masing simpul. (b) Jika semua simpul memiliki label ±, maka graf tersebut merupakan graf terhubung kuat.
4.2.2. Algoritma II Algoritma untuk mengecek status keterhubungan suatu graf ini dilakukan dengan cara memberi label pada tiap-tiap simpul dengan meninjau busur masuk dan busur keluarnya.
Untuk membuat graf menjadi terhubung kuat, maka dilakukan reduksi graf dengan cara : 1. Simpul yang berlabel ± dikelompokkan menjadi satu (sebagai suatu komponen terhubung kuat). 2. Langkah 2 (pelabelan simpul) diulangi kembali dengan membuang simpul yang telah dikelompokkan (Gambar 7 dan Gambar 8). 3. Langkah ini berulang terus sampai sudah tidak ada lagi simpul yang bisa direduksi (dikelompokkan).
1. Inisialisasi Input merupakan graf terhubung berarah. 2. Pelabelan Simpul (a) Label ± diberikan pada sebarang simpul va pada graf (Gambar 5). (b) Label + diberikan pada simpul yang dituju oleh busur keluar simpul va . (c) Misalkan vb adalah simpul yang dituju oleh busur keluar simpul va , label + diberikan juga pada simpul yang dituju oleh busur keluar simpul vb . (d) Pelabelan (label +) dilanjutkan terhadap semua simpul yang mungkin diberi label + sesuai dengan aturan pada poin (c).
Setelah didapat graf hasil reduksi dari graf awal (Gambar 9). Maka untuk membuat graf terhubung kuat cukup dengan memberi busur yang berlawanan dari satu elemen dalam komponen terhubung kuat ke salah satu komponen terhubung kuat lainnya. Atau dengan merubah orientasi arah sehingga didapat graf reduksi yang terhubung kuat. 5
Gambar 7: Pelabelan Simpul va , a = 6
Gambar 8: Pelabelan Simpul Tahap II
Gambar 9: Graf Hasil Reduksi
Gambar 10: Diagram Alir Status Keterhubungan Graf
Kedua Algoritma tersebut bekerja berbanding lurus dengan banyaknya busur pada suatu graf. Semakin banyak busur yang ada pada suatu graf, maka semakin besar alokasi waktu untuk mendapatkan hasil yang dikehendaki. Algoritma yang akan diimplementasi adalah algoritma I yaitu dengan cara memanipulasi matriks hubung dari representasi grafnya.
5. Pengujian dan Pembahasan 5.1. Lingkungan Uji Coba Lingkungan uji coba perangkat lunak yang dibangun dalam Tugas Akhir ini meliputi perangkat keras dan perangkat lunak yang digunakan. Spesifikasinya disajikan dalam Tabel 1. Perangkat Keras
4.3. Kompleksitas Algoritma Perangkat Lunak Jumlah maksimum mekanisme setiap operasi ini adalah sebanyak n − 1 (dengan n sebagai jumlah simpul pada graf) yaitu jika suatu baris dioperasikan dengan seluruh baris yang lain (kecuali dengan barisnya sendiri) dan karena setiap operasi baris melakukan paling banyak n operasi penjumlahan biner, maka batas atas waktu eksekusi algoritma untuk setiap baris adalah sebesar n(n − 1). Hal ini berakibat untuk mengeksekusi matriks representasi dari graf dengan n simpul (n baris), didapat batas atas waktu eksekusi algoritma sebesar n(n − 1). Jumlah maksimum mekanisme pelabelan pada algoritma II adalah 2n(n − 1), dengan n sebagai jumlah simpul dan 2 sebagai tanda peninjauan 2 kali terhadap maksimum busur (busur masuk dan busur keluar) dari satu simpul ke satu simpul yang lain. n − 1 adalah kemungkinan maksimum terhubungnya suatu simpul dengan simpul yang lain pada graf.
Prosesor : Intel Atom Memory : 1.83 GHz, RAM 1 GB Sistem Operasi : Windows7 Home Basic Skrip editor : Notepad ++ Framework: Backbone.js Library: JQuery, Raphael Piranti pembuka : Google Chrome
Tabel 1: Tabel Lingkungan Uji Coba Sistem
Backbone.js memasok struktur untuk aplikasi JavaScript dengan menyediakan model dengan key-value dan koleksikoleksi yang kaya fungsi serta menghubungkan aplikasi yang sudah ada melalui JSON. JQuery adalah pustaka JavaScript yang cepat dan ringkas dalam penyederhanaan dokumen HTML, penanganan event, animasi, dan interaksi Ajax untuk pengembangan web. Raphael adalah pustaka JavaScript yang menyederhanakan pekerjaan vektor grafis di web. 6
5.2. Uji Coba Proses Uji coba proses dilakukan pada setiap step-step yang ada dalam implementasi algoritma dan aplikasinya 1. Step render vertex dan edge Membuat model graf dengan mengambil data-data dari file vertex.json dan edge.json. JSON sendiri merupakan singkatan dari JavaScript Object Notation (notasi objek JavaScript), adalah suatu format ringkas pertukaran data komputer. Formatnya berbasis teks dan terbaca manusia serta digunakan untuk merepresentasikan struktur data sederhana dan larik asosiatif (disebut objek).
Gambar 11: Rendering Vertex dan Edge
2. Step generate matriks Membuat representasi matriks hubung dari graf berarah (Gambar ( 12) yang sudah ada dengan ketentuan 1, jika ada busur dari vi ke v j mi j = 0, jika tidak ada busur dari vi ke v j
Gambar 13: Step Operasi Baris
Operasi pertama dilakukan pada baris ke-1. Operasi dilakukan dengan mencari elemen yang bernilai 1 pada baris tersebut kemudian dioperasikan dengan baris yang menjadi kolom bernilai 1 pada baris itu. Pertama-tama yang dilakulan adalah mencari nilai 1 dari indeks terkecil pada baris ke-1. Pada kolom ke-2 terdapat nilai 1. Hal ini berakibat baris ke-1 dioperasikan dengan baris ke-2. 0 1 1 0 0 0 0 0 + 1 0 0 0 0 0 0 1 = 1 1 1 0 0 0 0 1. Kemudian kita lihat pada baris ke-2 (yang baru saja dioperasikan), terdapat elemen bernilai 1 pada kolom ke-1 dan ke-8, maka baris ke-1 (hasil operasi dengan baris ke2) dioperasikan lagi (selanjutnya diistilahkan dengan suboperasi) dengan baris ke-1 (dirinya sendiri) dan baris ke-8. 1 1 1 0 0 0 0 1 + 0 0 0 0 0 0 1 0 = 1 1 1 0 0 0 1 1. Karena algoritma ini berjalan secara rekursif, maka kita mencari juga elemen yang bernilai 1 pada baris ke-8 (ada pada kolom ke-7) untuk kemudian dioperasikan (sub-
Gambar 12: Graf Berarah dan Representasi Matriksnya
3. Step operasi baris Operasi baris dilakukan dengan mencari elemen yang bernilai 1 pada baris tersebut kemudian dioperasikan dengan baris yang menjadi kolom bernilai 1 pada baris pertama tadi. Operasi ini berjalan secara rekursif (memanggil dirinya sendiri). Operasi yang digunakan yaitu 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, dan 0 + 0 = 0. Operasi baris dimulai dari baris pertama hingga baris terakhir secara berurutan. 7
operasi) dengan baris ke-1 (hasil operasi dengan baris ke8). 1 1 1 0 0 0 1 1 + 0 0 0 0 0 1 0 0 = 1 1 1 0 0 1 1 1.
Gambar 16: Matriks Hasil Akhir Gambar 14: Konsol Operasi Baris
Dari matriks hasil akhir (Gambar 16) dapat dilihat bahwa simpul 1, 2, 3, 4, dan 5 adalah suatu komponen terhubung kuat. Komponen terhubung kuat lainnya adalah simpul 6 dan 7. Sehingga didapat graf hasil reduksi seperti pada Gambar 4.11. 4. Step pengecekan kondisi berhenti Kondisi berhenti jiga semua simpul sudah selesai ditelusuri lintasannya dan didapat sebuah matriks hasil akhir. Adapun jika hanya untuk mengecek status keterhubungan suatu graf, kondisi berhenti jika ada baris yang elemen-elemennya 0 semua atau jika ada simpul yang setelah ditelusuri lintasannya (setelah dioperasikan barisnya) terdapat nilai 0 (yang artinya tidak terhubung ke suatu simpul tertentu).
Setelah itu kita lihat apakah ada elemen yang bernilai 1 pada baris ke-1 untuk di operasikan lagi. Langkah yang serupa dilakukan terhadap baris-baris berikutnya (Gambar 13). Untuk operasi langkah per langkahnya bisa diamati melalui konsol (Gambar 14). Dari graf pada Gambar 12 didapat matriks hasil akhir dengan nilai elemen-elemennya 0 dan 1. Hal ini menunjukkan bahwa graf tersebut bukan merupakan graf terhubung kuat, karena bila dilihar dari matriks akhirnya hanya baris ke-1, 2, 3, 4, dan 5 yang berisikan nilai 1 semua, yang berarti simpul 1, 2, 3, 4, dan 5 memiliki lintasan ke semua simpul pada graf tersebut, sedangkan yang lain tidak. Simpul 6,7, dan 8 hanya memiliki lintasan ke simpul 6 dan 7 saja.
5.3. Uji Coba Program Ujicoba program dilakukan dengan cara menjalankan skrip yang telah diimplementasikan sebelumnya. Skrip dibuka melalui peramban web (web browser) dengan terlebih dahulu menginstal server yang berdiri sendiri (localhost). Ketika program pertama kali dibuka, maka yang akan muncul adalah interface seperti pada Gambar 17. Kemudian kita bisa membuat abstraksi graf dari peta yang tersedia dengan mengklik tulisan ”Buat Graf” di bagian atas (di bawah judul) sehingga akan muncul tampilan seperti pada Gambat 18. Untuk mengkustomisasi tampilan (melihat peta dan graf atau salah satu dari keduanya), dapat dilakukan dengan mengklik tulisan (di bawah judul) ”Hilangkan/Munculkan Peta” atau ”Hilangkan/Munculkan Graf”. Pengecekan status keterhubungan graf tersebut adalah dengan menekan tombol eksekusi berwarna biru (Gambar 19) dibawah peta/graf sampai muncul keterangan terkait status keterhubungan dari graf (arus lalu lintas). Setelah itu, akan muncul status keterhubungan graf tersebut beserta representasi matriks hubung (Gambar 20 dan Gambar 21) dan representasi matriks lintasan beserta matriks hasil operasi baris per baris.
Gambar 15: Pohon Lintasan Graf pada Gambar 12
Ilustrasi lintasan yang mungkin dari tiap-tiap simpul dapat dilihat pada Gambar 15 dengan simpul ayah hanya dapat mengunjungi simpul akar-akarnya. Sehingga jelas bahwa simpul 1 memiliki lintasan ke semua simpul pada graf tersebut. Begitu pula simpul 2, 3, 4, dan 5. Simpul 6, 7, dan 8 hanya memiliki akar simpul 6 dan simpul 5. Karena graf pada Gambar 12 bukan merupakan graf terhubung kuat, maka untuk membuatnya menjadi graf terhubung kuat adalah dengan cara mencari graf reduksi dimana setiap komponennya merupakan simpul-simpul yang terhubung kuat.
5.4. Pembahasan Pada algoritma I, untuk mengetahui simpul yang dituju oleh simpul ke-i, cukup dengan hanya mencari elemen yang berni8
Gambar 19: Interface Tombol Eksekusi
Gambar 17: Interface Awal
Gambar 20: Matriks Awal
semua simpul pada graf G (jika dilihat matriks hubungnya semua elemennya bernilai 1), maka graf tersebut merupakan graf terhubung kuat. Akan tetapi, jika terdapat minimal satu simpul yang tidak memiliki lintasan yang melalui semua simpul pada graf G (jika dilihat matriks hubungnya, elemen baris kei tidak seragam), maka graf tersebut bukanlah merupakan graf terhubung kuat. Jika setiap selesai operasi baris didapat bahwa elemen baris tersebut tidak bernilai 1 semua, maka bisa langsung disimpulkan bahwa graf tersebut bukan merupakan graf terhubung kuat. Akan tetapi, perhitungan terus dilanjutkan untuk mendapatkan semua lintasan yang mungkin dari setiap simpul pada graf. Sehingga mempermudah untuk mengubah graf tersebut menjadi graf terhubung kuat. Adapun aturan pembacaan matriks yang didapat adalah sebagai berikut :
Gambar 18: Interface Peta dan Graf
lai 1 pada baris ke-i. Agar algoritma lebih sistematis, maka penelusuran dilakukan berurutan dari simpul dengan dengan index terkecil terlebih dahulu (v1 , v2 , v3 , . . . , vn ) Kemudian dari simpul-simpul yang telah dikunjungi akan ditelusuri lagi simpul-simpul yang tertuju berikutnya. Demikian seterusnya sehingga didapat suatu lintasan yang melalui atau tidak melalui simpul-simpul pada graf G. Apabila setiap simpul pada graf G memiliki lintasan yang melalui
• Elemen bernilai 1 di tiap-tiap baris pada matriks hasil 9
graf lalu lintas jalan raya tersebut dengan cara melihat baris dan kolom dari matriks akhirnya. Setelah memperoleh graf reduksi dari graf awal (baik dengan algoritma I maupun algoritma II) maka untuk membuat graf terhubung kuat dari model tersebut adalah dengan memberikan arah bolak-balik (busur masuk dan busur keluar) dari minimal satu elemen (simpul) di dalam suatu graf hasil reduksi ke minimal satu elemen (simpul) graf hasil reduksi yang lain. Pembentukan graf terhubung kuat dapat juga dilalukan dengan cara menambahkan busur keluar dari suatu simpul (yang belum memiliki lintasan ke semua simpul pada graf) menuju simpul lain (yang sudah memiliki lintasan ke semua simpul pada graf). 6. Penutup 6.1. Kesimpulan 1. Baik pada algoritma I maupun algoritma II, jumlah eksekusi algoritma berbanding lurus dengan banyaknya busur pada graf. Namun, untuk menentukan jumlah maksimum eksekusi mengacu pada banyaknya simpul pada graf. 2. Batas atas kompleksitas algoritma I adalah n2 (n − 1) dengan waktu eksekusi terlama sebesar n2 (n − 1)× maksimum waktu yang diperlukan dalam 1 kali iterasi. 3. Batas atas kompleksitas algoritma II adalah 2n(n − 1) dengan waktu eksekusi terlama sebesar 2n(n − 1)× maksimum waktu yang diperlukan dalam 1 kali iterasi.
Gambar 21: Matriks Akhir
akhir menandakan adanya lintasan dari simpul yang diwakili oleh baris tersebut. • Jika pada baris ke-i kolom ke-j terdapat elemen yang bernilai 0, maka simpul ke-i tidak memiliki lintasan menuju simpul ke-j.
6.2. Saran Untuk pengembangan penelitian lebih lanjut, disarankan: 1. Implementasi algoritma dapat dicoba dalam bentuk struktur data yang lain selain matriks. 2. Untuk pembanding proses dari algoritma I, dapat dilakukan implementasi dan aplikasi terhadap algoritma II.
• Jika baris ke-i pada matriks akhir graf berarah bernilai 1 semua, maka simpul yang diwakili oleh baris ke-i memiliki lintasan ke setiap simpul pada graf. • Jika kolom ke- j pada matriks akhir graf berarah bernilai 1 semua, maka simpul yang diwakili oleh kolom ke- j dapat dilintasi oleh setiap simpul pada graf.
References [1] Budayasa, I.K., 2007, Teori Graph dan Aplikasinya Surabaya: Unesa Press. [2] Madanella,Ella, 2007, Strategi Algoritmik Bandung: Program Studi Teknik Informatika STEI ITB. [3] Munir,Rinaldi, 2007, Diktat Kuliah IF 2153, Matematika Diskrit, Edisi Keempat Bandung: Program Studi Teknik Informatika STEI ITB. [4] Siang, J. J., 2002, Matematika Diskrit dan Aplikasinya pada Ilmu Komputer Yogyakarta: Andi.
Karena eksekusi algoritma ini (algoritma I) berbanding lurus dengan banyaknya busur pada graf. maka jumlah eksekusi algoritma pengecekan status keterhubungan suatu graf ini adalah banyaknya elemen bernilai 1 pada representasi matriksnya. Jumlah maksimum mekanisme operasi ini adalah sebanyak n − 1 (maksimum busur keluar pada suatu simpul), dengan n sebagai jumlah simpul pada graf. Dan karena setiap operasi penyatuan melakukan paling banyak n operasi, maka batas atas kompleksitas algoritma program tersebut sebesar n2 (n − 1). Eksekusi algoritma II juga berbanding lurus dengan banyaknya busur pada graf dengan jumlah minimum busur adalah n − 1 (dengan n adalah banyaknya simpul pada graf) dan maksimum busur yang mungkin 2n(n − 1) Untuk menyelesaikan permasalahan perubahan arus lalu lintas maka haruslah didapat keluaran (dari program) graf terhubung kuat. Jika hasil keluarannya belum merupakan graf terhubung kuat, maka akan dibentuk graf reduksi dari model 10
