Igra policaja in roparjaGyergyek, Miha (Avtor) Iršič, Vesna (Mentor) igra policaja in roparjapotezapremikzmagovalna strategijapolicijski grafroparski grafretraktsenčna strategijapastrazgradljiv grafpolicijska urejenostčas lovljenja2-razgradljiv grafObravnavamo 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.20242024-09-12 08:15:09Delo diplomskega seminarja/zaključno seminarsko delo/naloga161527UDK: 519.17VisID: 143009COBISS_ID: 207778563sl