arvutiteaduse instituudi lõputööderegister


Suured indutseeritud metsad tasandilistes graafides
Nimi Kairi Hennoch
Kokkuvõte Tasandilised graafid on graafid, mida saab joonistada tasandile nii, et tema servad ei lõiku üksteisega mujal kui tippudes. Selles töös me uurime, kui suuri indutseeritud metsi on alati võimalik tasandilistes graafides leida. Praegu parim teadaolev tulemus on pärit Borodinilt, mille kohaselt igas tasandilises graafis leidub indutseeritud mets, mis sisaldab vähemalt 2/5 tema tippudest. Selles tööd anname me osalise tulemuse selle hinnangu parandamise suunas. Täpsemalt, me näitame, et minimaalne vastunäide meie parandatud tulemusele ei sisalda tippe, mille aste on väiksem kui 4, ja et selles sisalduvad astmega 4 tipud saavad olla vaid üht kindlat tüüpi.
Lõputöö keel inglise
Lõputöö tüüp Magister - Informaatika
Juhendaja(d) Dirk Oliver Theis, Kaveh Khoshkhah
Kaitsmise aasta 2016
PDF