|
|
Zakázané minory pro apexové třídy grafů
Klimošová, Tereza ; Kráľ, Daniel (advisor) ; Dvořák, Zdeněk (referee)
In the present work we search for the minimal forbidden minors (also called obstructions) for the class of apexes of partial 2-trees. Because this class is minor closed, by Robertson-Seymour's theorem it has a nite set of obstructions. The set of obstructions is one of the possible characterizations of every minor closed class. We analyze a structure of possible obstructions for the class of apexes of partial 2-trees and thanks to this knowledge, we can classify all the obstructions for the class of apexes of partial 2-trees except for some special type of them with pathwidth three. We use the knowledge of obstructions for related classes of graphs.
|
|
|
The Past and the Present of the Talent Search in Table Tennis Case
Dvořák, Zdeněk ; Suchý, Jiří (advisor) ; Štochl, Jan (referee)
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 (advisor) ; Dvořák, Zdeněk (referee)
We study two deterministic analogues of random walks. The first is the chip-firing game, a single player game played by moving chips around a directed graph, popularised by Björner and Lovász. We find an efficient simulation of boolean circuits and Turing machines using instances of the chip-firing game - after assigning a fixed strategy to the player. The second is the Propp machine, or the rotor router model, a quasirandom model intro- duced by Priezzhev. We improve results of Kijima et al. and show a bound of O(m) on the discrepancy of this process from a random walk on d-regular graphs with m edges. 1
|
|
| |
|
|
Structural Theory of Graph Immersions
Hruška, Michal ; Dvořák, Zdeněk (advisor) ; Klimošová, Tereza (referee)
Immersion is a notion of graph inclusion related to the notion of graph minors. While the structural theory of graph minors is extensive, there are still numerous open problems in the structural theory of graph immersions. Kuratowski's theorem claims that the class of graphs that do not contain a subdivision of the graphs K3,3 and K5 is exactly the class of planar graphs. The main goal of this thesis is to describe the structure of the graphs that do not contain an immersion of K3,3. Such graphs can be separated by small edge cuts into small graphs or planar 3-regular graphs. 1
|
|
|
Sufficient conditions for embedding trees
Rozhoň, Václav ; Klimošová, Tereza (advisor) ; Dvořák, Zdeněk (referee)
We study sufficient degree conditions that force a host graph to contain a given class of trees. This setting involves some well-known problems from the area of extremal graph theory. The most famous one is the Erdős-Sós conjecture that asserts that every graph with average degree greater than k − 1 contains any tree on k + 1 vertices. Our two main results are the following. We prove an approximate version of the Erdős-Sós conjecture for dense graphs and trees with sublinear max- imum degree. We also study a natural refinement of the Loebl-Komlós-Sós conjecture and prove it is approximately true for dense graphs. Both results are based on the so-called regularity method. The second mentioned result is a joint work with T. Klimošová and D. Piguet. 1
|
|
|
Vliv technologie kompostování biologicky rozložitelných odpadů na kvalitu kompostu
DVOŘÁK, Zdeněk
The thesis deals with composting and ways of handling biodegradable waste and biodegradable municipal waste. It explains the terms related to composting and processing of BW and BMW and clarifies the difference between humus and primary organic matter and its composition. Furthermore, the thesis covers qualitative and quantitative features of compost, raw material composition of the dump, and factors influencing the process of decomposition itself. The practical part of the thesis describes the quality of the compost from the municipal composting plant Písek. This part also includes a description of the composting plant and a description of the composting process. The main part and the goal of the thesis is to determine the ion-exchange capacity T according to Sandhoff and to suggest the optimal composting technology in the Municipal composting plant Písek.
|
|
|
3-Coloring Graphs on Torus
Pekárek, Jakub ; Dvořák, Zdeněk (advisor) ; Šámal, Robert (referee)
The theory of Dvořák et al. shows that a 4-critical triangle-free graph embedded in the torus has only a bounded number of faces of length greater than 4 and that the size of these faces is also bounded. We study the natural reduction in such embedded graphs-identification of opposite vertices in 4-faces. We give a computer-assisted argument showing that there are exactly four 4-critical triangle-free irreducible toroidal graphs in which this reduction cannot be applied without creating a triangle. Using this result we demonstrate several properties that are necessary for every triangle-free graph embedded in the torus to be 4-critical. Most importantly we demonstrate that every such graph has at most four 5-faces, or a 6-face and two 5-faces, or a 7-face and a 5-face, in addition to at least seven 4-faces.
|
|
|
Approximation of independence number of planar graphs
Berg, Michal ; Dvořák, Zdeněk (advisor) ; Fiala, Jiří (referee)
The independent set problem is a well-known NP-complete problem, which is NP- complete even for planar graphs. But unlike general graphs, there exists an polynomial- time approximation scheme for planar graphs. We are going to describe an exact algorithm for maximum independent set problem in planar graphs based on dynamic programming. This algorithm can be easily modified to an polynomial-time approximation scheme. We implemented both versions of this algorithm and tested them. We used a few random planar graph generators for that. We compared the exact algorithm with another two algorithms. We compared the approximation algorithm with its exact version and measured its real approximation ratio and also its time complexity in comparison with the exact version. We discovered that the exact algorithm usually finishes the computation faster than the other two algorithms. We also discovered that the approximation version has a better approximation ratio compared to the theoretical minimum with good time complexity. 1
|
|
|
Algorithms based on bounded expansion - implementation and evaluation
Rapavá, Jana ; Dvořák, Zdeněk (advisor) ; Knop, Dušan (referee)
This thesis builds upon the result that a lot of graph classes - namely classes with bounded expansion - have properties which make deciding graph problems definable in first-order logic easier. One very important example of such a problem is subgraph isomorphism. The purpose of this work is to implement and test proposed algorithm for this problem (which has a linear time complexity in relation to the size of graph we are looking for the subgraph in). Powered by TCPDF (www.tcpdf.org)
|
guest ::
RSS feed.