Název: Stuctural Aspects of Graph Homomorphisms
Překlad názvu: Stuctural Aspects of Graph Homomorphisms
Autoři: Bok, Jan ; Nešetřil, Jaroslav (vedoucí práce) ; Hubička, Jan (oponent)
Typ dokumentu: Diplomové práce
Rok: 2017
Jazyk: eng
Abstrakt: [eng] [cze]
This thesis is about graph-indexed random walks, Lipschitz mappings and graph homo- morphisms. It discusses connections between these notions, surveys the existing results, and shows new results. Graph homomorphism is an adjacency-preserving mapping between two graphs. Our main objects of study are graph homomorphisms to an infinite path. We are interested in two parameters: maximum range and average range. The average range of a graph is the expected size of the image of a uniformly picked random homomorphism to an infinite path. We obtain formulas for several graph classes and investigate main conjectures on this parameter. For maximum range parameter we show a general formula and an algorithm to compute it for general graphs. Besides that, we study the problem of extending a prescribed partial graph homomorphism to a full graph homomorphism. We show that this problem is polynomial in some cases. 1 Tato diplomová práce se zabývá náhodnými procházkami, Lipschitzovskými zobrazeními a grafovými homomorfismy. Diskutujeme propojení těchto pojmů, dáváme přehled dosavadních výsledků a ukazujeme nové výsledky. Grafový homomorfismus je zobrazení mezi dvěma grafy zachovávající sousednost. Hlavním předmětem zkoumání jsou pro nás homomorfismy grafů do nekonečných cest. Konkrétně nás zajímají dva parametry: maximální rozsah a průměrný rozsah. Průměrný rozsah grafu je očekávaná velikost obrazu uniformně a náhodně zvoleného homomorfismu do nekonečné cesty. Ukazujeme, jak odvodit vztahy pro výpočet průměrného rozsahu na různých třídách grafů a zabýváme se hlavními hypotézami, které se týkají tohoto parametru. Pro maximální rozsah ukazujeme přesný vztah a způsob výpočtu na obecném grafu. Kromě toho studujeme problém rozšiřování částečného homomorfismu, kde ukážeme jeho polynomialitu pro některé případy. 1
Klíčová slova: graphs; homomorphisms; Lipschitz mappings; random walks; graphs; homomorphisms; Lipschitz mappings; random walks

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/90408

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


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 > Diplomové práce