Toyyibah, Mucharomatut (2013) Menghitung bilangan dominasi pada graph grid n x n, n < 7 / Mucharomatut Toyyibah. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Kata kunci graph grid himpunan pendominasi bilangan dominasi algoritma BFS (breadth-first search) algoritma pemrograman dinamis. Salah satu topik yang dibahas dalam teori graph ialah himpunan pendominasi (dominating set). Himpunan pendominasi ialah suatu himpunan bagian S dari himpunan titik V(G) dimana titik-titik yang tidak berada pada S terhubung langsung dengan minimal satu titik pada S. Ukuran dari himpunan pendominasi terkecil disebut bilangan dominasi. Bilangan dominasi pada graph G dinotasikan dengan 947 (G) dan bilangan dominasi pada graph grid G_(n n) dinotasikan dengan 947 _(n n) Banyak sekali manfaat penggunaan himpunan pendominasi dan bilangan dominasi dalam kehidupan sehari-hari diantaranya untuk menentukan rute bus sekolah menentukan posisi stasiun radio survey lahan dan sistem jaringan komputer. Oleh karena itu studi mengenai bilangan dominasi telah berkembang sejak lama. Banyak usaha-usaha yang telah dilakukan dalam menentukan himpunan pendominasi dan bilangan dominasi untuk memecahkan permasalahan dalam kehidupan. Salah satu metode dalam menetukan bilangan dominasi pada graph grid ialah dengan pendekatan bilangan kromatik sampai ditemukan suatu rumus umum untuk bentuk graph grid tertentu. Selain dengan rumus umum bilangan dominsi dapat dicari melalui algoritma pencarian. Dengan menggunakan algoritma BFS (breadth-first search) dengan ciri khas algoritma pemrograman dinamis diperoleh bahwa 947 _1 1 1 947 _2 2 2 947 _3 3 3 947 _4 4 4 947 _5 5 7 947 _6 6 10 947 _7 7 12 dengan diberikan salah satu contoh himpunan pendominasi minimum untuk masing-masing ukuran. Baik perhitungan dari Chang Clark dan Hare (1995) dan algoritma pencarian diperoleh hasil yang sama untuk masing-masing ukuran.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 10 Jun 2013 04:29 |
| Last Modified: | 09 Sep 2013 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17318 |
Actions (login required)
 |
View Item |