Sokszögek hatékony háromszögelése

A tétel rövid nézete
dc.contributor.advisorNagy, Ábris
dc.contributor.authorHudák, Noémi
dc.contributor.departmentDE--Természettudományi és Technológiai Kar--Matematikai Intézethu_HU
dc.date.accessioned2022-05-06T06:17:13Z
dc.date.available2022-05-06T06:17:13Z
dc.date.created2022-05-05
dc.description.abstractA 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.hu_HU
dc.description.correctorLB
dc.description.courseMatematikahu_HU
dc.description.degreeBSc/BAhu_HU
dc.format.extent56hu_HU
dc.identifier.urihttp://hdl.handle.net/2437/332472
dc.language.isohuhu_HU
dc.rights.accessHozzáférhető a 2022 decemberi felsőoktatási törvénymódosítás értelmében.
dc.subjectháromszögeléshu_HU
dc.subjectteremőr problémahu_HU
dc.subjectmonoton háromszögekhu_HU
dc.subject.dspaceDEENK Témalista::Matematikahu_HU
dc.titleSokszögek hatékony háromszögelésehu_HU
Fájlok
Gyűjtemények
Hallgatói dolgozatok (Matematikai Intézet)