|
|
Optimization of ditribution of products
Bílek, Jan ; Pangrác, Ondřej (advisor) ; Šámal, Robert (referee)
The thesis deals with the Vehicle Routing problem with vehicles having limited capacity. We mainly focus on the variant with heterogeneous fleet of vehicles each having its variable and fixed costs. Algorithm designed to solve the problem first finds an feasible initial solution by probabilistically modified Clarke-Wright savings method and then improves it by techniques based on local search. Obtained results are compared with state-of-the-art algorithms on well- known benchmarks. The implementation of the algorithm in Java is part of the work. 1
|
|
|
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
|
|
|
Circuits and matchings in graphs
Tesař, Karel ; Pangrác, Ondřej (advisor) ; Šámal, Robert (referee)
O grafu řekneme, že je k-linkovaný, pokud pro každých k dvojic jeho vrchol· existují navzájem disjunktní cesty, které dané dvojice spojují. Existuje vztah mezi k-linkovaností a vrcholovou souvislostí grafu. V této práci hledáme vztah mezi vrcholovou souvislostí grafu a vlastností, že každých k jeho disjunktních hran leží na společné kružnici. Tento problém se dá řešit pomocí k-linkovanosti. Naším cílem je dosáhnout lepších odhad· na souvislost, resp. jiných postačujících podmínek než těch, které jsou známe pro k-linkovanost. 1
|
|
|
Lipschitz mappings of discrete sets
Kaluža, Vojtěch ; Matoušek, Jiří (advisor) ; Šámal, Robert (referee)
In this thesis we consider Feige's question of whether there always exists a constantly Lipschitz bijection of an n2 -element set S ⊂ Z2 onto a regular lattice of n × n points in Z2 . We propose a solution of this problem in case the points of the set S form a long rectangle or they are arranged in the shape of a square without a part of its interior points. The main part is a summary of Burago's and Kleiner's article [2] and the article by McMullen [12] dealing with the problem of existence of separated nets in R2 that are not bi-Lipschitz equivalent to the integer lattice. This problem looks similar to Feige's problem. According to these articles we construct a separated net that is not bi-Lipschitz equivalent to the integer lattice, using a positive bounded measurable function that is not the Jacobian of a bi-Lipschitz homeomorphism almost everywhere. We present McMullen's construction of such a function and we complete his proof of its correctness. 1
|
|
|
Petersen coloring and variants
Bílková, Hana ; Šámal, Robert (advisor) ; Dvořák, Zdeněk (referee)
The Petersen coloring of 3-regular graph G is equivalent to the normal coloring by five colors. The normal coloring is a good coloring of edges such that every edge and its four neighbours have together three or five different colors. Jaeger conjectures that every bridgeless 3-regular graph has a Petersen coloring. If the conjecture were true, it would imply other interesting statements about 3-regular graphs. In this text we investigate normal coloring by more than five colors. Jaeger theorem about nowhere-zero Z2 3 -flow implies that every bridgeless graph has normal coloring by seven colors. Independently on the Jaeger theorem, we prove the existence of normal coloring by nine colors for graphs with a bridge, a cut of size two or with a triangle. The idea of our proof comes from Andersen's proof of existence of strong coloring by ten colors for 3-regular graphs. Finally, we sketch the idea of the proof for other classes of 3-regular graphs. 1
|
|
|
Quoridor implementation
Boroš, Martin ; Pangrác, Ondřej (advisor) ; Šámal, Robert (referee)
The aim of this thesis is to analyze the game Quoridor. We propose and implement decision-making algorithms for computer players. Quoridor is a relatively new board game for two or four players. It can be viewed as the problem of finding the shortest path in a graph. In addition, edges are allowed to be removed. First, we introduce Quoridor, its history and rules. Then, we propose a suitable notation and a representation of the game. Next, we discuss decision-making algorithms for a twoplayer game and their necessary changes and improvements for a four-player game. Finally, we introduce the application that was developed to implement and evaluate the proposed ideas.
|
|
|
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
|
|
|
Dots and Bpxes implementation
Balko, Martin ; Šámal, Robert (referee) ; Pangrác, Ondřej (advisor)
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
|
|
|
Structural properties of graphs---probabilistic and deterministic point of view
Hladký, Jan ; Pawlas, Zbyněk (referee) ; Šámal, Robert (advisor)
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.
|
|
| |
guest ::
