20.500.12556/RUL-161527 Igra policaja in roparja delo diplomskega seminarja The game of cop and robber Obravnavamo igro med dvema igralcema na povezanem grafu. Prvi igralec je policaj in poskuša ujeti drugega igralca, ki predstavlja roparja. Med vsako potezo se igralca lahko premakneta v sosednje vozlišče. Če sta v neki potezi igralca v istem vozlišču, je policaj roparja ujel in zmagal, če pa roparja ne more ujeti v končno mnogo potezah, je zmagal ropar. Grafom, na katerih policaj vedno zmaga, pravimo policijski, tistim, na katerih pa vedno zmaga ropar, pravimo roparski. Karakteriziramo policijske in roparske grafe in opišemo zmagovalno strategijo za policaja. Na policijskih grafih označimo s časom lovljenja najmanjši indeks poteze, v kateri policaj zagotovo zmaga. Najdemo zgornjo mejo za čas lovljenja v splošnih policijskih grafih in dokažemo, da je to najboljša zgornja meja. Čas lovljenja natančneje omejimo navzgor še za nekatere družine grafov. Problem časa lovljenja posplošimo na igro z enim policajem in več roparji. Najdemo zgornjo mejo in dokažemo, da je najboljša za tri roparje. Poiščemo zgornjo mejo za nekatere družine grafov in za drevesa dokažemo, da je najboljša. We consider a game between two players on a connected graph. The first player is the cop and tries to catch the second player, who is the robber. In each round, the players can move to an adjacent vertex. If in any move the players are on the same vertex, the cop captures the robber and wins. If the robber cannot be captured in a finite number of moves, the robber wins. Graphs on which the cop always wins are called cop-win graphs, while those on which the robber always wins are called robber-win graphs. We characterize cop-win and robber-win graphs and describe a winning strategy for the cop. On cop-win graphs, we define the capture time as the smallest index of the round in which the cop is guaranteed to win. We find an upper bound for the capture time in general cop-win graphs and prove that it is the best upper bound. We also provide a better upper bound for the capture time for some families of graphs. We generalize the capture time problem to a game with one cop and multiple robbers. We find an upper bound and prove it to be the best for three robbers. We also find an upper bound for some families of graphs and prove it to be the best for trees. igra policaja in roparja poteza premik zmagovalna strategija policijski graf roparski graf retrakt senčna strategija past razgradljiv graf policijska urejenost čas lovljenja 2-razgradljiv graf the game of cop and robber round move winning strategy cop-win graph robber-win graph retract shadow strategy trap dismantlable graph cop-win ordering capture time 2-dismantlable graph true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2024-09-12 08:15:09 2024-09-12 08:15:15 2024-09-17 09:30:40 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 143009 207778563 14288.pdf 14288.pdf 1 6E27854CECD3874F6298310405BC900B 9400b0cbb84536fa07b0f537004e092934c99b7a12ccf87b663f72b3f91a877d 51cbe8ce-70ce-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=190480 Fakulteta za matematiko in fiziko 0 0 0