KETERATURAN GRAF BERARAH DERAJAT KELUAR TIGA DENGAN ORDO KURANG DUA DARI BATAS MOORE

Abstract

Dengan pesatnya perkembangan teknologi informasi, kebutuhan akan rancangan jaringan komunikasi yang besar menjadi meningkat. Jaringan komunikasi dapat dimodelkan sebagai graf atau graf berarah dengan asumsi tiap elemen pemroses pada jaringan direpresentasikan sebagai titik dan koneksi di antara dua elemen pemroses direpresentasikan sebagai sisi atau sisi berarah (pada kasus koneksi berarah). Ada dua parameter yang mempengaruhi ordo (jumlah titik) dari graf atau graf berarah, yaitu derajat dan diameter. Derajat adalah jumlah koneksi suatu titik pada graf atau graf berarah. Diameter adalah jarak terjauh di antara sebarang dua titik. Pada kasus graf berarah, derajat sebuah titik dibedakan menjadi derajat keluar dan derajat masuk. Derajat keluar adalah jumlah koneksi yang meninggalkan sebuah titik, sedangkan derajat masuk adalah jumlah koneksi yang menuju suatu titik. Semakin besar derajat keluar atau diameter graf berarah, maka semakin besar jumlah titik yang dapat diraih. Oleh karena itu, persoalan bagaimana merancang jaringan berarah (jaringan dengan koneksi berarah) dengan skala besar adalah mencari berapa ukuran maksimal graf berarah dengan diberikan derajat keluar dan diameter tertentu yang lebih dikenal dengan sebutan n d;k problem. Interval n (ordo graf berarah dengan derajat keluar dan diameter tertentu) dibatasi oleh batas atas Moore (M d;k d;k ) yang besarnya 1+d+d dengan asumsi graf berarah yang dibicarakan adalah graf berarah dengan derajat keluar sama untuk setiap titiknya. 2 +: : : +d k Salah satu upaya mendapatkan besar n yang optimal dan mungkin untuk dicapai adalah dengan mereduksi besarnya batas atas Moore atau membuktikan ketiadaan graf berarah dengan ordo mendekati atau sama dengan batas Moore. Namun, ada dua kemungkinan bagi keberadaan graf berarah, yaitu diregular (sebarang dua titik pada graf berarah memiliki derajat masuk sama dengan derajat keluar) dan non-diregular (ada titik pada graf berarah yang memiliki derajat masuk tidak sama dengan derajat keluar). Skripsi ini memberikan pembuktian bahwa graf berarah dengan derajat keluar d = 3; diameter k ¸ 3; dan ordo M 3;k d;k ¡ 2 adalah diregular. Manfaat dari hasil penelitian ini adalah dihasilkannya jaminan tentang kete- raturan dari graf berarah dengan derajat keluar d = 3; diameter k ¸ 3; dan ordo M ¡2. Kriteria keteraturan ini selanjutnya akan digunakan untuk membuktikan ketiadaan graf berarah. 3;k