20.500.12556/DKUM-74902 Igra policajev in roparjev na grafih The game of cops and robbers on graphs V magistrskem delu bomo predstavli igro policajev in roparjev na grafih, kjer se policaji in ropar premikajo po vozliščih grafa. Cilj policajev je, da eden izmed njih uspe priti na enako vozlišče kot ropar. Grafom, na katerih ima v igri z enim policajem policaj zmagovalno strategijo, pravimo policaj-zmaga grafi. Najmanjše število policajev, ki je potrebnih, da imajo zmagovalno strategijo na grafu G, imenujemo varnostno število grafa G. Poleg igre policajev in roparjev bomo predstavili še druge različice te igre. Varnostno število grafa bomo izračunali za nekatere preproste družine grafov in predstavili spodnje in zgornje meje varnostnega števila grafa. Nato bomo pokazali, kako varnostno število retraktov grafa vpliva na varnostno število originalnega grafa. Kot bomo videli, retrakti grafov igrajo pomembno vlogo pri karakterizaciji policaj-zmaga grafov. Dokažemo, da so policaj-zmaga grafi natanko odstranljivi grafi. Predstavimo tudi policaj-zmaga urejenost in policaj-zmaga strategijo. Na koncu še dokažemo, da so tudi mostovni grafi policaj-zmaga grafi. In this master's thesis we will present the Game of Cops and Robbers on graphs, where cops and robber moves on vertices of a graph. The goal of the cops is, that one of them is on the same vertex as the robber. The graphs on which one cop has a winning strategy are called cop-win graphs. The minimum number of cops, that have a winning strategy on a graph G, is called the cop number of G. In addition to the Game of Cops and Robbers, we will present other variations of this game. We will calculate the cop number for some simple graph families and present some lower and upper bounds for the cop number. Then we will show how the cop number of a retract of a graph affects on the cop number of the original graph. As we will see, retracts of a graph play an important role in the characterization of the cop-win graphs. We prove that cop-win graphs are exactly dismantlable graphs. Then we present the cop-win ordering and the cop-win strategy. At the end, we show that bridged graphs are cop-win graphs. igra policajev in roparjev varnostno število grafa policaj-zmaga grafi odstranljivi grafi mostovni grafi Game of Cops and Robbers cop-win number cop-win graphs dismantlable graphs bridged graphs true true false [T. Bastašić] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2019-09-11 20:55:02 2019-11-05 14:48:53 2022-08-09 09:42:17 2019-12-10 08:13:48 2019 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 24865288 URN:SI:UM:DK:ANTDMAOV MAG_Bastasic_Tina_2019.pdf MAG_Bastasic_Tina_2019.pdf 1 627FFE8487F2D6A8325E87B3BEA11873 208347b969e76397ad31f8b62027e9f9c1617e6d2c2a421b13d1babc6b14a1d3 f29b0715-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/131741a0-026f-4c0d-bf2c-a080067ab3db https://dk.um.si/Dokument.php?lang=slv&id=137708 Fakulteta za naravoslovje in matematiko 0 0 0