|
|
Petersenovské obarvení a jeho varianty
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Petersenovské obarvení 3-regulárního grafu G je ekvivalentní tzv. normálnímu obarvení za použití pěti barev. Normální obarvení je dobré hranové obarvení ta- kové, že každá hrana je spolu se svými čtyřmi sousedy obarvena dohromady třemi nebo pěti různými barvami. Podle Jaegerovy hypotézy lze každý 3-regulární graf bez mostů petersenovsky obarvit. Platnost hypotézy by dokázala další zajímavá tvrzení pro 3-regulární grafy. V tomto textu se budeme zabývat normálním obar- vením pro větší počet barev. Z Jaegerovy věty o nenulovém Z2 3 -toku plyne, že každý graf bez mostů lze normálně obarvit sedmi barvami. Zde dokážeme exis- tenci obarvení devíti barvami pro grafy s mostem, s řezem velikosti dva nebo s trojúhelníkem nezávisle na Jaegerově větě. Důkaz využívá myšlenku Andersenova důkazu existence silného hranového obarvení 3-regulárních grafů deseti barvami. V závěru řekneme, jak by mohl jít důkaz dokončit pro zbylé třídy 3-regulárních grafů. 1
|
|
|
Generování grafů
Mohelníková, Lucie ; Dvořák, Zdeněk (vedoucí práce) ; Jelínek, Vít (oponent)
Název práce: Generování grafů Autor: Lucie Mohelníková Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: Mgr. Zdeněk Dvořák,Ph.D., Informatický ústav Univerzity Karlovy Abstrakt: Zabýváme se generováním grafů z vybraných tříd, zejména pak grafů nakreslených na plochách. Zaměřujeme se na metodu generování za pomoci dekontrakcí vrcholů, pro níž je zásádní identifikace počátečních (ireducibilních) grafů. Uvádíme přehled výsledků o ireducibilních triangulacích a kvadrangulacích různých ploch, zejména pak nízkého rodu (rovina, projektivní rovina, Kleinova láhev). Hlavním přínosem této práce je identifikace 21 ireducibilních triangulací toru, čímž dokazujeme výsledek Lawrencenka bez použití výpočetní techniky. Klíčová slova: ireducibilní, triangulace, torus
|
|
|
Výpočetní složitost v teorii grafů
Doucha, Martin ; Kratochvíl, Jan (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Tato práce zavádí dvě nové parametrizace grafových úloh zobecňující vrcholové pokrytí, které v hierarchii grafových parametrizací vyplňují část prostoru mezi vrcholovým pokrytím a klikovou šířkou. Dále zde zkoumáme parametrizovanou složitost hledání Hamiltonovské cesty a kružnice, klasického barvení grafu, problému Precoloring extension a Equitable coloring pro tyto nové parametrizace. Kromě problému Precoloring extension, který je pro jednu parametrizaci W[1]-těžký, se pro všechny ostatní problémy podařilo najít FPT algoritmus pro obě parametrizace. Hranici mezi třídami FPT a W[1] se tak u těchto problémů podařilo posunout blíže směrem k parametrizaci klikovou šířkou.
|
|
|
Szemerédi Regularity Lemma a jeho aplikace v kombinatorice
Hladký, Jan ; Kráľ, Daniel (vedoucí práce) ; Dvořák, Zdeněk (oponent)
V práci podáme důkaz domněnky Loebla, Komlóse a Sósové (1995) pro husté grafy. Dokážeme následující tvrzení. Pro libovolné q > 0 existuje číslo n0 takové, že pokud má libovolný graf G řadu n > n0 alespoň polovinu vrcholů se stupněm alespoň k > qn, pak G obsahuje každý strom na k+1 vrcholech jako podgraf. Tím vylepšujeme předchozí výsledky autorů Zhao (2002) a Piguet a Stein (2007). Ukážeme, že v jistých případech lze předpoklady věty oslabit. Je diskutována dolní mez k problému. Jako důsledek hlavní věty dostaneme těsný odhad Ramseyova čísla dvou stromů. Důkaz hlavní věty kombinuje vnořovací techniku založenou na Regularity Lemmatu s Metodou stability. Výsledku bylo dosaženo ve společné práci s Dianou Piguet.
|
|
|
Distributed computing
Šišaj, Róbert ; Novotný, Miroslav (oponent) ; Dvořák, Zdeněk (vedoucí práce)
Cieľom práce je vytvorenie systému pre distribúciu výpočtov pre menšie siete LAN. Systém by mal tvoriť platformu pre rôzne aplikácie, ktorým umožní paralelné spracovanie výpočtovo náročných úloh (hľadanie prvočísel, renderovanie videosekvencií, úpravy fotografií, ...). Čitateľ sa zoznámi s tematikou distribuovaných systémov, dozvie sa o ich výhodách i nevýhodách a osvojí si základné pojmy z tejto oblasti. Súčasťou práce je porovnanie s podobnými existujúcimi systémami (SETI@home, distributed.net). Zahrnutá je aj analýza slabín navrhovaného systému a prípadné námety na jeho vylepšenie do budúcnosti.
|
|
| |
|
|
Zakázané minory pro apexové třídy grafů
Klimošová, Tereza ; Dvořák, Zdeněk (oponent) ; Kráľ, Daniel (vedoucí práce)
V předložené práci se zabýváme hledáním minimálních zakázaných minorů, neboli obstrukcí, pro třídu apexů částečných 2-stromů. Jelikož je tato třída uzavřená na minory, má podle Robertson-Seymourovy věty konečnou množinu obstrukcí. Množina obstrukcí je jedna z možných charakterizací každé třídy uzavřené na minory. V práci analyzujeme strukturu obstrukcí pro třídu apexů částečných 2-stromů a díky její znalosti nacházíme všechny obstrukce s výjimkou speciálního typu obstrukcí, které mají path-width 3. Při hledání obstrukcí využíváme znalosti obstrukcí pro příbuzné třídy grafů.
|
|
| |
|
| |
|
| |
host ::
RSS.