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