| dc.description.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. | en_US |
