Meno:Lenka
Priezvisko:Trojaková
Názov:Určovanie prahových funkcií podgrafov niektorých tried grafov
Vedúci:doc. RNDr. Eduard Toman CSc.
Rok:2009
Kľúčové slová:Enumerácia označených objektov, náhodné grafy, prahové funkcie, maximálna k-rozmerná podkocka
Abstrakt:Pomocou pravdepodobnostných metód sa v súčasnosti dosahuje väčšina vý- sledkov pre náhodne indukované grafy. Pravdepodobnostné metódy súvisia s enumeráciou diskrétnych štruktúr. Na skúmanie náhodných premenných vyjadrujúcich vlastnosti náhodných grafov sa často využíva Čebyševova a Markovova nerovnosť. Pre niektoré vlastnosti vieme určiť, od akej asympto- ticky najmenšej pravdepodobnosti vzniku hrany má takmer každý náhodne indukovaný graf danú vlastnosť. Takáto pravdepodobnosť sa nazýva prahová funkcia pre danú vlastnosť. Táto práca sa zaoberá spôsobmi enumerácie ozna- čených objektov, konkrétne počtom stromov na n vrcholoch a určovaním prahových funkcií podgrafov niektorých tried grafov. V prvej časti uvedieme pojmy a tvrdenia potrebné pre túto prácu. V druhej časti sa budeme veno- vať technikám enumerácie počtu označených objektov, ktoré demonštrujeme na dôkazoch Cayleyho vety. V tretej časti určíme prahovú funkciu existencie maximálnej k-rozmernej podkocky n-rozmernej hyperkocky.

Súbory bakalárskej práce:

bakalarka1.pdf