20.500.12556/RUL-187625 Igra policajev in roparja z ničelno vidlivostjo delo diplomskega seminarja Game of zero-visibility cops and robber Igra policajev in roparja z ničelno vidljivostjo je igra dveh igralcev na povezanem grafu, v kateri policaji nimajo popolnih informacij, ropar pa je vseveden in pozna nasprotnikov položaj in strategijo. V diplomskem delu obravnavamo optimizacijski problem določanja policijskega števila z ničelno vidljivostjo, to je najmanjše število policajev, s katerim zagotovimo ujetje roparja. Predstavimo optimalne policajeve zmagovalne strategije za nekatere osnovne družine grafov, drevesa in splošne grafe. Pri splošnih grafih podamo zgornjo mejo policijskega števila z ničelno vidljivostjo s pomočjo potne dekompozicije in potne širine grafa. Game of zero-visibility cops and robber is a two-player game played on a connected graph in which the cops have no information about the robber’s location, while the omniscient robber knows both the cops’ positions and their strategy. This thesis examines the optimization problem of determining the zero-visibility cop number, that is, the minimum number of cops required to guarantee the robber’s capture. We present optimal winning strategies for the cops on selected basic graph families, trees, and general graphs. For general graphs, we derive an upper bound on the zero-visibility cop number using path decompositions and the pathwidth of a graph. teorija grafov igra policajev in roparja ničelna vidljivost policijsko število z ničelno vidljivostjo policajeva zmagovalna strategija potna širina potna dekompozicija monotona strategija Graph theory Cops and Robber game zero visibility zero-visibility cop number winning strategy for the cops pathwidth path decomposition monotone strategy true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2026-09-12 08:15:07 2026-09-12 08:15:10 2026-09-22 12:34:31 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 163677 291999235 24328.pdf 24328.pdf 1 840144DDB00DDF82950C2EA960F792B2 11945e06d9600757a10b8a72965be2d689e85e3cbccf5634e6caab877040d0c1 47fadba4-ae71-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=247325 Fakulteta za matematiko in fiziko 0 0 0