DOMINATING SET PADA HASIL OPERASI GRAF KHUSUS DAN APLIKASINYA

Abstract

Salah satu teori yang dikembangkan dalam teori graf adalah dominating set. Dominating set merupakan suatu konsep penentuan titik seminimal mungkin pada graf dengan ketentuan titik sebagai dominating set menjangkau titik yang ada di sekitarnya. Kardinalitas terkecil dari dominating set disebut domination number yang dinotasikan dengan (G). Saat ini dominating set tidak hanya diterapkan pada graf khusus saja, tetapi juga diterapkan pada hasil operasi graf. Operasi graf merupakan operasi terhadap dua buah graf atau lebih sehingga menghasilkan graf baru. Jenis-jenis operasi graf diantaranya operasi joint, cartesian product, crown product, tensor product, composition, shackle, dan amalgamation. Pada penelitian ini, peneliti akan mengembangkan teori dominating set pada hasil operasi graf khusus dan mengaplikasikan teori dominating set pada permainan catur, yaitu menentukan dominating set kuda pada papan catur berukuran 8 × 8. Dalam penelitian ini, peneliti menggunakan metode deduktif aksiomatik dalam menyelesaikan permasalahan. Metode deduktif aksiomatik merupakan metode penelitian yang menggunakan prinsip-prinsip pembuktian deduktif yang berlaku dalam logika matematika dengan menggunakan aksioma atau teorema yang telah ada untuk memecahkan suatu masalah. Tujuan dari penelitian ini adalah menentukan banyaknya titik (order ) dan banyaknya sisi (size) pada hasil operasi graf khusus, yaitu Pn + Fm, Cn + Lm, Cn ⊙ Lm, Pn ⊙ Fm, Pn[Km], Cn[Wm], Ln[Km], Pn[Btm], Shack (P2[Km], v = x1,k, r), dan Amal (Btn, v = x2, r); menentukan dominating set dan domination number pada hasil operasi graf khusus, yaitu G1 + G2, Pn + Fm, Cn + Lm, G1 ⊙ G2, Cn ⊙ Lm, Pn ⊙ Fm, G1[G2], Pn[Km], Cn[Wm], Ln[Km], Pn[Btm], Shack (P2[Km], v = x1,k, r), Amal (G, v = xi, r), dan Amal (Btn, v = x2, r); dan menentukan dominating set kuda pada papan catur berukuran 8×8.