Seiring dengan semakin kompleksnya kehidupan manusia dari sisi sarana dan prasarana kehidupan, maka semakin pesat pula perkembangan sains dan teknologi untuk mencapainya. Matematika mempunyai peran yang sangat besar dalam perkembangan sains dan teknologi. Salah satunya adalah teori graf sebagai bagian dari matematika yang mempunyai peran untuk menyelesaikan permasalahan yang bersifat diskrit. Sebagai makhluk sosial dan berakal, manusia terus menuntut adanya perkembangan dalam sarana maupun prasarana untuk menujang semua aktivitasnya. Peran matematika sangat besar dalam mencapai perkembangan sarana dan prasarana ini, yaitu untuk mendapatkan sarana dan prasarana yang optimal, efektif dan efisien. Oleh karena itu, mengembangkan konsep matematika untuk memenuhi tuntutan zaman juga sangat diperlukan. Salah satu perkembangan dalam matematika yang dikaji dalam artikel ini adalah tentang dimensi metrik dalam graf.
Teori graf merupakan teori yang mengkaji suatu susunan yang terdiri atas titik dan garis, dimana garis menyatakan hubungan antar dua titik. Sedangkan dimensi metrik menyatakan kardinalitas minimal suatu himpunan titik pada graf, dimana himpunan tersebut dapat membedakan setiap titik yang ada pada graf tersebut. Berbagai masalah dapat diselesaikan dengan konsep dimensi metrik ini, antara lain masalah jaringan elektrik, menyusun isomer kimia organic, dan navigasi robot yang medan geraknya berupa graf. Selanjutnya muncul permasalahan lain dalam graf yang tidak dapat diselesaikan dengan menggunakan konsep dimensi metrik, tetapi membutuhkan konsep yang berkebalikan dengan konsep dimensi metrik. Oleh karena itu Susilowati dkk. Membangun konsep dimensi metrik komplemen untuk menyelesaikan permasalahan yang diilustrasikan sebagai berikut. Misalkan terdapat perusahaan yang akan menjalankan suatu proyek besar, maka diperlukan adanya pimpinan proyek. Dalam pemilihan pemimpin tim proyek di suatu perusahaan, minimal terdapat dua orang calon pemimpin dari perusahaan yang memiliki pandangan yang sama terhadap anggota tim proyek, dalam artian mengetahui bidang keahlian. Dengan adanya minimal dua orang calon pemimpin ini diharapkan jika suatu saat pemimpin mengalami suatu kendala maka terdapat pemimpin pengganti yang dapat memimpin proyek. Karena dua calon pemimpin memiliki pandangan yang sama terhadap tim yang dipimpin maka kebijakan yang diambil oleh pemimpin pengganti tidak akan berbeda dari pemimpin sebelumnya, sehingga proyek tersebut akan tetap berjalan dengan lancar walaupun ada pergantian pemimpin proyek.
Dalam konsep ini, tim proyek digambarkan dengan titik dalam graf. Apabila anggota tim saling mengenal maka titiknya dihubungkan dengan garis. Anggota tim proyek digambarkan dengan himpunan pembeda komplemen sedangkan dua orang calon pemimpin digambarkan dengan dua titik yang memiliki pandangan/representasi yang sama terhadap himpunan pembeda komplemen. Dimensi metrik komplemen menyatakan kardinalitas maksimal dari himpunan pembeda komplemen. Baik dimensi metrik atau dimensi metrik komplemen, keduanya berfungsi untuk menyelesaikan masalah optimasi, yaitu masalah maksimasi dan masalah minimasi. Dalam artikel ini dikaji dimensi metrik komplemen pada graf hasil operasi join. Graf hasil operasi join diperoleh dari dua graf yang masing masing struktur dua graf penyusunnya dipertahankan dan ditambah dengan menghubungkan setiap titik pada graf pertama dengan semua titik pada graf kedua. Graf yang dilibatkan dalam artikel ini adalah graf lengkap, graf lintasan, graf bintang, dan graf siklus. Graf lengkap adalah graf yang setiap dua titiknya membentuk garis, graf lintasan adalah graf semua titiknya membentuk garis dengan dua titik yang lain, kecuali dua titik yang hanya membentuk garis dengan satu titik saja. Graf bintang adalah graf yang memuat tepat satu titik yang membentuk garis dengan semua titik yang lain dan titik lainnya hanya bertetangga dengan titik tersebut. Sedangkan graf siklus adalah graf yang setiap titiknya membentuk garis dengan dua titik yang lain.
Dari hasil pengamatan yang sudah ditunjukkan kebenarannya secara matematika, diperoleh hasil bahwa beberapa dimensi metrik komplemen graf hasil operasi join adalah banyaknya titik pada salah satu graf penyusunnya ditambah dengan dimensi metrik komplemen graf penyusunnya yang lain. Namun ada juga graf hasil operasi join yang dimensi metrik komplemennya tidak memenuhi sifat di atas. Dari hasil yang diperoleh, ditemukan syarat graf yang dioperasikan agar diperoleh graf hasil operasi join yang dimensi matriksnya memenuhi sifat di atas. Syaratnya adalah salah satu graf yang dioperasikan adalah yang mempunyai dimensi metrik komplemen maksimal, dimana dimensi metrik komplemen maksimal pada suatu graf adalah banyaknya titik dikurangi dua. Hasil lebih detailnya, dapat dilihat pada artikel lengkap.
Penulis: Dr. Liliek Susilowati, S.Si., M.Si.
Artikel lengkap dengan judul: “The complement metric dimension of the joint graph”
Dapat diakses melalui laman: https://aip.scitation.org/doi/pdf/10.1063/5.0042149
