Název: Strukturální vlastnosti grafů---pravděpodobnostní a deterministický pohled
Překlad názvu: Structural properties of graphs---probabilistic and deterministic point of view
Autoři: Hladký, Jan ; Pawlas, Zbyněk (oponent) ; Šámal, Robert (vedoucí práce)
Typ dokumentu: Bakalářské práce
Rok: 2006
Jazyk: eng
Abstrakt: [eng] [cze]
We study bipartite subgraphs of a random cubic graph in the thesis. We show, that an edge-maximum bipartite subgraph of a random cubic graph on n vertices has asymptotically almost surely less then 3 2 · 0.9351n edges. We also show that the number of vertices of a vertex-maximum induced bipartite subgraph of a random cubic graph lies within interval [0.75n; 0.9082n]. To obtain the lower bound we design a randomized algorithm for finding a large induced bipartite subgraph of a random cubic graph. We discuss consequences of the results for graph homomorphisms, namely for Pentagon Conjecture posed by Nešetřil. V práci zkoumáme bipartitní podgrafy náhodného kubického grafu. Ukážeme, že hranově maximální bipartitní podgraf náhodného kubického grafu na n vrcholech má asymptoticky skoro jistě méně než 3 2 ·0.9351n hran. Dále ukážeme, že počet vrcholů vrcholově maximálního indukovaného bipartitnho podgrafu náhodného kubického grafu asymptoticky skoro jistě leží v intervalu [0.75n; 0.9082n]. K získání dolního odhadu zkonstruujeme randomizovaný algoritmus na hledání velkého indukovaného biparitního podgrafu v náhodném kubickém grafu. V závěru práce diskutujeme důsledky pro grafové homomorfismy, zejména pro Nešetřilovu Pětiúhelníkovou domněnku.

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/6970

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-269355


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce