Teori graf adalah cabang matematika yang berurusan dengan hubungan antar objek, direpresentasikan sebagai titik (vertices) dan sisi (edges). Konsep ini digunakan di berbagai bidang, mulai dari desain jaringan komputer hingga analisis sosial. Di tengah perkembangan teori graf, muncul dua konsep menarik: himpunan dominasi jarak  (distance domination) dan himpunan pembeda dominasi jarak  (distance resolving domination). Keduanya menjadi lebih kompleks ketika diterapkan pada operasi graf seperti operasi korona graf (corona product of graphs).

Sebagai ilustrasi dari konsep himpunan dominasi jarak (distance domination), terdapat suatu jaringan yang terdiri atas kota-kota  yang dihubungkan oleh jalan yang membentuk graf. Dalam jaringan ini, distance domination adalah cara untuk memilih sejumlah titik strategis sehingga setiap lokasi lain di jaringan berada dalam jarak maksimum dari titik-titik tersebut. Konsep ini sangat penting dalam pengelolaan sumber daya, seperti menentukan lokasi pusat layanan kesehatan atau stasiun pemadam kebakaran. Dalam graf , sebuah himpunan disebut sebagai himpunan dominasi jarak  yang disimbolkan dengan  jika setiap titik  memiliki jarak paling jauh sebanyak  dari setidaknya satu titik pada . Dalam aplikasi nyata, hal ini memungkinkan efisiensi pengelolaan jaringan besar karena memastikan setiap titik dalam graf dapat dijangkau dengan batas tertentu.

Sementara itu, distance resolving domination memperluas ide dominasi dengan menambahkan kemampuan membedakan lokasi. Selain memastikan semua titik berada dalam jangkauan, himpunan titik yang dipilih juga harus dapat membedakan setiap pasangan titik dalam graf berdasarkan jaraknya. Konsep ini berguna dalam navigasi robotik atau pengawasan jaringan, di mana identifikasi lokasi yang unik diperlukan. Secara formal, sebuah himpunan   disebut himpunan pembeda dominasi jarak  jika memenuhi dua kondisi: pertama,  adalah himpunan dominasi jarak , dan kedua, setiap titik  memiliki representasi jarak unik terhadap titik-titik pada . Representasi ini berupa vektor jarak, yang membuat titik-titik pada  dapat digunakan untuk identifikasi lokasi secara efektif.

Selain penjelasan mengenai konsep himpunan dominasi jarak  dan himpunan pembeda dominasi jarak , juga tak lupa penjelasan mengenasi hasil operasi korona pada dua graf. Operasi korona graf adalah hasil operasi antara dua graf  dan  yang dinotasikan dengan   . Setiap titik pada graf   dihubungkan dengan salinan lengkap dari graf . Struktur ini menciptakan jaringan yang lebih kompleks, dengan properti topologis unik. Sebagai contoh, jika  adalah graf lintasan dengan tiga titik () dan  adalah graf lingkaran (cycle) dengan empat titik , maka graf hasil operasi korona   akan membentuk jalur utama yang diikuti oleh empat titik baru yang terhubung pada setiap titik dari . Struktur semacam ini banyak ditemukan dalam desain jaringan komunikasi dan sistem distribusi.

Penerapan konsep himpunan dominasi jarak  dan himpunan pembeda dominasi jarak  pada graf hasil operasi korona menghadirkan tantangan unik. Kompleksitas struktur korona graf membuat perhitungan menjadi lebih rumit, tetapi juga membuka peluang untuk menemukan pola-pola baru yang dapat diterapkan secara luas. Keunikan pada graf hasil operasi korona ini dapat dilihat pada hasil-hasil penelitiannya pada himpunan dominasi jarak  dan himpunan pembeda dominasi jarak . Titik-titik yang menjadi himpunan dominasi jarak  terletak pada titik-titik anggota himpunan graf  sedangkan titik-titik yang menjadi himpunan pembeda dominasi jarak  terletak pada titik-titik anggota himpunan graf . Sehingga, untuk bilangan dominasi  jarak   pada graf   yaitu sebanyak kardinalitas titik pada graf . Sedangkan untuk banyaknya bilangan himpunan pembeda dominasi jarak  bergantung pada dimensi metrik dari graf  yang dipilih dikalikan sebanyak kardinalitas titik dari graf . Oleh karena itu, dapat dikatakan bahwa penelitian mengenai graf hasil operasi korona graf ini sangat menantang tetapi hasil yang didapatkan cukup sederhana. Dengan memahami konsep-konsep ini, kita tidak hanya mempelajari struktur graf yang kompleks tetapi juga memperluas aplikasi matematika untuk memecahkan masalah-masalah dunia nyata sehingga topik ini cukup menarik untuk digali lebih dalam.

Penulis: Prof. Dr. Liliek Susilowati, S.Si., M.Si.

Fakultas Sains dan Teknologi, Universitas Airlangga
Artikel lengkap dengan judul:

“ Distance Domination And Resolving Domination Of The Corona Product Of Graphs.”

Dapat diakses melalui laman: http://www.iapress.org/index.php/soic/article/view/2101/1175