arvutiteaduse instituudi lõputööderegister


Graatsiliste graafide arvjada leidmine kasutades paralleelarvutusi
Nimi Miron Storožev
Kokkuvõte Graatsiliste graafide kirjeldamine on üks graafiteooria lahendamata probleeme. Graafide üheks kirjeldamise võimaluseks on kasutada arvjada, ent senini pole suudetud leida piisaval hulgal graatsiliste graafide arvjada elemente. Eelnevalt on koostatud programm, mis leiab n-tipuliste graatsiliste graafide arvu, kuid selle keerukusest tuleneva pika tööaja tõttu pole tänaseni loendatud rohkemaid kui 11-tipulisi graatsilisi graafe.
Käesolevas lõputöös on paralleelarvutusi kasutades optimeeritud olemasolevat graatsiliste graafide loendamise programmi. Paralleelarvutuse rakendamise tulemusena kiirendatakse graatsiliste graafide leidmise protsessi. Käitades optimeeritud programmi klastril on leitud ja loendatud 12- ja 13-tipulised graatsilised graafid.
Bakalaureusetöö tulemusena valminud programmi võib kasutada ka suurema tipuarvuga graatsiliste graafide loendamiseks. Töö käigus leitud 12- ja 13-tipulisi graafe kasutatakse edaspidi graatsiliste graafide kirjeldamisel.
Lõputöö keel eesti
Lõputöö tüüp Bakalaureus - Informaatika
Juhendaja(d) Ahti Peder
Kaitsmise aasta 2018
PDF