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.