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

---

Ketersediaan

2192A19III

2192 A 19-ii

Perpustakaan FSM Undip (Referensi)

Tersedia

Informasi Detail

Judul Seri

MATEMATIKA

No. Panggil

2192 A 19-ii

Penerbit

: ., 2019

Deskripsi Fisik

-

Bahasa

Indonesia

ISBN/ISSN

-

Klasifikasi

519.4024

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

-

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Permadani Candra Sari

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar