Bakalárska práca

Meno: Terézia Strišovská

Názov témy: Kostry v grafoch

Školiteľ: doc. RNDr. Tatiana Jajcayová, PhD.

Cieľ práce: Cieľom práce je navrhnť a zbehnúť experimenty a určiť ohraničenia pre počet kostier v rôznych triedach grafov.

Denník

práca s generátorom regulárnych grafov(genreg), prepis kódu na spracovanie jeho výstupov(počítanie kostier v jednotlivých grafoch, hľadanie grafov s minimálnym a maximálnym počtom kostier) do C++
odskúšanie verzie programu s paralelným spracovaním výstupov z genregu
skúmanie štruktúry 4-regulárnych grafov s minimálnym počtom kostier

študovanie článkov o počte kostier v regulárnych grafoch, porovnanie zatiaľ zistených hodnôt s ohraničeniami z článkov
prehľad možností genregu, ktoré by umožnili sparalelizovať proces genrovania grafov
popísanie doterajšej práce s genregom, rôznych verzií kódu na spracovanie jeho výstupu

kontrola a snaha o pochopenie vzorca pre horné ohraničenie počtu kostier z článku Nogu Alona
úprava paralelného spracovania grafov tak, že spracovanie grafov prebieha po skupinách a nie po jednom
paralelné genrovanie grafov s využitým možnosti rozdeliť generovanie na viacero častí, ktoré sa následne oddelene spracujú
testovanie najnovšej verzie práce s grafmi na väčších množinách grafov - pre n=24, k=3; n=18, k=4(n - počet vrcholov, k - regularita)

úprava vyhodnocovania a zberania výsledkov jednotlivých generátorov
využitie generátora regulárnych grafov na konštrukciu biregulárnych grafov, kde je práve jeden vrchol odlišného stupňa
hľadanie biregulárnych grafov na n+1 vrcholoch, kde n vrcholov má regularitu n - 1 a jeden vrchol n - 2, s minimálnym počtov kostier

pokračovanie v generovaní reulárnych grafov
hľadanie grafov s maximálnym a minimálnym počtom kostier v biregulárnych grafov, kde všetky vrcholy až na jeden majú stupeň 3, skúšanie rôznych hodnôt stupňa pridaného vrvholu
písanie východiskovej kapitoly

vytvorenie verzide generovania biregulárnych grafov, ktorá funguje paralelne
generovanie biregulárnych grafov na n++ vrcholoch, kde n vrcholov má stupeň 4
písanie východiskovej kapitoly
konzultácia ohľadom doterajších zistení týkajúcich sa minimálneho a maximálneho počtu kosteir v 3-regulárnych grafoch

oprava výpočtu kostier grafu, aby bolo možné získať správne výsledky aj pre väčší počet kostier, optimalizácie
prehľad algoritmov na vygenerovanie všetkých kositier grafu, študovanie algoritmu ktorý navrhli S. Kapoor a H. Ramesh
písanie východiskovej kapitoly
implementácia AHU algoritmu na izomorfizmus stromov v C++

písanie o použitých algoritmoch
analýza štruktúry biregulárnych grafov s minimálnym počtom kostier pre rôzne hodnoty stupňa pridaného vrcholu
dorobenie verzie generovania biregulárnych grafov, kde si môžeme určiť počet vrcholov obidvoch stupňov

zjednotenie kódu pre rôzne verzie spracovania grafov(regulárne, biregulárne grafy, paralelné, sériové generovanie)
študovanie ďalších algoritmov na generovanie všetkých kostier grafu
implementácia algoritmu, ktorý navrhli Cristian E. Onete a Maria Cristina C. Onete - kostry sa tu generujú pomocou upravenej incidenčnej matice

opravy chýb v implementácii AHU algoritmu
využitie generovania kostier na zistenie počtu tried izomorfizmu pre množinu všetkých kostier zadaného grafu, porovnanie tried izomorfizmu kostier grafov s maximálnym a minimálnym počtom kostier pre zadaný počet vrcholov
konzultácia o vlastnostiach 3-regulárnych grafov s maximálnym počtom kostier a o hornom odhade počtu kostier pre regulárne grafy z článku N.Alona

generovanie grafov so stanoveným najnižším možným obvodom, overovanie vzťahu obvodu grafov k počtu ich kostier
písanie o algoritme na generovanie všetkých kostier grafu a o zistených výsledkoch pre spodnú hranicu kostier pre 3 a 4-regulárne grafy

Zdroje:

http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html

M. Meringer: Fast Generation of Regular Graphs and Construction of Cages. Journal of Graph Theory 30, 137-146, 1999.

N. Alon: The Number of Spanning Trees in Regular Graphs. Random Struct. Algorithms 1(2). 1990. 175-182.

A. Aho, J. Hopcroft, and J. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Co., Reading, MA, 1974, pp. 84-85.

D. B. WEST. Introduction to Graph Theory. Prentice-Hall, Inc. 1996. 0-13-227828-6.

T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN. Introduction to Algorithms, Third Edition. The MIT Press. 2009. 978-0-262-03384-8.

A. STANOYEVITCH. Discrete Structures with Contemporary Applications. Chapman and Hall/CRC Press. 2011. 978-1-4398-1768-1.