PENGEMBANGAN PROGRAM APLIKASI KONSTRUKSI GRAF BERARAH DENGAN TEKNIK PENGHAPUSAN TITIK

Abstract

Teori graf merupakan bagian dari ilmu matematika, yang dapat diterapkan pada berbagai bidang ilmu dan juga kehidupan sehari-hari. Teori graf saat ini menjadi topik yang banyak mendapat perhatian, karena graf banyak digunakan untuk merepresentasikan objek-objek di berbagai bidang ilmu seperti masalah dalam jaringan komunikasi, transportasi, ilmu komputer, dan riset operasi. Salah satu topik yang menarik pada teori graf salah satunya adalah yang berhubungan dengan konstruksi suatu graf. Teknik konstruksi graf banyak dimunculkan termasuk diantaranya teknik konstruksi graf berarah Kautz dan teknik penghapusan titik (vertex deleting scheme). Graf berarah Kautz merupakan graf berarah yang berderajat keluar d, diameter k dan ordo n = d . Sedangkan teknik penghapusan titik (vertex deleting scheme) merupakan suatu teknik graf berarah yang dapat dibangun dari graf berarah lainnya dengan menggunakan kesamaan sifat-sifat derajat keluar dari beberapa titik. Tujuan dari penelitian ini yaitu untuk mengembangkan program aplikasi konstruksi graf berarah dengan teknik penghapusan titik berbasis web dengan menggunakan PHP. PHP (akronim dari PHP: Hypertext Preprocessor) merupakan bahasa pemrograman yang berfungsi untuk membuat website dinamis maupun aplikasi web. Dan untuk memudahkan pengguna dalam membangun sebuah graf berarah yang diperoleh dari graf berarah lain yang mempunyai beberapa titik dengan sifat ketetanggaan keluar yang sama. Metode yang digunakan dalam penelitian ini termasuk salah satu jenis penelitian prosedural dikarenakan model penelitian yang bersifat deskriptif dan telah ditunjukkan bagaimana langkah-langkah yang harus dilakukan untuk menghasilkan produk (hasil).Hasil penelitian ini yaitu sebuah matrik adjacency yang dihasilkan dari konstruksi graf berarah Kautz, kemudian hasil dari matrik adjacency tersebut dihasilkan suatu konstruksi graf berarah dengan menggunakan teknik penghapusan titik. Konstruksi graf ini dibatasi untuk nilai k = 2 dan d ¸ 2, sehingga di dapatkan hasil matrik adjacency dan konstruksi graf berarah dengan teknik penghapusan titik. Untuk mendapatkan hasil dari konstruksi ini yaitu dengan memasukkan nilai dari d, dimana d ¸ 2 untuk k = 2, sehingga akan didapatkan nilai dari jumlah titik (n). Kemudian dapat dihasilkan matrik adjacency untuk selajutnya dapat ditentukan bagaimana konstruksi graf berarahnya dengan menggunakan teknik penghapusan titik.