20.500.12556/RUL-112623 Robni stražarji v trdnjavskem problemu delo diplomskega seminarja Edge guards for the fortress problem V diplomskem seminarju bomo obravnavali trdnjavski problem z robnimi stražarji. Trdnjavski problem je problem, pri katerem je trdnjava predstavljena kot poligon v ravnini, stražarji pa so točke ali robovi v ravnini. Dokazali bomo, da je v splošni trdnjavi $\lceil n/3 \rceil$ robnih stražarjev včasih potrebnih in vedno dovolj, da zastražijo zunanjost trdnjave. Pri ortogonalni trdnjavi pa potrebujemo $\lfloor n/4 \rfloor + 1$ robnih stražarjev. In this seminar we consider the fortress problem with edge guards. In the fortress problem the fortress is considered a polygon and guards are points or edges in a plane. We will prove that it is always possible to guard exterior of general fortress with $\lceil n/3 \rceil$ edge guards and exterior of orthogonal fortress with $\lfloor n/4 \rfloor + 1$ edge guards. poligon stražar rob trdnjava polygon guard edge fortress true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2019-10-27 07:45:24 2019-10-27 07:45:29 2024-05-30 10:17:59 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.1 104882 18815833 1125.pdf 1125.pdf 1 458FF9B085F31DF4E3F07AD0C284129C e535d67a0aa4db3d480aa2d0aa918dfbfe191216792a6d48df9d7c15351e2135 ec6b4651-a1b7-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=124543 Fakulteta za matematiko in fiziko 0 0 0