Text
Dimensi Metrik dan Bilangan Pencarian Lokasi pada Beberapa Graf untuk Permainan Cops and Robber
ABSTRAK
Tugas Akhir ini membahas varian lain dari permainan Cops and Robber yang
terinspirasi dari masalah penentuan lokasi aktual seorang pengguna ponsel yang sedang
berjalan. Diberikan sebuah graf G sebagai representasi daerah pencarian seorang
pengguna ponsel, yang dalam pembahasan ini dianalogikan sebagai perampok. Pada
setiap rondenya, polisi akan menerima informasi jarak antara mereka dengan
perampok. Polisi dikatakan memenangkan permainan jika mereka dapat menentukan
titik yang sedang ditempati oleh perampok, jika tidak maka perampok yang menang.
Dimensi metrik dari graf G didefinisikan sebagai minimum banyaknya polisi yang
dibutuhkan agar polisi memenangkan permainan dalam satu ronde permainan.
Sedangkan, bilangan pencarian lokasi dari graf G didefinisikan sebagai banyaknya
polisi minimum dimana polisi dapat memenangkan permainan dalam satu atau
beberapa ronde permainan. Diperoleh hasil bahwa dimensi metrik dan bilangan
pencarian lokasi graf G berbeda pada beberapa jenis graf dan terbukti bahwa dimensi
metrik graf G akan selalu kurang dari atau sama dengan selisih antara order dengan
diameter graf G dan bilangan pencarian lokasi graf G akan selalu kurang dari atau sama
dengan pathwidth dari graf G.
Kata kunci : Cops and Robber game, dimensi metrik , bilangan pencarian lokasixiii
ABSTRACT
This paper discusses the other variant of the Cops and Robber game inspired by the
problem of determining the actual location of a walking mobile user. Given a graph G
as a representation of the search area of a mobile user who in this paper is analogous
as the robber. On each round, the cops will receive distance information between them
and the robber. The cops are said to have won the game, if they could determine the
occupied vertex of the robber, if not then the robber win. Metric dimension of graph G
is defined as the minimum number of cops needed so that they win the game in one
round of play, while localization number of graph G is defined as the minimum number
of cops needed so that the cops can win the game in one or several round. The result
shows that the metric dimension and localization number of graph G are different on
several graphs and it is also proved that the metric dimension of graph G will always
be less than or equal to the difference between the order of graph G and its diameter
and the localization number of graph G will always be less than or equal to the
pathwidth of graph G.
Keywords: Cops and Robber game, metric dimension, localization number
2192A19III | 2192 A 19-ii | Perpustakaan FSM Undip (Referensi) | Tersedia |
Tidak tersedia versi lain