Dimensi Metrik dan Bi-Metrik Graf Dumbbel

Abstract

Dimensi metrik pertama kali diperkenalkan oleh Harary dan Melter pada tahun 1976 dalam artikel yang berjudul ”On the Metric Dimension of Graph”. Dalam artikel tersebut dibahas tentang himpunan pembeda. Misalkan 𝐺 adalah graf dengan himpunan titik 𝑉(𝐺) dan himpunan sisi 𝐸(𝐺), jarak antara titik 𝑢 dan 𝑣 di 𝐺 yaitu panjang lintasan terpendek dari 𝑢 ke 𝑣. Jika representasi titik 𝑢 dan 𝑣 di 𝐺 berbeda maka disebut dengan himpunan pembeda 𝑆. Kajian tentang dimensi metrik memunculkan suatu gagasan baru yaitu dimensi bi-metrik. Dimensi bimetrik diperkenalkan oleh Raghavendra, Sooryanarayana, dan Chandru Hegde pada tahun 2014 dalam artikel yang berjudul “Bi-Metric Dimension of Graphs”. Perbedaan dimensi metrik dan bi-metrik terletak pada penentuan representasi setiap titik pada graf 𝐺. Dimensi metrik merepresentasikan setiap titiknya berupa jarak, sedangkan dimensi bi-metrik merepresentasikan setiap titiknya berupa pasangan terurut jarak dan detour. Detour merupakan panjang lintasan terpanjang dari 𝑢 ke 𝑣 di 𝐺. Penelitian ini membahas tentang dimensi metrik dan bi-metrik graf dumbbell. Graf dumbbell adalah graf yang dibentuk dari 2 graf cycle 𝐶𝑚 dan 𝐶𝑛 yang dihubungkan oleh suatu graf lintasan 𝑃𝑞, dengan titik-titik ujung dari graf lintasan 𝑃𝑞 adalah salah satu titik dari masing-masing graf cycle (Wang et al, 2010). Graf dumbbell dinotasikan dengan 𝐷𝑚,𝑛,𝑞, dengan 𝑚, 𝑛 ≥ 3 menyatakan banyaknya titik pada kedua graf cycle dan 𝑞 ≥ 2 menyatakan banyaknya titik pada graf lintasan. Metode yang digunakan dalam penelitian ini adalah metode pendeteksian pola dan metode deduktif aksiomatik. Penentuan dimensi metrik dan bi-metrik diawali dengan menotasikan setiap titik pada graf dumbbell, memilih himpunan pembeda 𝑆 dengan 𝑆 ⊆ 𝑉(𝐷𝑚,𝑛,𝑞), lalu merepresentasikan setiap titik pada graf dumbbell terhadap 𝑆, apabila representasi setiap titik berbeda, maka diperoleh himpunan pembeda, tetapi jika terdapat representasi titik yang sama maka dilakukan pemilihan himpunan pembeda yang lain. Kardinalitas minimum dari himpunan pembeda merupakan dimensi metrik dan bi-metrik pada graf dumbbell. Pada penelitian ini, diperoleh dimensi metrik pada graf dumbbell 𝐷𝑚,𝑛,𝑞 = 2, dimensi metrik pada graf dumbbell 𝐷2𝑚,𝑛,𝑞 = 2 untuk 𝑚 dan 𝑛 ganjil dan dimensi metrik pada graf dumbbell 𝐷2𝑚,𝑛,𝑞 = 3 untuk 𝑚 dan 𝑛 genap. Sedangkan dimensi bi-metrik pada graf dumbbell 𝐷𝑚,𝑛,𝑞 = 2, dimensi bi-metrik pada graf dumbbell 𝐷2𝑚,𝑛,𝑞 = 2 untuk 𝑚 dan 𝑛 ganjil dan dimensi bi-metrik pada graf dumbbell 𝐷2𝑚,𝑛,𝑞 = 3 untuk 𝑚 dan 𝑛 genap. Sehingga dapat disimpulkan bahwa nilai dimensi metrik pada graf dumbbell sama dengan nilai dimensi bi-metriknya.