20.500.12556/RUL-186420 Levi in kontaminacije na trikotniških mrežah Lions and contaminations on triangular grids Diplomska naloga obravnava problem levov in kontaminacije na trikotniških mrežah: po grafu se gibljejo levi, ki čistijo kontaminacijo, ta pa se hkrati ˇsiri na vsa nezasedena sosednja vozlišča. Zanima nas najmanjše število levov, potrebnih za očiščenje mreže Pn. Implementirali smo simulacijsko jedro in štiri modele gibanja (pasovni, vljudni, kofeinirani in monotoni) ter z izčrpnim preiskovanjem za n od 3 do 8 določili najmanjše število levov in ga primerjali z mejami iz literature. Pri pasovnem, vljudnem in monotonem modelu zadošča n levov, kofeinirani model pa mrežo P5 očisti s štirimi in P6 s petimi levi; torej z manj kot n. Rezultate smo prikazali v interaktivni spletni aplikaciji. This thesis studies the lions and contamination problem on triangular grids: lions move along a graph and clean contamination, which simultaneously spreads to every unoccupied neighbouring vertex. We ask for the smallest number of lions needed to clean the grid Pn. We implement a simulation core and four movement models (strip, polite, caffeinated and monotone) and, through exhaustive search for n from 3 to 8, determine the minimum number of lions and compare it with bounds from the literature. The strip, polite and monotone models require n lions, whereas the caffeinated model cleans P5 with four and P6 with five lions; fewer than n. We presented the results in an interactive web application. levi in kontaminacija trikotniške mreže igre zasledovanja in izmikanja čiščenje grafov izčrpno preiskovanje Cheegerjeva konstanta lions and contamination triangular grids pursuit-evasion games graph cleaning exhaustive search Cheeger constant true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2026-09-01 12:00:08 2026-09-01 12:00:18 2026-09-04 06:51:33 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38784 289976323 Uhan_Masa_-_Levi_in_kontaminacije_na_trikotniskih_mrezah.pdf Uhan_Masa_-_Levi_in_kontaminacije_na_trikotniskih_mrezah.pdf 1 239C0F6E7FCF9968FCF793A9419B4B2F d83bd0a3ea6ad336c09600393fa6a36ed37bf7e999d3304546c0eddbea6ca058 8417f5b6-a5eb-11f1-9b0d-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=245667 Fakulteta za računalništvo in informatiko 0 0 0