DIMENSI PARTISI DARI GRAF KHUSUS DAN OPERASINYA

Abstract

Dimensi partisi dari graf khusus dan operasinya; Ilham Saifudin, S.Pd, 131820101004; 2015: 52 halaman; Jurusan Matematika; Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jember. 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 Ln, graf komposisi Pn[P1], graf tangga tigasiklus 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 v 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 dengan n ≥ 3 adalah k, dimensi metrik graf komplemen Ln dengan n ≥ 2 adalah 2, dimensi metrik graf komposisi Pn[P1] dengan n ≥ 3 adalah k, dimensi metrik graf tangga tiga-siklus TCLn dengan n ≥ 3 adalah k, dimensi metrik graf tangga permata Dln dengan n ≥ 2 adalah ⌈3(n+1 2 )⌉ − 2. Sedangkan 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 dengan n ≥ 3 adalah k + 1, dimensi partisi graf komplemen Ln dengan n ≥ 2 adalah 3, dimensi partisi graf komposisi Pn[P1] dengan n ≥ 3 adalah k + 1, dimensi partisi graf tangga tiga-siklus TCLn dengan n ≥ 3 adalah k + 1, dimensi partisi graf tangga permata Dln dengan n ≥ 2 adalah ⌈3(n+1 2 )⌉ − 1. 2. 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(Ln) = 3 pd(C4, v, n) = pd(Pn[P1]) = pd(TCLn) = k + 1 pd(Dln) = ⌈3(n+1 2 )⌉ − 1 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.