Dimensi Metrik dan Dimensi Partisi pada Graf Hasil Operasi Comb dari Graf Lingkaran dan Graf Bintang Berorde Empat

Abstract

Teori graf adalah struktur matematika yang digunakan untuk memodelkan suatu objek dengan representasi titik dan garis. Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun 1736. Menurut Hartsfield dan Ringel (1990), graf didefinisikan sebagai pasangan himpunan (𝑉, 𝐸), dengan 𝑉 sebagai himpunan tak kosong dari titik (vertex) dan 𝐸 sebagai himpunan sisi (edge) yang menghubungkan sepasang titik. Untuk himpunan terurut 𝑊 = {𝑤1, 𝑤2, 𝑤3, … , 𝑤𝑛} dari himpunan titik di graf terhubung 𝐺 dan sebuah titik 𝑣 di 𝐺, k-tuple terurut 𝑟(𝑣|𝑊) = (𝑑(𝑣, 𝑤1), 𝑑(𝑣, 𝑤2), … , 𝑑(𝑣, 𝑤𝑘)). Dimensi partisi dapat dimisalkan dalam sebuah graf terhubung 𝐺 dengan 𝑣 ∈ 𝑉(𝐺) dan 𝑆 adalah himpunan bagian dari 𝑉(𝐺). Jarak antara 𝑣 dengan 𝑆 dinotasikan dengan 𝑑(𝑣, 𝑆). Partisi sebuah himpunan dikatakan partisi pembeda jika 𝑟(𝑣|Π) untuk setiap 𝑣 ∈ 𝑉(𝐺) berbeda. Nilai minimum 𝑘 sedemikian sehingga 𝑆1, 𝑆2, … , 𝑆𝑘 merupakan partisi pembeda disebut dimensi partisi dari 𝐺 yang dinotasikan dengan 𝑝𝑑(𝐺). Penelitian terkait dimensi metrik dan dimensi partisi ini dilakukan dengan mencari hasil dimensi metrik dan partisi dari salah satu graf yaitu graf 𝐶𝑛 ⊵ 𝑆4. Graf 𝐶𝑛 ⊵ 𝑆4 merupakan graf yang terbentuk dari operasi comb titik graf lingkaran dan graf bintang. Graf 𝐶𝑛 ⊵ 𝑆4 merupakan graf yang dibentuk dengan menambahkan satu salinan dari graf bintang pada setiap titik di graf lingkaran. Graf 𝐶𝑛 ⊵ 𝑆4 terdiri dari graf lingkaran dengan banyak titik 𝑛 dan graf bintang dengan banyak titik 4. Graf 𝐶𝑛 ⊵ 𝑆4 belum pernah dikaji sebelumnya. Metode penelitian yang digunakan pada penelitian ini adalah menggunakan metode pendeteksian pola dan deduktif aksiomatik. Metode ini berfungsi untuk mencari pola dalam mengonstruksi himpunan pembeda dari dimensi metrik dan dimensi partisi pada graf 𝐶𝑛 ⊵ 𝑆4 sedemikian sehingga ditemukan nilai pembeda minimum dan representasi titik yang berbeda. Berdasarkan hasil dan pembahasan pada penelitian ini, dapat disimpulkan bahwa hasil dimensi metrik dan dimensi partisi dari graf 𝐶𝑛 ⊵ 𝑆4 adalah 𝑑𝑖𝑚(𝐶𝑛 ⊵ 𝑆4) = 𝑛 dan 𝑝𝑑(𝐶𝑛 ⊵ 𝑆4) = 3 untuk 𝑛 = 3, 4, 𝑝𝑑(𝐶𝑛 ⊵ 𝑆4) = 4 untuk 5 ≤ 𝑛 ≤ 14.