Skripsi

Menghitung bilangan dominasi pada graph grid n x n, n < 7 / Mucharomatut Toyyibah

Abstrak
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.

Informasi Detail

DDC

Rs 511.5 TOY m

Prodi

Universitas Negeri Malang. Jurusan Matematika, 2013.

Deskripsi Fisik

vii, 59 lembar: il. tab.; 30 cm

Bahasa

Indonesia

No Reg

02284/KI/13

Edisi

Skripsi ( Sarjana )--Universitas Negeri Malang, 2013

Subjek

1. GRAPH GRID

Pembimbing

1. Purwanto

Lampiran Berkas