DIMENSI PARTISI DARI GRAF KHUSUS DAN OPERASINYA

Abstract

Graf adalah salah satu pokok bahasan Matematika Diskrit yang telah lama dikenal dan banyak diaplikasikan pada berbagai bidang. Dalam merepresentasikan visual dari suatu graf yaitu dengan menyatakan objek dengan simpul, noktah, bulatan, titik, atau vertex, sedangkan hubungan antara objek dinyatakan dengan garis atau edge. Teori graf dapat digunakan untuk menyelesaikan beberapa permasalahan suatu bidang. Sebagai contoh, dalam permasalahan deadlock atau proses dalam sistem operasi yang tidak berjalan. Salah satu topik yang menarik pada teori graf adalah masalah dimensi partisi (partition dimension). Dimensi partisi sudah ada sejak tahun 1976 dengan jurnal On the metric dimension of the graph (Harary,et.al, 1976). Diantaranya dalam penelitian sebelumnya tentang dimensi partisi pada graf roda Wn oleh Tomaseu, I, Javaid, I, dan Slamin. Dalam menentukan nilai dimensi partisi dapat dilakukan dengan cara menentukan dimensi metrik terlebih dahulu. Secara umumnya dimensi metrik dari graf G atau dinotasikan dim(G) adalah menentukan banyaknya titik pada basis graf G, dimana basis merupakan himpunan pembeda yang mempunyai kardinalitas minimal. Sedangkan dimensi partisi dari graf G adalah menentukan nilai k minimum untuk k-partisi pembeda dari V (G). Untuk setiap vertek v dari graf terhubung dan sebuah subset S dari V (G), jarak antara v dan S adalah d(v, S)=min {d(v, x)|x ∈ S}. Beberapa keterangan di atas yang menerangkan konsep dimensi metrik dan dimensi partisi. Graf yang digunakan dalam penelitian fokus pada beberapa graf khusus dan operasinya, diantaranya yaitu: graf tangga Ln, graf shackle (C4, v, n), komplemen dari graf L¯n, graf komposisi Pn[P2], graf tangga tiga-siklus TCLn, dan graf tangga permata Dln. Metode yang digunakan dalam penelitian ini adalah metode pendeteksian pola (pattern recognition) dan deduktif aksiomatik. Pada pendektesian pola memiliki tujuan untuk menentukan nilai dimensi partisi (pd) dari sebuah kontruksi yang diawali mencari dimensi metrik (dim) dari masing-masing graf khusus dan operasinya. Dari hasil penelitian mengenai nilai dimensi metrik (dim) dan dimensi partisi (pd) pada graf khusus dan operasinya diperoleh sebagai berikut: 1. nilai dimensi metrik (dim) dari graf khusus dan operasinya diantaranya: - dimensi metrik graf tangga Ln dengan n ≥ 2 adalah 2, - dimensi metrik graf shackle (C4, v, n) adalah dim(shack(C4, v, n)) =   2; untuk n = 1 3; untuk n = 2 n; untuk n ≥ 3, - dimensi metrik graf komplemen L¯n dengan n ≥ 2 adalah 2, - dimensi metrik graf komposisi Pn[P2] dengan n ≥ 2 adalah dim(Pn[P2]) = ( 3; untuk n = 2 n; untuk n ≥ 3, - dimensi metrik graf tangga tiga-siklus TCLn adalah dim(TCLn) = ( 2; untuk 1 ≤ n ≤ 2 n; untuk n ≥ 3, - dimensi metrik graf tangga permata Dln dengan n ≥ 2 adalah ⌈3(n+1 2 )⌉−2. 2. nilai dimensi partisi (pd) dari graf khusus dan operasinya diantaranya: - dimensi partisi graf tangga Ln dengan n ≥ 2 adalah 3, - dimensi partisi graf shackle (C4, v, n) adalah pd(shack(C4, v, n)) =   3; untuk n = 1 4; untuk n = 2 n + 1; untuk n ≥ 3, - dimensi partisi graf komplemen L¯n dengan n ≥ 2 adalah 3, - dimensi partisi graf komposisi Pn[P2] dengan n ≥ 3 adalah pd(Pn[P2]) = ( 4; untuk n = 2 n + 1; untuk n ≥ 3, - dimensi partisi graf tangga tiga-siklus TCLn adalah pd(TCLn) = ( 3; untuk 1 ≤ n ≤ 2 n + 1; untuk n ≥ 3, - dimensi partisi graf tangga permata Dln dengan n ≥ 2 adalah ⌈3(n+1 2 )⌉−1; 3. nilai dimensi partisi (pd) memiliki kesamaan dari graf khusus dan operasinya akibat dari penambahan sisi pada graf khusus dan juga hasil operasinya, kecuali pada graf tangga permata Dln. Berikut kesamaan nilai dimensi partisi yang diperoleh: pd(Ln) = pd(L¯n) = 3, dengan n ≥ 2 pd(shack(C4, v, n)) = pd(Pn[P2]) = pd(TCLn) = n + 1, dengan n ≥ 3 pd(Dln) = ⌈3(n+1 2 )⌉ − 1, dengan n ≥ 2. Hasil penelitian ini diharapkan dapat memberikan konstribusi terhadap berkembangnya pengetahuan baru dalam bidang teori graf dan bisa digunakan sebagai acuan oleh peneliti lain untuk meneliti tentang dimensi metrik (dim) dan dimensi partisi (pd) untuk graf lainnya.