|
|
Distinguishing pairs of words using finite automata
Bilan, Daria ; Koucký, Michal (advisor) ; Šámal, Robert (referee)
This work considers a fundamental open problem in informatics - distin- guishing two words by a deterministic finite automaton with the smallest pos- sible number of states. We review the existing research, where proven lower and upper bounds in terms of words' lengths differ exponentially. Next, we empirically try two approaches not studied previously: analysis of discerning sets and application of randomly generated automata. We show that the first approach does not help improve the bounds for the main problem, while the random automata could be successful for randomly taken word pairs but not for all of them. A combination of a randomly generated automaton with the best performing already known, though, may decrease an average number of states by several orders of magnitude. We propose several topics for further investigation based on the obtained experimental results. 1
|
|
|
Coloring triangle-free graphs on the torus
Urmanov, Eldar ; Dvořák, Zdeněk (advisor) ; Šámal, Robert (referee)
Pekárek and Dvořák (2021) proposed a linear-time algorithm to decide 3-colorability of triangle-free graphs drawn on the torus. We implemented this algorithm efficiently and evaluated its performance on a natural class of graphs. Pekárek and Dvořák (2021) popsali algoritmus rozhodující 3-obarvitelnost grafu bez trojúhelníků nakreslených na toru v lineárním čase. Tato práce popisuje efektivní implementaci algoritmu a vyhodnocení jejího výkonu na přirozené tridě grafů. 1
|
|
|
Structure of flow-continuous mappings in algebraic context
Hušek, Radek ; Šámal, Robert (advisor) ; Bonamy, Marthe (referee) ; Kaiser, Tomáš (referee)
We explore the structure of the cycle space of the graphs - most notably questions about nowhere-zero flows and cycle double covers. We touch several facets of this field. First we show that there are edge 2-connected graphs which distinguish Z2 2- and Z4- connectivity (group connectivity which is a strengthening of nowhere-zero flows). Then we examine a conjecture of Matt DeVos which asserts existence of group flows given existence of a graph homomorphism between suitable Cayley graphs. We introduce a strengthening of this conjecture called strong homomorphism property (SHP for short) which allows splitting vertices (and hence a reduction to cubic graphs). We conjecture that SHP holds for every graph and the smallest group in which the graph has a nowhere- zero flow and we prove that both SHP and the original conjecture imply existence of cycle double covers with few cycles. The question we discuss the most is counting objects on graphs - especially counting circuit double covers. We shows an almost exponential lower bound for graphs on surfaces with nice embeddings and we also show that this bound does not apply to Flower snarks. Then we shows quite precise bound for flower snarks and we also improve the lower bound for planar graphs to an exponential one. Along the way we build a framework for counting...
|
|
|
Structural properties of graphs---probabilistic and deterministic point of view
Hladký, Jan ; Šámal, Robert (advisor) ; Pawlas, Zbyněk (referee)
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.
|
|
|
Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe
Dvořák, Pavel ; Valla, Tomáš (advisor) ; Šámal, Robert (referee)
In this thesis we study positional games, especially multidimensional tic-tac-toe. We compare present advanced algorithms (Pn-search, Db-search and λ-search) for position solving in positional games. We apply the algorithms on the do- main of 43 and 53 games, which are the first nontrivial cases of 3-dimensional tic-tac-toe. We parallelize Pn-search for cases when there are more starting po- sitions. We apply Pn-search as a single-thread task and we solve how to share the transposition table with solved positions. Our main and clearly theoretical result is the characterization of the group of all automorphisms of combinatorial cube nd with the same set of lines as multidimensional tic-tac-toe has. This is a generalization of Silver [The American Mathematical Monthly, Vol. 74, No. 3, 1967], who characterized the automorphisms of the game 43 . 1
|
|
|
Generalized Moran process
Svoboda, Jakub ; Šámal, Robert (advisor) ; Balko, Martin (referee)
The Moran process is a model for simulating evolutionary dynamics. In that model, one mutant with higher fitness is introduced to a structured population. Evolution is simulated in rounds. In one round, individual is selected proportio- nally to its fitness and spreads to the place of a random neighbour. In this thesis, we motivate the Moran process, present basic results, and define our variant. We work in a vertex dependent model; every individual has fitness according to its type and occupied vertex. In the vertex dependent model we prove two theorems about the number of steps the process has to make to get to the stable state. We show that on the complete graph, the process takes only polynomially many steps and we find a graph where the process take exponentially many steps, but in the normal settings the number of steps is the same as on the complete graph. 1
|
|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
Binary matrices not containing a smaller matrix as a submatrix have become an interesting topic recently. In my thesis, I introduce two new algorithms to test whether a big square binary matrix contains a smaller binary matrix together with a process using randomness, which approximates a uniformly random matrix not containing a given matrix. The reason to create such algorithms is to allow researchers test their conjectures on random matrices. Thus, my thesis also contains an effective cross- platform implementation of all mentioned algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Dots and Bpxes implementation
Balko, Martin ; Pangrác, Ondřej (advisor) ; Šámal, Robert (referee)
Title: Dots and Boxes implementation Author: Martin Balko Department: Department of Applied Mathematics Supervisor: RNDr. Ondřej Pangrác, Ph.D. Supervisor's email address: pangrac@kam.mff.cuni.cz Abstract: The presented thesis deals with the analysis of a popular logical game Dots and Boxes and its generalized versions. It focuses on the different methods and algorithms of opponent's artificial intelligence. The result of the work is implementation of the generalized version of this game in which a board editing, game with more than two players on the several levels of difficultness and the different face valuations are possible. Keywords: Dots and Boxes, Nimstring, Advanced Chain Counting
|
|
|
Group connectivity of graphs
Mohelníková, Lucie ; Šámal, Robert (advisor) ; Pangrác, Ondřej (referee)
Název práce: Grupová souvislost graf· Autor: Lucie Mohelníková Katedra: Informatický ústav Univerzity Karlovy Vedoucí diplomové práce: Mgr. Robert 'ámal,Ph.D., Informatický ústav Univerzi- ty Karlovy Abstrakt: Zabývali jsme se grupovou souvislostí graf·, zejména pak Z2 2- a Z4- souvislostí. Implementovali jsme v jazyce C++ test, zda je graf grupově souvislý a pomocí něho hledáme grafy, které jsou grupově souvislé v jedné ze zkoumaných grup a v druhé nikoliv. Zkoumali jsme grafy, které vzniknou podrozdělením hran několika speciálních graf· např. K4 a krychle. Hlavním přínosem této práce je nalezení dvou graf·, které jsou Z4-souvislé a nejsou Z2 2-souvislé. Pomocí druhé nezávislé implementace testu na grupovou souvislost napsané v jazyce Prolog s využitím CSP jsme ověřili, že tyto grafy jsou Z4-souvislé. Analyticky jsme dokázali, že jeden z nalezených graf· není Z2 2-souvislý. Klíčová slova: grupová souvislost, toky, grupa
|
|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (advisor) ; Paulusma, Daniel (referee) ; Šámal, Robert (referee)
Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles
|
guest ::
