| Meno: | Maroš
|
|---|
| Priezvisko: | Bajtoš
|
|---|
| Názov: | Metrické vlastnosti náhodne indukovaných podgrafov n-rozmernej hyperkocky
|
|---|
| Vedúci: | doc. RNDr. Eduard Toman, CSc.
|
|---|
| Rok: | 2008
|
|---|
| Kľúčové slová: | náhodné grafy, vrcholové pokrytie, boolovské funkcie
|
|---|
| Abstrakt: | Predložená práca sa zaoberá niektorými metrickými vlastnosťami náhodne indukovaných podgrafov n-rozmerných hyperkociek. Cieľ práce je vyčísliť horné a dolné ohraničenie vrcholového pokrytia pre špeciálny pravdepodobnostný model - náhodne indukované podgrafy n-rozmerných hyperkociek s daným počtom vrcholov (tento model bol zavedený v [5]). Ná nájdenie týchto ohraničení je použitý všeobecný greedy algoritmus pre hľadanie vrcholového pokrytia[2] a niektoré výsledky z [1] a z [3]. Vrcholové pokrytie náhodne indukovaného podgrafu hyperkocky je úzko späté s minimalizáciou boolovských funkcií.
|
|---|