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