MENGHITUNG BILANGAN DOMINASI

MENGHITUNG BILANGAN DOMINASI PADA GRAPH GRID 𝑛 × 𝑛, 𝑛 ≤ 7 Mucharomatut Toyyibah 1) Purwanto 2) FMIPA Universitas Negeri Malang [email protected]

Abstrak: Himpunan pendominasi ialah suatu himpunan bagian 𝑉′ dari himpunan titik 𝑉(𝐺) dimana titik-titik yang tidak berada pada 𝑉′ terhubung langsung dengan minimal satu titik pada 𝑉′. Ukuran dari himpunan pendominasi terkecil disebut bilangan dominasi. Bilangan dominasi pada graph 𝐺 dinotasikan dengan 𝛾(𝐺) dan bilangan dominasi pada graph grid 𝐺𝑛×𝑛 dinotasikan dengan 𝛾𝑛,𝑛 . Graph grid adalah graph yang merupakan hasil kali cartesius dari graph lintasan 𝑃𝑚 × 𝑃𝑛 atau jika dituliskan dalam notasi pembentuk himpunan maka 𝑉 𝑃𝑚 × 𝑃𝑛 = {(𝑣𝑖 , 𝑤𝑗 )|𝑣𝑖 ∈ 𝑃𝑚 , 𝑤𝑗 ∈ 𝑃𝑛 }. Graph grid dengan 𝑚 × 𝑛 titik dinotasikan dengan 𝐺𝑚 ,𝑛 . Pada tulisan ini dibahas pencarian himpunan pendominasi minimum dan bilangan dominasi menggunakan algoritma BFS (breadth-first search) dengan ciri khas algoritma pemrograman dinamis kemudian diperiksa hasil yang diperoleh dengan penelitian sebelumnya. Kata Kunci: graph grid, himpunan pendominasi, bilangan dominasi, algoritma BFS (breadth-first search), algoritma pemrograman dinamis.

Suatu permasalahan akan semakin mudah dipelajari, dipahami dan diselesaikan jika dibawa ke model matematika. Setelah model matematikanya diketahui, maka masalah tersebut akan dipilah-pilah ke dalam cabang-cabang ilmu matematika. Salah satu cabang ilmu matematika yang bermanfaat dalam menyelesaikan suatu permasalahan tersebut adalah teori graph. Salah satu topik yang dibahas dalam teori graph ialah himpunan pendominasi (dominating set). Himpunan pendominasi ialah suatu himpunan bagian 𝑉′ dari himpunan titik 𝑉(𝐺) dimana titik-titik yang tidak berada pada 𝑉′ terhubung langsung dengan minimal satu titik pada 𝑉′. Ukuran terkecil dari himpunan pendominasi disebut bilangan dominasi (domination number) dilambangkan dengan 𝛾(𝐺). (Alanko dkk, 2011). Banyak manfaat bilangan dominasi dan himpunan pendominasi dalam kehidupan sehari-hari. Seperti disebutkan dalam Haynes, Hedetniemi, dan Slater (1998:21) diantaranya dalam rute bus sekolah. Sebagian besar rute bus sekolah beroperasi berdasarkan aturan tertentu. Biasanya aturan tersebut berupaya agar setiap anak berjalan tidak jauh ke tempat pemberhentian bus. Dalam kasus ini permasalahanya di titik-titik mana saja pemberhentian bus ditentukan agar setiap anak berjalan tidak jauh ke pemberhentian tersebut. Dari Beineke dan Wilson (2004:5) hasil kali cartesius (Cartesian product) 𝐺 □ 𝐻 atau 𝐺 × 𝐻 memiliki himpunan titik 𝑉(𝐺) × 𝑉(𝐻) atau jika ditulis dalam notasi pembentuk himpunan diperoleh 𝑉 𝐺 × 𝐻 = {(𝑣𝑖 , 𝑤𝑗 )|𝑣𝑖 ∈ 𝐺, 𝑤𝑗 ∈ 𝐻} dan (𝑣𝑖 , 𝑤𝑗 ) terhubung langsung ke (𝑣ℎ , 𝑤𝑘 ) jika salah satu dari berikut ini terpenuhi a) 𝑣𝑖 terhubung langsung ke 𝑣ℎ pada G dan 𝑤𝑗 = 𝑤𝑘 , atau b) 𝑣𝑖 = 𝑣ℎ dan 𝑤𝑗 terhubung langsung ke 𝑤𝑘 pada H 1) Mucharomatut T. adalah mahasiswa Jurursan Matematika FMIPA Universitas Negeri Malang 2) Purwanto adalah dosen Jurursan Matematika FMIPA Universitas Negeri Malang

1

Dalam bentuk yang kurang formal, 𝐺 □ 𝐻 dapat diperoleh dengan mengambil 𝑛 −salinan dari H dan menghubungkan titik-titik yang berkorespondensi pada salinan berbeda jika ada suatu sisi di G. Menurut Weisstein, graph grid adalah graph yang merupakan hasil kali cartesius dari graph lintasan 𝑃𝑚 × 𝑃𝑛 atau jika dituliskan dalam notasi pembentuk himpunan maka 𝑉 𝑃𝑚 × 𝑃𝑛 = {(𝑣𝑖 , 𝑤𝑗 )|𝑣𝑖 ∈ 𝑃𝑚 , 𝑤𝑗 ∈ 𝑃𝑛 }. Graph grid dengan 𝑚 × 𝑛 titik dinotasikan dengan 𝐺𝑚 ,𝑛 . Didefinisikan beberapa notasi yang sering digunakan baik pada teorema maupun algoritma pencarian himpunan pendominasi dan bilangan dominasi. Seperti pada Alanko, dkk (2011) untuk suatu titik 𝑣 ∈ 𝑉, himpunan titik-titik yang didominasi oleh 𝑣 dinotasikan dengan 𝐷(𝑣). Untuk suatu himpunan 𝑉′ ⊆ 𝑉, himpunan titik-titik yang didominasi oleh (titik-titik pada) 𝑉′ dinotasikan dengan 𝐷(𝑉′). Untuk suatu himpunan 𝑆 ⊆ 𝑉, titik dengan urutan leksikografis terkecil pada 𝑉\𝑆 dinotasikan dengan 𝑠(𝑆). Urutan leksikografis artinya 𝑣𝑖,𝑗 lebih kecil dari 𝑣𝑘,𝑙 jika 𝑖 < 𝑘 atau jika 𝑖 = 𝑘 dan 𝑗 < 𝑙. Beberapa penelitian telah dilakukan dalam menentukan bilangan dominasi pada graph grid seperti disebutkan dalam Chang, Clark, dan Hare (1995). Hasil dari penelitian tersebut digunakan untuk mengecek hasil pencarian dengan algoritma apakah sudah sesuai dengan perhitungan rumus umum, diantaranya sebagai berikut : 𝑛+2 a) 𝛾1,𝑛 = 3

b) 𝛾2,𝑛 = c) 𝛾3,𝑛 = d) 𝛾4,𝑛 =

𝑛+2 2 3𝑛+4 4

𝑛 + 1, 𝑛 = 1,2,3,5,6,9 𝑛, 𝑛 𝑙𝑎𝑖𝑛𝑦𝑎 6𝑛+6

e) 𝛾5,𝑛 =

5 6𝑛+8 5

, 𝑛 = 2,3,7 , 𝑛 𝑙𝑎𝑖𝑛𝑦𝑎

10𝑛+10

f) 𝛾6,𝑛 =

7 10𝑛+12 7

g) 𝛾7,𝑛 = h) 𝛾8,𝑛 = i) 𝛾9,𝑛 =

, 𝑛 𝑙𝑎𝑖𝑛𝑦𝑎 𝑗𝑖𝑘𝑎 𝑛 ≥ 4

5𝑛+3 3 15𝑛+14 8 23𝑛+20 11 30𝑛+37

j) 𝛾10,𝑛 =

, 𝑛 ≥ 6 𝑑𝑎𝑛 𝑛 ≡ 1 (𝑚𝑜𝑑 7)

13 30𝑛+24 13

, 𝑛 ≡ 0 𝑎𝑡𝑎𝑢 3 (𝑚𝑜𝑑 13) 𝑑𝑎𝑛 𝑛 ≠ 13,16 , 𝑛 𝑙𝑎𝑖𝑛𝑦𝑎 𝑢𝑛𝑡𝑢𝑘 10 ≤ 𝑛 ≤ 125

2

HASIL DAN PEMBAHASAN Berikut ini dijelaskan beberapa teorema yang diambil dari Alanko, dkk (2011) yang akan digunakan untuk membentuk algoritma dalam mencari himpunan pemdominasi minimum pada graph grid 𝐺𝑛 ×𝑛 = (𝑉, 𝐸). Teorema 1 Perhatikan suatu graph grid 𝐺𝑛×𝑛 = 𝑉, 𝐸 , dan misalkan 𝑉1 ⊆ 𝑉 dan 𝑉2 ⊆ 𝑉 sedemikian sehingga 𝑉1 = 𝑉2 dan 𝐷(𝑉1 ) ⊆ 𝐷(𝑉2 ). Untuk mencari himpunan pendominasi minimum dari 𝐺, boleh mengabaikan 𝑉1 dan hanya memperhatikan himpunan pendominasi yang dibuat dari 𝑉2 . Bukti : Untuk sebarang 𝑉3 ⊆ 𝑉 maka 𝑉1 ∪ 𝑉3 merupakan suatu himpunan pendominasi dari 𝐺. Karena 𝐷(𝑉1 ) ⊆ 𝐷(𝑉2 ) maka 𝑉2 ∪ 𝑉3 juga merupakan himpunan pendominasi dari 𝐺. Karena 𝑉2 ∪ 𝑉3 merupakan himpunan pendominasi dari 𝐺 maka saat 𝑉1 = 𝑉2 , untuk mencari himpunan pendominasi minimum dari 𝐺 cukup dengan memperhatikan himpunan pendominasi yang diperoleh dari 𝑉2 dan mengabaikan himpunan pendominasi yang diperoleh dari 𝑉1 . Teorema 2 Perhatikan suatu graph grid 𝐺𝑛×𝑛 = (𝑉, 𝐸), dan misalkan 𝑆 ⊆ 𝑉. Ketika memperhatikan titik-titik untuk mendominasi 𝑣𝑖,𝑗 = 𝑠(𝑆), kandidatkandidat 𝑣𝑖−1,𝑗 dan 𝑣𝑖,𝑗 −1 dapat diabaikan (setiap kali titik-titik tersebut ada, yaitu, 𝑖 ≥ 2 dan 𝑗 ≥ 2, secara berurutan). Bukti : Menurut definisi dari 𝑠 𝑆 , titik yang belum terdominasi yang dapat didominasi oleh 𝑣𝑖−1,𝑗 hanyalah titik 𝑣𝑖,𝑗 . Sama halnya,titik-titikyang belum terdominasi yang dapat didominasi oleh𝑣𝑖,𝑗 −1 (dengan asumsi 𝑗 ≥ 2) hanyalah titik 𝑣𝑖,𝑗 dan titik 𝑣𝑖+1,𝑗 −1 (jika 𝑖 ≤ 𝑚 − 1). Tetapi, jika𝑖 ≤ 𝑚 − 1, 𝑣𝑖+1,𝑗 mendominasi titik yang sama, dan jika𝑖 = 𝑚, 𝑣𝑖+1,𝑗 (atau 𝑣𝑖,𝑗 , jika 𝑗 = 𝑛) mendominasi titik yang sama tersebut. Sehingga dari Teorema 1 diperoleh bahwa kandidat-kandidat 𝑣𝑖−1,𝑗 dan 𝑣𝑖,𝑗 −1 dapat diabaikan (setiap kali titik-titik tersebut ada, yaitu, 𝑖 ≥ 2 dan 𝑗 ≥ 2, secara berurutan). Teorema 3 Perhatikan suatu graph grid 𝐺 = 𝑉, 𝐸 𝑛 × 𝑛 dan misalkan 𝑆 ⊆ 𝑉. Ketika memperhatikan titik-titik untuk mendominasi 𝑣𝑖,𝑗 = 𝑠 𝑆 jika 𝑣𝑖,𝑗 +1 ∈ 𝑆, 𝑗 ≤ 𝑛 − 1, kandidat 𝑣𝑖,𝑗 dapat diabaikan. Bukti : Jika𝑣𝑖,𝑗 +1 , 𝑣𝑖,𝑗 +2 ∈ 𝑆, titik-titik yang belum terdominasi yang dapat didominasi oleh 𝑣𝑖,𝑗 hanyalah titik 𝑣𝑖,𝑗 dan jika 𝑖 ≤ 𝑚 − 1, 𝑣𝑖+1,𝑗 +1 . Tetapi, untuk 𝑖 ≤ 𝑚 − 1, 𝑣𝑖+1,𝑗 mendominasi kedua titik-titik tersebut. Sehingga dari Teorema 1 diperoleh bahwa untuk mendominasi 𝑣𝑖,𝑗 = 𝑠 𝑆 jika 𝑣𝑖,𝑗 +1 ∈ 𝑆, 𝑗 ≤ 𝑛 − 1, kandidat 𝑣𝑖,𝑗 dapat diabaikan

3

Teorema 4 Perhatikan suatu graph grid 𝐺 = (𝑉, 𝐸)𝑛 × 𝑛, dan misalkan 𝑆 ⊆ 𝑉. Saat memperhatikan titik-titik untuk mendominasi 𝑣𝑖,𝑗 = 𝑠(𝑆) jika 𝑣𝑖,𝑗 +1 , 𝑣𝑖,𝑗 +2 ∈ 𝑆, 𝑖 ≤ 𝑛 − 1, 𝑗 ≤ 𝑛 − 2, maka kandidat 𝑣𝑖,𝑗 +1 dapat diabaikan. Bukti : Jika 𝑣𝑖,𝑗 +1 , 𝑣𝑖,𝑗 +2 ∈ 𝑆, titik-titik yang belum terdominasi yang dapat didominasi oleh 𝑣𝑖,𝑗 +1 hanyalah titik 𝑣𝑖,𝑗 dan jika 𝑖 ≤ 𝑚 − 1, 𝑣𝑖+1,𝑗 +1 . Tetapi, untuk 𝑖 ≤ 𝑚 − 1, 𝑣𝑖+1,𝑗 mendominasi kedua titik-titik tersebut. Sehingga dari Teorema 1 diperoleh bahwa untuk mendominasi 𝑣𝑖,𝑗 = 𝑠(𝑆) jika 𝑣𝑖,𝑗 +1 , 𝑣𝑖,𝑗 +2 ∈ 𝑆, 𝑖 ≤ 𝑛 − 1, 𝑗 ≤ 𝑛 − 2, maka kandidat 𝑣𝑖,𝑗 +1 dapat diabaikan Algoritma Pencarian Himpunan Pendominasi Minimum Untuk mencari himpunan pendominasi minimum digunakan Algoritma Breadth-First Search (BFS) dengan ciri khas dari Algoritma Pemrograman Dinamis. Selama pencarian kita memperhatikan himpunan-himpunan titik-titik yang terdominasi (daripada titik-titik yang mendominasi). Berikut langkah-langkah Algoritma Breadth-First Search (BFS) dengan ciri khas dari Algoritma Pemrograman Dinamis sebagai berikut : 1. Tentukan himpunan 𝑆 yang merupakan himpunan titik-titik yang terdominasi, dengan 𝑆0 = ∅ 2. Tentukan 𝑠 𝑆𝑝 = 𝑣𝑖,𝑗 3. Tentukan kandidat-kandidat pendominasi 𝑠(𝑆𝑝 ) 4. Lakukan pengurangan-pengurangan kandidat dengan kriteria sebagai berikut : a) Jika 𝑖 ≥ 2 maka kandidat 𝑣𝑖−1,𝑗 diabaikan b) Jika 𝑗 ≥ 2 maka kandidat 𝑣𝑖,𝑗 −1 diabaikan c) Jika 𝑗 ≤ 𝑛 − 1, 𝑣𝑖,𝑗 +1 ∈ 𝑆𝑝 maka kandidat 𝑣𝑖,𝑗 diabaikan d) Jika 𝑖 ≤ 𝑚 − 1, 𝑗 ≤ 𝑛 − 2, 𝑣𝑖,𝑗 +1 ∈ 𝑆𝑝 dan 𝑣𝑖,𝑗 +2 ∈ 𝑆𝑝 maka kandidat 𝑣𝑖,𝑗 +1 diabaikan. 5. Pilih satu titik 𝑣𝑘,𝑙 dari kandidat yang tersisa sebagai titik pendominasi. Jika terdapat dua atau lebih kandidat tersisa maka perhatikan hal-hal berikut : a) Untuk 𝑛 ≠ 1 dan 𝑝 = 0 maka pilih selain 𝑣1,1 b) Pilih kandidat yang lebih banyak mendominasi titik baru atau jika 𝐷(𝑉1 ) ⊆ 𝐷(𝑉2 ) maka pilih himpunan pendominasi 𝑉2 6. Tentukan 𝐷(𝑣𝑘,𝑙 ) 7. Diperoleh 𝑆𝑝 = 𝑆𝑝−1 ∪ 𝐷(𝑣𝑘𝑙 ) Lakukan pencarian sampai semua titik telah terdominasi PENUTUP Kesimpulan Untuk menentukan himpunan pendominasi dari graph jika terdapat dua himpunan bagian dari himpunan titik yang merupakan himpunan pendominasi yang memiliki banyak anggota sama maka dipilih himpunan yang mendominasi

4

titik lebih banyak (Teorema 1). Jika dalam pencarian terdapat titik yang belum terdominasi 𝑠 𝑆 = 𝑣𝑖,𝑗 diperoleh aturan sebagai berikut :  Jika 𝑖 ≥ 2 maka kandidat 𝑣𝑖−1,𝑗 diabaikan Jika 𝑗 ≥ 2 maka kandidat 𝑣𝑖,𝑗 −1 diabaikan (Teorema 2)  Jika 𝑗 ≤ 𝑛 − 1, 𝑣𝑖,𝑗 +1 ∈ 𝑆𝑝 maka kandidat 𝑣𝑖,𝑗 diabaikan (Teorema 3)  Jika 𝑖 ≤ 𝑚 − 1, 𝑗 ≤ 𝑛 − 2, 𝑣𝑖,𝑗 +1 ∈ 𝑆𝑝 dan 𝑣𝑖,𝑗 +2 ∈ 𝑆𝑝 maka kandidat 𝑣𝑖,𝑗 +1 diabaikan. (Teorema 4) Menentukan himpunan pendominasi minimum dan bilangan dominasi menggunakan algoritma BFS (breadth-first search) dengan ciri khas algoritma pemrograman dinamis diperoleh bahwa 𝛾1,1 = 1; 𝛾2,2 = 2; 𝛾3,3 = 3; 𝛾4,4 = 4; 𝛾5,5 = 7; 𝛾6,6 = 10; 𝛾7,7 = 12; dengan salah satu contoh himpunan pendominasi minimum untuk masing-masing ukuran. Menentukan bilangan dominasi dengan menggunakan rumus dari Chang, Clark, dan Hare (1995) dan dengan menggunakan algoritma BFS (breadth-first search) dengan ciri khas algoritma pemrograman dinamis diperoleh hasil yang sama. Saran Dalam tulisan ini masih disajikan graph grid persegi 𝑛 × 𝑛 dengan ukuran yang terbatas yaitu sampai dengan 𝑛 ≤ 7, diharapkan pembaca dapat mengembangkan untuk graph grid yang lebih umum. Masih banyak masalah penentuan bilangan dominasi untuk graph grid yang belum ditemukan yang dapat dijadikan sebagai bahan penelitian antara lain bilangan dominasi pada graph grid 𝑛 × 𝑛 untuk 𝑛 > 7, bilangan dominasi pada graph grid 𝑚 × 𝑛 untuk sebarang 𝑚 dan masih banyak lagi permasalahan penentuan bilangan dominasi yang lain. Masih banyak pula bentuk-bentuk lain graph yang dapat dicari bilangan dominasinya. DAFTAR PUSTAKA Alanko, S., Crevals, S., Isopoussu, A., Östegård, P., & Pettersson, V. 2011. Computing the Domination Number of Grid Graphs, 18 (141). Dari The Electronic Journal of Combinatorics (Online) (http://www.combinatorics.org) diakses 11 Maret 2012 Beineke, L.W, dan Wilson, R.J. 2004. Topics in Algebraic Graph Theory. Cambridge : Cambridge University Press. Dari BookFinder (Online) (http://www.en.bookfi.org ) diakses 18 Januari 2013 Chang, T. Y, Clark, W.E, dan Hare, E.O. 1995. Domination Number of Complete Grid Graphs. I. . 38 (97). Dari The Electronic Journal of Combinatorics (Online) (http://www.combinatorics.org) diakses 21 Desember 2012 Haynes, T.W, Hedetniemi, S.T, dan Slater, P.J. 1998. Fundamentals of Domination in Graphs. New York: Marcel Dekker, Inc. Dari BookFinder (Online) (http://www.en.bookfi.org ) diakses 11 April 2012 Weisstein, Eric W. Grid Graph. From MathWorld-A Wolfram Web Resource. (http://mathworld.wolfram.com/GridGraph.html) diakses tanggal 11 April 2012

5