ANALISA HIMPUNAN DOMINASI LOKASI PADA MODEL TOPOLOGI GRAF KHUSUS DAN OPERASINYA

Abstract

Terapan ilmu pengetahuan meningkat guna mengantisipasi permasalahan yang ditimbulkan baik secara teori maupun metode yang sesuai salah satunya yaitu menggunakan teori graf. Meskipun umurnya relatif muda yaitu pada tahun 1735 dikenalkan oleh seorang matematikawan terkenal Swiss yang bernama Leon- hard Euler, teori graf merupakan cabang matematika diskrit yang memiliki banyak aplikasi dalam kehidupan sehari-hari, salah satunya yaitu penempatan detektor. Penempatan detektor merupakan salah satu penerapan bidang matematika diskrit yaitu teori graf dengan menggunakan konsep himpunan dominasi lokasi. Himpunan dominasi lokasi atau dalam istilah asing disebut locating domi- nating set penerapannya dimulai pada tahun 1980 oleh Slater dengan membuat sebuah kode lokasi perlindungan untuk beberapa fasilitas dengan menggunakan jaringan detektor. suatu himpunan titik D pada graf G = (V;E) dikatakan himpunan dominasi lokasi atau locating dominating set jika untuk setiap pasangan titik yang berbeda u dan v pada V (G) ¡ D memenuhi syarat ; 6= N(u) \ D 6= N(v)\D dimana N(u) adalah himpunan titik tetangga dari u. Kardinalitas mini mum dari himpunan dominasi lokasi disebut locating domination number yang disimbolkan dengan °L(G) . Metode yang digunakan dalam penelitian ini adalah deskriptif aksiomatik. Data dalam penelitian ini menggunakan data sekunder berupa graf-graf khusus dan operasinya. Graf-graf khusus yang digunakan antara lain graf lintasan Pn, graf fan Fn, graf parasut PCn, graf helm Hn dan graf roda Wn dan operasi yang digunakan yaitu joint, crown product, amalgamasi, shackle dan power graf. Pada penelitian ini dihasilkan beberapa teorema sebagai berikut: 1. Teorema 4.2.1 Misal G adalah graf khusus berupa graf helm Hn untuk n ¸ 3, maka nilai himpunan dominasi lokasi dari G adalah °L (Hn)=n. 2. Teorema 4.2.2 Misal G adalah graf hasil operasi amalgamasi dari graf helm Hn, untuk n ¸ 3 dan m ¸ 2, maka °L (Amal(Hn; v;m)) = n £ m. 3. Teorema 4.2.3 Misal G adalah graf hasil operasi shackle dari graf helm Hn, untuk n ¸ 3 dan m ¸ 2, maka °L (Shack(Hn; v;m)) = n £ m. 4. Teorema 4.2.4 Misal G adalah graf hasil operasi power graf dari graf roda Wn dan graf fan F1;2, untuk n ¸ 3, maka °L (WF1;2 n ) = n. 5. Teorema 4.2.5 Misal G adalah graf hasil operasi power graf dari graf lin- tasan Pn dan graf helm Hm, untuk n ¸ 3 dan m ¸ 3, maka °L (PHm n ) = m(n ¡ 1). 6. Teorema 4.2.6 Misal G adalah graf khusus berupa graf parasut PCn untuk n ¸ 4, maka nilai himpunan dominasi lokasi dari G adalah °L (PCn)=d4n 5 e. 7. Teorema 4.2.7 Misal G adalah graf khusus berupa graf kipas Fn untuk n ¸ 4 dan n 6= 5, maka nilai himpunan dominasi lokasi dari G adalah °L (Fn)=d2n 5 e. 8. Teorema 4.2.8 Misal G adalah graf hasil operasi joint dari graf lintasan Pn dan graf helm Hm, untuk n ¸ 2 dan m ¸ 3, maka °L (Pn+Hm) = d2n 5 e+m. 9. Teorema 4.2.9 Misal G adalah graf hasil operasi crown product dari graf lintasan Pn dan graf helm Hm, untuk n ¸ 2 dan m ¸ 3, maka °L (Pn¯Hm) = m £ n. 10. Teorema 4.2.10 Misal G adalah graf hasil operasi amalgamasi dari graf parasut PCn, untuk n ¸ 5 dan m ¸ 2, maka °L (Amal(PCn; v;m)) = (d4n 5 e) £ m. 11. Teorema 4.2.11 Misal G adalah graf hasil operasi shackle dari graf kipas Fn, untuk n ¸ 5 dan m ¸ 3, maka °L (Shack(Fn; v;m)) = d2mn¡2m+2 5 e.