|
|
Zakázané minory pro apexové třídy grafů
Klimošová, Tereza ; Kráľ, Daniel (vedoucí práce) ; Dvořák, Zdeněk (oponent)
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ů.
|
|
|
Minulost a současnost výběru talentů na příkladu stoního tenisu
Dvořák, Zdeněk ; Suchý, Jiří (vedoucí práce) ; Štochl, Jan (oponent)
Název Minulost a současnost výběru talentů na příkladu stolního tenisu Název v angličtině The past and the present of the choice of talents in tahle tennis Cíle práce: Popsat výběr sportovních talentů ve stolním tenise jak byl prováděn v mitiulosti; tj. před rokem 1990 a dnes; tj. od roku 2000 po dnešek. Navrhnout změny výběru talentů nebo alespoň v odborné veřejnosti vyvolat diskuzi o těchto změnách. Metody práce: Neuvádím z důvodů rešeršního a popisného charakteru práce. Výsledky práce: Popsání výběru talentů před rokem 1990 a po roce 2000, jejich srovnání pomocí používané literatury a praktických zkušeností. Vysvětlení důvodů navrhovaných změn náhledu na výběr talentů na základě praktických zkušeností práce s talentovanou mládeží. Klíčová slova: Stolní tenis, talent, výběr talentů, kolektivní myšlení, regenerace.
|
|
|
Pseudorandom walks and chip firing games
Mittal, Parth ; Koucký, Michal (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Studujeme dva deterministické procesy analogické náhodným procházkám na grafech. První je hra s vystřelováním žetonů, chip-firing game, zavedená Björnerem a Lovászem. Jedná se o hru jednoho hráče hranou pohybem žetonů po orientovaném grafu. Našli jsme efektivní simulaci booleovských obvodů a Turingových strojů pomocí této hry. Druhým procesem je Prop- pův stroj, neboli rotor-router model, pseudonáhodný proces zavedený Priez- zhevem. Zlepšujeme výsledky Kijima a spol. a ukazujeme novou horní mez O(m) na diskrepanci tohoto procesu na grafech stupně d s m hranami. 1
|
|
| |
|
|
Structural Theory of Graph Immersions
Hruška, Michal ; Dvořák, Zdeněk (vedoucí práce) ; Klimošová, Tereza (oponent)
Imerze je pojem inkluze grafů související s pojmem grafových minorů. Zatímco strukturální teorie grafových minorů je rozsáhlá, ve strukturální teorii grafových imerzí je stále velké množství otevřených problémů. Kuratowského věta tvrdí, že třída grafů, které neobsahují dělení grafů K3,3 a K5 je právě třída rovinných grafů. Hlavním cílem práce je popsat strukturu grafů neobsahujících imerzi K3,3. Takové grafy mohou být rozděleny pomocí malých hranových řezů na malé grafy nebo rovinné 3-regulární grafy. 1
|
|
|
Sufficient conditions for embedding trees
Rozhoň, Václav ; Klimošová, Tereza (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Studujeme podmínky na stupně vrcholů, které vynucují, že daný graf obsahuje libovolný strom z dané třídy. Tento typ problémů zahrnuje některé známé problémy z oblasti extremální teorie grafů. Nejslavnějším z nich je domněnka Erdős-Sósové, která tvrdí, že každý graf s průměrným stupněm vyšším než k − 1 obsahuje libovolný strom na k + 1 vrcholech. Naše dva hlavní výsledky jsou následující. Dokazujeme přibližnou verzi domněnky Erdős-Sósové pro husté grafy a stromy se sublineárním maximál- ním stupněm. Dále studujeme přirozené zobecnění domněnky Loebl-Komlós- Sósové a opět dokážeme přibližnou verzi této domněnky pro husté grafy. Oba výsledky jsou založeny na takzvané regularity metodě. Druhý výsledek je společnou prací s T. Klimošovou a D. Piguet. 1
|
|
|
Vliv technologie kompostování biologicky rozložitelných odpadů na kvalitu kompostu
DVOŘÁK, Zdeněk
Diplomová práce se zabývá kompostováním a způsoby nakládání s biologicky rozložitelnými odpady a biologicky rozložitelnými komunálními odpady. Vysvětlení pojmů spojených s kompostováním a zpracováním BRO a BRKO a rozdílem mezi humusem a primární organickou hmotou a jejím složením. Dále kvalitativními a kvantitativními znaky kompostu, surovinovou skladbou zakládky a faktory ovlivňujícími samotný proces tlení. Praktická část diplomové práce popisuje kvalitu kompostu z městské kompostárny Písek, popis kompostárny, a popis prováděného kompostovacího procesu. Hlavní částí a samotným cílem práce je stanovení iontovýměnné kapacity T podle Sandhoffa a navržení optimálního kompostovací technologie v Městské kompostárně Písek.
|
|
|
3-Coloring Graphs on Torus
Pekárek, Jakub ; Dvořák, Zdeněk (vedoucí práce) ; Šámal, Robert (oponent)
Dvořák et al. dokázali, že 4-kritická graf bez trojúhelníků vnořený v toru má pouze omezeně mnoho stěn délky větší než 4 a velikost těchto stěn je také omezena. V této práci studujeme operaci redukce těchto vnořených grafů pomocí sjednocení protějších vrcholů ve 4-stěnách. Představíme počítačem asistovaný důkaz ukazující, že existují právě čtyři 4-kritické grafy bez trojúhelníků vnořené do toru, které jsou irreducibilní, tedy na ně není možné použít redukci bez vzniku trojúhelníků. Pomocí tohoto výsledku ukážeme několik vlastností, které nutně platí pro jakýkoliv 4-kritický graf bez trojúhelníků vnořený v toru. Především ukážeme, že každý takový graf má nejvýše čtyři 5-stěny nebo 6-stěnu a dvě 5-stěny nebo 7-stěnu a 5-stěnu, a k tomu alespoň sedm 4-stěn.
|
|
|
Aproximace nezávislosti rovinných grafů
Berg, Michal ; Dvořák, Zdeněk (vedoucí práce) ; Fiala, Jiří (oponent)
Problém nezávislé množiny je dobře známý NP-úplný problém, který je NP-úplný i pro rovinné grafy. Ale na rozdíl od obecných grafů, pro rovinné grafy existuje polynomiální aproximační schéma. Popíšeme přesný algoritmus pro hledání největší nezávislé množiny v rovinných grafech založený na dynamickém programování. Tento přesný algoritmus lze jednoduše upravit na polynomiální aproximační schéma. Obě jeho verze jsme implemen- tovali a otestovali. Při tom jsme používali několik generátorů náhodných rovinných grafů. Přesný algoritmus jsme experimentálně srovnávali s dalšími dvěma algoritmy. Aproximační algoritmus jsme srovnávali s jeho přesnou verzí a měřili skutečný aproximační poměr a také jeho časovou náročnost v porovnání s přesnou verzí. Zjistili jsme, že přesný algoritmus na zvolených grafech většinou dokončí výpočet rychleji než ostatní dva algoritmy. Také jsme zjistili, že aproximační verze má vzhledem k teoretickému minimu většinou lepší apro- ximační poměr s dobrou časovou složitostí. 1
|
|
|
Algorithms based on bounded expansion - implementation and evaluation
Rapavá, Jana ; Dvořák, Zdeněk (vedoucí práce) ; Knop, Dušan (oponent)
Tato bakalářská práce navazuje na větu, která říká, že mnoho tříd grafů - konkrétně třídy s omezenou expanzí - má vlastnosti zjednodušující rozhodování grafových problémů definovatelných v logice prvního řádu. Důležitým příkladem takového problému je izomorfismus podgrafů. Cílem této práce je implementovat a otestovat navrhnutý algoritmus pro tento problém (který má lineární časovou složitost vzhledem k velikosti grafu, ve kterém hledáme podgraf). Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.