Pada graf dikenal dua istilah himpunan, yaitu himpunan titik dan himpunan garis. Pada graf, titik menggambarkan obyek yang dikaji dan garis menyatakan hubungan antar obyek yang dikaji. Himpunan bagian dari himpunan titik pada suatu graf disebut sebagai himpunan pembeda pada suatu graf, jika representasi setiap titik pada graf berbeda terhadap himpunan pembeda tersebut. Adapun yang dimaksud dengan representasi suatu titik terhadap suatu himpunan berkardinalitas adalah pasangan berurutan elemen, dimana elemen tersebut yang berupa jarak antar suatu titik dengan setiap elemen pada himpunan tersebut. Dimensi metrik lokal dominasi adalah kardinalitas minimum dari suatu himpunan titik pada memenuhi dua kondisi, yang pertama adalah setiap dua titik yang bertetangga pada graf tersebut mempunyai representasi yang berbeda terhadap himpunan titik tersebut, yang kedua adalah setiap titik pada graf yang bukan anggota himpunan tersebut bertetangga dengan minimal satu titik pada himpunan tersebut.
Artikel ini membahas tentang sifat-sifat dimensi metrik lokal dominasi pada graf. Pada bagian awal disajikan bilangan dominasi beberapa graf khusus yang sudah ditemukan oleh Chartrand dkk pada tahun 2000. Hasil ini mendukung hasil utama pada penelitian ini. Pada bagian pembahasan, diawali dengan menyajikan definisi utama, yaitu dimensi metrik lokal dominasi dan disajikan contoh untuk memudahkan pembaca memahami definisi utama ini. Selanjutnya definisi utama ini diimplementasikan pada beberapa graf khusus. Graf khusus yang digunakan pada penelitian ini antara lain adalah graf bintang, graf lengkap, graf lintasan, dan graf siklus.
Dua hasil berkaitan dengan sifat himpunan pembeda disajikan untuk memudahkan pembuktian hasil selanjutnya. Batas atas dan batas bawah dari dimensi metrik lokal dominasi juga berhasil ditemukan. Hasil besar yang diperoleh dalam penelitian ini adalah karakterisasi graf dengan dimensi metrik lokal dominasi tertentu, yaitu dimensi metrik lokal dominasi suatu graf adalah satu jika hanya jika graf tersebut merupakan graf bintang. Sedangkan dimensi metrik lokal dominasi suatu graf adalah sama dengan ordo graf minus satu jika hanya jika graf tersebut merupakan graf lengkap. Untuk mencapai karakterisasi graf dengan dimensi metrik lokal dominasi tertentu di atas, terlebih dulu diselidiki himpunan dominasi dari graf lintasan dan graf siklus, yang dilanjutkan dengan menyajikan dimensi metrik lokal dominasinya. Sebagai hasil tambahan, disajikan dimensi metrik lokal dominasi dari graf bipartite lengkap, yang nilainya sama dengan bilangan dominasinya.
Penelitian dimensi metrik secara umum, merupakan kasus yang tingkat kompleksitasnya tinggi, utamanya jika ordo grafnya besar. Terlebih lagi untuk dimensi metrik dominasi atau dimensi metrik lokal dominasi. Oleh karena itu, untuk menyelesaikan masalah dimensi metrik sangat membutuhkan program komputasi. Kolaborasi keilmuan bidang matematika, khususnya teori graf dengan teknik informatika merupakan suatu keniscayaan agar memperoleh hasil penelitian yang tepat guna.
Definisi-definisi dari graf yang digunakan pada penelitian ini tidak disajikan secara eksplisit, karena sudah dianggap istilah biasa pada pembahasan teori graf. Hasil secara lebih detil beserta pembuktiannya dapat dilihat langsung pada artikel asli yang dipublikasikan pada jurnal STATISTICS, OPTIMIZATION AND INFORMATION COMPUTING, Vol. 12, Nopember 2024, pp 1912-1920, yang dapat diakses melalui laman yang tertera di bawah ini.
Penulis: Dr. Liliek Susilowati, S.Si., M.Si.
Fakultas Sains dan Teknologi, 51动漫
Artikel lengkap dapat diakses melalui laman:
