Perpustakaan Digital ITB

Konsep pelabelan tak teratur (irregularity strength) dari suatu graf pertama kali diperkenalkan oleh Chartrand dkk. (1988). Ide tersebut menjadi inspirasi bagi Ba?ca dkk. (2007) untuk mengusulkan konsep pelabelan total tak-teratur. Ba?ca dkk. (2007) mendefinisikan pelabelan-k total tak-teratur titik dari suatu graf G(V,E) sebagai suatu pemetaan ! : V [ E ! {1, 2, 3, · · · , k} sedemikian sehingga bobot dari setiap titik di G berbeda. Bobot sebarang titik x dihitung dengan wt(x) = !(x) + P xy2E(G) !(xy). Nilai total ketakteraturan titik atau total vertex irregularity strength dari suatu graf G, dilambangkan dengan tvs(G), merupakan suatu bilangan bulat positif terkecil k sedemikian sehingga G memiliki pelabelan-k total tak-teratur titik. Nurdin dkk. (2010) secara umum memberikan batas bawah nilai total ketakteraturan titik untuk sebarang graf G yang memiliki derajat minimum " dan derajat maksimum ! sebagai berikut: tvs(G) # max (? " + n! " + 1 ? , ? " + n! + n!+1 " + 2 ? , · · · , & " + P tetapi, penentuan nilai total ketakteraturan titik untuk graf kubik secara umum masih merupakan permasalahan terbuka. Fokus dari penelitian ini adalah mengkaji cara menghitung nilai total ketakteraturan titik untuk graf kubik. Teknik pelabelan untuk memperoleh suatu pelabelank total tak-teratur titik diberikan dalam suatu algoritma. Sebagian besar metoda penentuan nilai total ketakteraturan titik sebelumnya bekerja berdasarkan karakteristik kelas graf yang dikaji. Sedangkan, algoritma yang diusulkan bekerja berdasarkan cara mengurutkan titik dan memberikan bobotnya pada suatu graf. Metode yang digunakan dalam pengurutan titik adalah (Bread-First Search/BFS). Selain itu, mekanisme dalam melabeli sisi dan titik merupakan bagian penting dari penelitian ini. Graf yang dijadikan objek penelitian termasuk ke dalam graf kubik, yakni graf prisma, beberapa graf platonik (tetrahedron, kubus, dan dodekahedron), graf simetris kubik hasil sensus oleh Foster, dan graf permutasi (keluarga graf pagar dan burger). Algoritma yang diajukan dan diterapkan pada graf kubik tersebut menghasilkan pelabelan-k total tak-teratur titik. Selain itu, label sisi dan titik terbesar yang dihasilkan dari pelabelan tersebut nilainya sama dengan batas bawah yang telah diajukan oleh Nurdin dkk. (2010). Artinya bahwa label sisi dan titik terbesarnya sama dengan nilai total ketakteraturan titik dari graf kubik tersebut. Hasil penelitian ini sekaligus membuktikan kebenaran dari konjektur yang diberikan oleh Nurdin dkk. (2010). Dengan demikian, penelitian ini menghasilkan teknik yang seragam dalam menentukan nilai total ketakteraturan titik pada graf kubik.