|
|
Navigation in Public Transport
Turic, Matúš ; Křivka, Zbyněk (referee) ; Burget, Radek (advisor)
This master's thesis deals with the issue of traveling in public transport. In the first part the author informs about similar applications and theories necessary for understanding the problems. In the second part, the author describes the design and behavior of the mobile and server application, including the used technologies. Created mobile application has the task of navigating the user from one point to another in the shortest possible time, while it should be possible to replace the current route with faster one.
|
|
|
Medical Image Segmentation Based on Graph Cut with Shape Prior
Kozlová, Dominika
This paper deals with a graph-based image segmentation and its improvement by using the information about the shape of the object for creating specific graph architecture (template). Improved method allows the cut to prefer more complicated structures, especially when the image contains a lot of noise and the object is hardly indistinguishable from the background. Algorithm was tested on simulated data and real CT and MRI images of vertebra and brain in 2D. Method was also extended to 3D further purposes.
|
|
|
Impact of stochastic link failures on push-sum protocol
Ecler, Tomáš ; Škorpil, Vladislav (referee) ; Kenyeres, Martin (advisor)
This master’s thesis deals with the distributed computing and mathematical tools for modelling the distributed systems. Firstly, my attention is focused on a description of the distributed algorithms, characteristic failures for the distributed systems, and mathematical tools for an analysis of the distributed systems.The experimental part is concerned with the impact of stochastic link failures on the chosen parameters of the protocol Push-sum, namely the deviation of the final states from the average value, the convergence rate of the protocol, the distribution of the final states, and the distribution of the convergence rates. My intention is demonstrated using Matlab on a tree, a ring, a line, a star, and a fully-connected mesh topology. Was analyzed two functionalities of the protocol Push-sum, namely an estimation of the average value and an estimation of sum.
|
|
|
Stochastic Optimization on Random Networks
Sigačevová, Jana ; Houda, Michal (advisor) ; Branda, Martin (referee)
The deterministic theory of graphs and networks is used successfully in cases where no random component is needed. However in practice, a number of decision-making and conflict situations require the inclusion of a stochastic element directly into the model. The objective of this thesis is the introduction of stochastic optimization and its application on random networks. The reader will become familiar with three approaches to stochastic optimization. Namely two-stage optimization, multi-stage optimization and chance constraint optimization. Finally, the studied issue is demonstrated on a real telecommunication network example.
|
|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (advisor) ; Manlove, David (referee) ; Fiala, Jiří (referee)
Title: Computational Complexity in Graph Theory Author: Eva Jelínková Department: Department of Applied Mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., Department of Applied Mathematics Abstract: We address problems from graph theory, especially from the computational complexity point of view. In the first part of the thesis we address the computational complexity of problems related to Seidel's switch- ing of graphs. We prove that the problem to decide if a given graph can be switched to contain at most a given number of edges is NP-complete, even for graphs with bounded density. We thus partially answer a question of Matoušek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014]. We also describe infinitely many graphs H such that it is NP-complete to decide if a given graph is switching-equivalent to a graph that does not contain H as an induced subgraph. We thus close an open problem of Kratochvíl, Nešetřil and Zýka [Annals of Discrete Math. 51, 1992]. In the second part of the thesis we address the topic of matchings under preferences. We focus on the housing market problem, in particular, on the model with duplicate houses. We present a 2-approximation algorithm for the maximum number of satisfied agents when the preference lists of agents are trichotomic. On the other hand, we...
|
|
|
Mathematical Environments Mazes and Cycle Path with Primary School Pupils
Bartoňová, Jana ; Slezáková, Jana (advisor) ; Kloboučková, Jaroslava (referee)
The diploma thesis deals with the mathematical environments Mazes and Cycle Paths. The first part is concerned with the definition of two opposite educational styles, transmissive and constructivistic. Within the constructivistic educational style it is also focused on schema-oriented education and on defining its principles for teaching mathematics by Hejný's method. It also introduces a new term genetic constructivism - its author proves that Hejný's mathematics and its didactic environments are embedded in ancient history. This diploma thesis gives an answer to the question of why the environments Mazes and Cycle Paths belong to the teaching of mathematics, and therefore, on what mathematical basis it stands. It is for this reason that it provides insight into the fundamentals of graph theory. It is focused on the historical aspect of terms maze and cycle path and charts exercises in Hejný's textbooks of mathematics from environments Mazes and Cycle Paths. The aim of research is to expand the collection of exercises from these two environments, to chart pupils' solving strategies and identify effective teaching methods in accordance with the schema-oriented education, which has been studied in seven experiments. The last part of this diploma thesis presents a didactic game, which is focused on...
|
|
| |
|
|
Concepts from graph theory in primary school mathematics curriculum
Mutinová, Tatiana ; Kloboučková, Jaroslava (advisor) ; Slezáková, Jana (referee)
Concepts from graph theory in primary school mathematic curriculum Ing. Tatiana Mutinová, 2014 Abstract This diploma thesis is focused on graph theory, especially on the concepts that are used in primary school mathematic curriculum. Furthermore it shows the reasons why it is necessary to include these graph concepts in young pupil's education. In the theoretical part, basic terms and definitions from chosen parts of graph theory are mentioned and few examples demonstrate how the applications of graph theory can help with solving real-life situations. The practical part summarized the current use of some graph theory concepts in primary school mathematic curriculum. This part also includes the demonstration of the graded series of problems and the sheets of exercises that could be usable in introducing and practising of some graph concepts. The experiment with mosaics, that was carried out within this diploma thesis, is an illustration how to connect mathematical and non-mathematical world and how to integrate research activities in young pupil's education. Key words: mathematics, graph theory, graph vertex, degree of graph vertex, edge of graph, problem of two colours, child of primary school
|
|
|
Optimisation using graph searching on special graph classes
Chejnovská, Anna ; Gavenčiak, Tomáš (advisor) ; Šámal, Robert (referee)
For a given graph we define the minimum path cover as a minimum cardinality set of vertex disjoint paths covering all the vertices of the graph. This problem is one of the usual generalization of the Hamiltonian path problem. In this thesis we based our work on a paper Corneil et al. (2013) presenting a certifying algorithm for the minimal path cover problem on cocomparability graphs (the complement of graph of strict partial order). We first introduce this algorithm an then we experimentally examine its robustness to five operations on edges and vertices of the graph. We also analyse the impact of these operation on the size of the minimal path cover theoretically. Powered by TCPDF (www.tcpdf.org)
|
|
|
Cops and robber game on directed complete graphs
Slívová, Veronika ; Gavenčiak, Tomáš (advisor) ; Jelínek, Vít (referee)
BACHELOR THESIS - ABSTRACT Veronika Slívová This thesis focuses on the game Cops and robber on tournaments (a graph we gain by orienting each edge of undirected complete graph). We show that tournaments containing a vertex with large outdegree have small cop number. On the other hand we prove that the number of cops we need to capture the robber on any tournament is not bounded. Then we study circulant tournaments and graphs obtained by cyclically orienting each triple of Steiner triple system. We disprove the conjecture made by Geňa Hahn that the cop number of any graph obtained by orientation Steiner triple system is bounded. We also show that the cop number of circulant tournaments cannot be bounded. Then we focus on the 2-fast cop and the 2-fast robber variant of the game. We prove that one 2-fast cop wins on any tournament. On the contrary in case that the game is played on tournament whose vertices have the same outdegree, the 2-fast robber is captured trivially or runs away indefinitely.
|
guest ::
