Meno:Peter
Priezvisko:Schmidt
Názov:Algoritmické vlastnosti vnorení grafov do plôch
Vedúci:Mgr. Michal Kotrbčík
Rok:2012
Kľúčové slová:vnorenie grafu, rod grafu, kompletný graf, kompletný bipartitný graf, snark, distribúcia rodov grafu, probabilistické vzorkovanie, priemerný rod
Abstrakt:Práca sa venuje algoritmickým vlastnostiam vnorení grafov do plôch. V prvej časti práce sa zameriavame na distribúciu rodov grafov. Za pomoci niekoľkých tvrdení prinášame distribúcie rodov pre kompletné grafy na najviac 7 vrcholoch, kompletné bipartitné grafy na najviac 10 vrcholoch a snarky na najviac 28 vrcholoch, spolu s odhadom času potrebného pre väčšie grafy. Druhá časť práce je zameraná na priemerný rod grafu. Pomocou odhadov počtu vnorení, súvisiacich s priemerným rodom grafu, testujeme priemerný rod kompletných grafov pravdepodobnostným algoritmom.

Súbory bakalárskej práce:

bakalarka.pdf
distribucie_rodov_snarkov.zip