Nagy, ÁbrisHudák, Noémi2022-05-062022-05-062022-05-05http://hdl.handle.net/2437/332472A dolgozat témája a sokszögek háromszögelése, amely fontos szerepet tölt be a matematika számos különböző területén, de ezek közül is kiemelten a teremőr problémában és annak különböző változataiban. A teremőr probléma azt a kérdést igyekszik megválaszolni, hogy legkevesebb hány őr szükséges egy n-oldalú sokszög alaprajzú terem őrzéséhez. A választ Václav Chvátal adta meg, miszerint n/3 őr mindig elegendő és néha szükséges. A megoldás egy elegáns bizonyítása az adott sokszög háromszögelésén és az így kapott gráf három színnel történő színezésén alapszik. Ezt a technikát később a probléma számos változatának megoldásában sikeresen alkalmazták, ezért megvizsgáljuk, hogy hogyan lehet a sokszögeket a lehető leghatékonyabban háromszögekre bontani, a különféle eljárások között ugyanis nagyságrendi különbségek lehetnek. Kiderül, hogy a legcélravezetőbb, ha a sokszöget először monoton sokszögekre bontjuk, majd az így kapott monoton sokszögeket háromszögeljük.56huháromszögelésteremőr problémamonoton háromszögekDEENK Témalista::MatematikaHozzáférhető a 2022 decemberi felsőoktatási törvénymódosítás értelmében.