| 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.
|
|---|