PENGEMBANGAN PROGRAM APLIKASI KONSTRUKSI GENERALISASI GRAF BERARAH KAUTZ

Abstract

Graf berarah banyak digunakan untuk merepresentasikan objek-objek dalam berbagai terapan ilmu, contohnya untuk merepresentasikan jaringan transportasi udara. Untuk merepresentasikan graf berordo kecil itu mudah, sedangkan untuk merepresentasikan graf yang berordo besar itu sulit. Untuk menghasilkan gambar yang baik, dibutuhkan teknik yang sesuai. Penelitian tentang teknik konstruksi graf berarah sudah banyak dilakukan dan menghasilkan teknik- teknik konstruksi seperti generalisasi graf de Bruijn, generalisasi graf berarah Kautz, graf berarah garis dan lain-lain. Namun tidak semua teknik dapat menghasilkan graf berarah yang teratur, Salah satu teknik yang menghasilkan graf berarah teratur adalah generalisasi graf berarah Kautz. Penemuan teknikteknik konstruksi tersebut tidak disertai dengan pengembangan program aplikasi yang menggunakan komputer untuk memudahkan atau mempercepat pengkonstruksiannya, sehingga untuk mengkonstruksi graf berordo besar masih sulit dilakukan. Tujuan penelitian ini adalah untuk menghasilkan sebuah program aplikasi konstruksi graf berarah Kautz berbasis web sehingga dapat menghasilkan graf berarah yang diketahui derajat-keluar d, diameter k dan ordo n = dk + dk¡b, dengan 0 < b · k untuk b ganjil dan untuk memudahkan pengguna dalam membangun graf berarah yang telah ditentukan derajat keluar d dan diameter k nya. Program aplikasi yang dikembangkan menggunakan bahasa pemrograman PHP yang ditulis dalam teks biasa dan mempunyai akhiran .php. PHP membutuhkan editor seperti ”Edit Plus 3” untuk menulis script yang akan diproses pada web server seperti Apache. Untuk media penyimpanan datanya (database server), PHP menggunakan MySQL. Ketiga software tersebut Apache, MySQL, dan PHP terdapat dalam satu paket software XAMPP yang sudah dikonfigurasi untuk keperluan lingkungan pengembangan aplikasi web. Sehingga, peneliti vii viii hanya tinggal menulis program PHP dan langsung menjalankan program tersebut melalui web browser. Teknik konstruksi yang dipilih adalah generalisasi graf berarah Kautz, maka derajat-keluar d, dimeter k akan menjadi input dengan syarat ordo n = dk + dk¡b, dengan 0 < b · k untuk b ganjil. Kemudian, input tersebut diproses menggunakan formula Imase dan Itoh yakni: v ´ ¡du ¡ i(mod n) i = 1; 2; : : : ; d Graf berarah yang dihasilkan oleh formula ini isomorfis dengan graf berarah yang dihasilkan oleh Miller. Selanjutnya hasil dari formula tersebut dinyatakan dalam matrik ketetanggaan dengan ordo n x n, kemudian matrik ketetanggan tersebut di konversi ke dalam graf berarah yang merupakan hasil konstruksi dari generalisasi graf berarah Kautz. Hasil program tersebut berupa website yang dipasang pada internet. Program tersebut dapat dieksekusi oleh pengguna dimanapun dan kapanpun dari web browser, yakni dengan memasukkan nilai yang diminta sehingga akan dimunculkan matrik ketetanggaannya beserta graf berarah hasil konversi dari matrik ketetanggaannya tersebut.