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

Abstract

Graf merupakan salah satu cabang matematika yang penting dan banyak manfaatnya. Topologi sebuah jaringan merupakan salah satu dari sekian banyak contoh yang dapat dimodelkan dengan graf. Seiring dengan beragam permasalahan yang muncul dalam perancangan sebuah jaringan berskala besar, maka hal ini juga berdampak bagi pengembangan teori graf, salah satunya 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 out-degree, 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 out-degree d = 3 dan diameter k ¸ 4 atau out-degree d ¸ 4 dan diameter k ¸ 3 masih belum diketahui dan merupakan masalah terbuka. Dalam penelitian ini, peneliti telah melakukan penelitian terhadap keteraturan graf berarah kurang dua dari batas Moore dengan out-degree 4 dan diameter 3 dengan hasil akhir bahwa graf berarah tersebut adalah diregular(teratur). Dalam melakukan penelitian tersebut, peneliti menggunakan metode deduktif, induktif, dan brute force. Untuk mengetahui keteraturan dari graf berarah, pembahasannya harus ditinjau dari dua aspek yaitu bagaimanakah out-regularitynya dan bagaimanakah in-regularitynya. Jika suatu graf berarah dinyatakan in-regular (teratur masuk) dan out-regular (teratur keluar), maka graf berarah tersebut dapat dinyatakan sebagai graf berarah diregular. Peneliti lain telah membuktikan bahwa graf berarah dengan out-degree d ¸ 2 dan di-ameter k ¸ 2 adalah out-regular. Sedangkan untuk mengetahui suatu graf berarah adalah in-regular, maka harus dibuktikan bahwa barisan - barisan indegree dari graf berarah tersebut tidak mungkin ada. Dalam mempelajari in-regularity dari graf berarah, pembahasannya dimulai dengan mengasumsikan bahwa graf berarah tersebut tidak in-reguler. Jika suatu graf berarah tidak in-regular maka graf berarah tersebut pasti memiliki barisan in-degree. Sehingga, jika graf berarah kurang dua dari batas Moore dengan out-degree 4 dan diameter 3 tidak in-reguler, maka graf berarah tersebut akan memiliki salah satu dari barisan in-degree: 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 membuktikan bahwa kelima barisan in-degree itu tidak ada. Sehingga dengan demikian dapat disimpulkan bahwa graf berarah kurang dua dari batas Moore dengan out-degree 4 dan diameter 3 adalah diregular.