KETERATURAN GRAF BERARAH DERAJAT KELUAR EMPAT DENGAN ORDE KURANG DUA DARI BATAS MOORE

Abstract

Teori graf merupakan cabang matematika diskrit yang dapat diaplikasikan secara luas dalam kehidupan sehari-hari. Salah satu aplikasi graf adalah dalam memodelkan permasalahan perancangan jaringan komunikasi dalam skala besar. Dalam perancangan suatu jaringan, permasalahannya adalah bagaimana memba- ngun sebuah jaringan jika jumlah simpul pada jaringan sebanyak mungkin, jum- lah hubungan yang disambungkan ke suatu simpul dibatasi, dan rute komunikasi antara dua sebarang simpul pada jaringan dibuat sependek mungkin. Dalam teori graf, permasalahan ini dikenal dengan degree/diameter problem yaitu bagaimana membangun sebuah graf berarah besar dengan batasan tertentu. Batasan ini kemudian dikenal dengan nama out-degree (derajat keluar), diameter, dan orde. Untuk mengetahui keberadaan sebuah graf berarah dengan derajat keluar, diameter, dan orde tertentu, salah satu jalan yaitu dengan meneliti keteraturan dari graf berarah itu. Penelitian tentang keteraturan graf berarah sudah banyak dilakukan oleh peneliti lainnya. Sejauh ini, keteraturan dari graf berarah kurang dua dari batas Moore dengan derajat keluar d = 4 dan diameter k ¸ 4 atau derajat keluar d ¸ 5 dan diameter k ¸ 3 masih belum diketahui dan merupakan masalah terbuka. Dalam penelitian ini, peneliti telah melakukan penelitian terhadap ketera- turan graf berarah kurang dua dari batas Moore dengan derajat keluar 4 dan diameter k ¸ 4 dengan hasil akhir bahwa graf berarah tersebut adalah tera- tur. Dalam melakukan penelitian tersebut, peneliti menggunakan metode deduk- tif, induktif, dan brute force. Untuk mengetahui keteraturan dari graf berarah, pembahasannya harus ditinjau dari dua aspek yaitu bagaimanakah keteraturan keluarnya dan bagaimanakah keteraturan masuknya. Jika suatu graf berarah dinyatakan teratur masuk dan teratur ke luar, maka graf berarah tersebut dapat dinyatakan sebagai graf berarah teratur. Baskoro membuktikan bahwa semua graf berarah adalah teratur keluar, se- hingga penelitian tentang keteraturan graf berarah hanya difokuskan untuk mem- pelajari bagaimanakah keteraturan masuknya. Dalam mempelajari keteraturan masuk dari graf berarah, pembahasannya dimulai dengan mengasumsikan bahwa graf berarah tersebut tidak teratur masuk yang dapat direpresentasikan dengan barisan derajat masuk. Sehingga, jika graf berarah kurang dua dari batas Moore dengan derajat keluar 4 dan diameter k ¸ 4 tidak teratur masuk, maka graf berarah tersebut akan memiliki barisan derajat masuk: f3,3,3,3,4,...,4,4,5,5,5,5g, f3,3,3,3,4,...,4,4,4,5,5,6g, f3; 3; 3; 3; 4; :::; 4; 4; 4; 4; 6; 6g, f3; 3; 3; 3; 4; :::; 4; 4; 4; 5; 7g, f3; 3; 3; 3; 4; :::; 4; 4; 4; 4; 4; 8g. Setelah melakukan penelitian, peneliti membuk- tikan bahwa kelima barisan derajat masuk itu tidak mungkin terjadi. Sehingga dengan demikian dapat disimpulkan bahwa graf berarah kurang dua dari batas Moore dengan derajat keluar 4 dan diameter k ¸ 4 teratur.