A teremőr probléma speciális sokszögekre

A tétel rövid nézete
dc.contributor.advisorDr. Nagy, Ábris
dc.contributor.authorVarga , Barbara
dc.contributor.departmentDE--Természettudományi és Technológiai Kar--Matematikai Intézet
dc.date.accessioned2023-12-14T11:25:51Z
dc.date.available2023-12-14T11:25:51Z
dc.date.created2023-11-17
dc.description.abstractA teremőr probléma egy síkbeli láthatósági probléma, amelyben arra a kérdésre keressük a választ, hogy legalább hány őrre van szükség egy n-oldalú sokszög alaprajzú terem vagy múzeum őrzéséhez. Pontosabban megfogalmazva: legalább hány pontot kell választanunk egy n-oldalú sokszögben ahhoz, hogy a sokszög minden pontja látható legyen ezek valamelyikéből? Ezt a kérdést először Victor Klee vetette fel 1973-ban, amelyre két évvel később Vasek Chvátal adott választ, amikor bebizonyította, hogy bármely n-oldalú sokszög alaprajzú terem őrzéséhez elegendő az oldalszám harmadával megegyező számú őr és tetszőlegesen nagy n esetén található olyan n-oldalú sokszög, amelynél valóban szükség van ennyi őrre. Ez az ún. Chvátal-féle teremőr tétel. A teremőr probléma később matematikusok generációit inspirálta a síkbeli láthatósági problémák tanulmányozására, akik a probléma számos különböző változatát dolgozták ki és oldották meg, amelyek között akadnak máig megválaszolatlanok. A dolgozatban az alap teremőr problémára adott Chvátal-féle megoldás ismertetése mellett a Victor Klee kérdésére adható választ olyan speciális alakú sokszögek esetén vizsgáljuk, mint csillagszerű, spirális vagy monoton sokszögek. Látható, hogy a sokszög alakjára tett megszorítás számos esetben lehetővé teszi, hogy a szükséges őrök számát jelentősen csökkentsük, ami különösen akkor szembetűnő, ha a sokszög oldalszáma helyett egy másik geometriai adat, a konkáv csúcsok számával fejezzük ki az őrök számát. Ezen felül megvizsgáljuk, hogy milyen hatással van az őrök számára adható korlátra, ha az őrök helyzetére megszorításokat teszünk (pl. az őrök csak a csúcsokban állhatbak). Végül meghatározzuk a szükséges őrök minimális számát abban az esetben is, ha az őrök mozoghatnak, külön vizsgálva azokat az eseteket, amikor az őrök útvonalára különféle megszorításokat teszünk. Mindezek mellett számos példát is bemutatunk annak igazolására, hogy a legtöbb állítás esetében szereplő korlátok tovább már nem javíthatók. A dolgozatban található tételek és példák nagy része megtalálható Joseph O'Rourke 1987-es Art Gallery Theorems and Algorithms című könyvében, viszont az abban szereplő eredményeket aktualizáltuk, illetve a példákat jelentősen pontosítva mutatjuk be, bizonyos esetekben segédtételek felhasználásával igazolva, hogy az adott példa valóban elkészíthető.
dc.description.courseMatematika
dc.description.degreeBSc/BA
dc.format.extent51
dc.identifier.urihttps://hdl.handle.net/2437/363102
dc.language.isohu
dc.rights.accessHozzáférhető a 2022 decemberi felsőoktatási törvénymódosítás értelmében.
dc.subjectgeometria
dc.subjectteremőr probléma
dc.subject.dspaceDEENK Témalista::Matematikahu_HU
dc.titleA teremőr probléma speciális sokszögekre
Fájlok
Gyűjtemények
Hallgatói dolgozatok (Matematikai Intézet)