|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (advisor) ; Koubek, Václav (referee) ; Sereni, Jean-Sébastein (referee)
One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are...
|
|
|
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
|
|
|
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...
|
|
|
Počítačové modelování větvených polymerů
Preisler, Zdeněk ; Uhlík, Filip (advisor) ; Netopilík, Miloš (referee)
In this work we study properties of branched polymers in a good solvent. We focus on problematic related to the size exclusion chromatography and predicting elution behavior of randomly branched polymers. We developed a software for generating self-avoiding walks (SAW) of any given non-looping architecture on a cubic lattice using Monte Carlo (MC) simulation and vali- date its reliability by presenting the scaling of different architectures: linear, 3-arm star and 6-arm star and asymmetric star. We calculate distribu- tion coefficients and calibration curves for size exclusion chromatography for various architectures to validate that the hydrodynamic radius is more suitable for predicting elution volume than the radius of gyration. Then we propose a new method for, although approximate, a very fast estimation of radius of gyration and hydrodynamic radius for different architecture using a graph method. It is done by comparing MC results with results obtained from graph theory. Then we introduce a correction to graph-theory results to fit the MC. At the end we present depletion layer calculation from MC and self-consistent field (SCF) method for polymers and their comparison. We show how calculation of depletion layer using SCF can be improved to get significantly better agreement with MC results. v
|
|
| |
|
|
Immersions and edge-disjoint linkages
Klimošová, Tereza ; Dvořák, Zdeněk (advisor) ; Kráľ, Daniel (referee)
Graph immersions are a natural counterpart to the widely studied concepts of graph minors and topological graph minors, and yet their theory is much less developed. In the present work we search for sufficient conditions for the existence of the immersions and the properties of the graphs avoiding an immersion of a fixed graph. We prove that large tree-with of 4-edge-connected graph implies the existence of immersion of any 4-regular graph on small number of vertices and that large maximum degree of 3-edge-connected graph implies existence of immersion of any 3-regular graph on small number of vertices.
|
|
|
Graph labeling
Böhm, Martin ; Mareš, Martin (advisor) ; Balyo, Tomáš (referee)
We introduce the concept of adjacency labeling schemes and recent results in the area. These schemes have practical application in parallel algorithm design and they relate to the theory of universal graphs. We concentrate on the modern technique of "Traversal and Jumping". We present a less technical proof of its correctness as well as correcting some errors in the original proof. We also apply brute-force algorithms to find small induced-universal graphs. 1
|
|
|
Graph theory and its use in school mathematics
Glasová, Ester ; Novotná, Jarmila (advisor) ; Dvořák, Petr (referee)
Graph theory and its use in school mathematics This thesis deals with the inclusion of some problems of graph theory in education at secondary school. It contains the necessary theory for teachers as well as several examples of graph theory in school mathematics in elementary school; moreover it describes several well-known problems, which can be solved using graph theory. The work also includes preparation of two lessons. The theme of the first one is drawing in one stroke and an Eulerian cycle in general. Second topic is dedicated to mazes and labyrinths, their transformation to graph and few algorithms for passing through the maze. In the experimental part, the author examines whether the students are able to understand the selected parts of graph theory, and whether they find this topic more interesting than the usual mathematics they are used to at school. The results of this experiment are then compared for children from two types of lower secondary schools.
|
|
|
Meze pro vzdálenostně podmíněné značkování grafů
Kupec, Martin ; Fiala, Jiří (advisor) ; Dvořák, Zdeněk (referee)
We study the complexity of the λ−L(p, q)-labelling problem for fixed λ, p, and q. The task is to assign vertices of a graph labels from the set {0, . . . , λ} such that labels of adjacent vertices differ by at least p while vertices with a common neighbor have different labels. We use two different reductions, one from the NAE-3SAT and the second one from the edge precoloring extension problem. 1
|
|
|
The architecture of regulatory network of metabolism
Geryk, Jan ; Flegr, Jaroslav (advisor) ; Cvrčková, Fatima (referee) ; Šafránek, David (referee)
The thesis focus on the modularity of metabolic network and foremost on the architecture of regulatory network representing direct regulatory interactions between metabolites and enzymes. I focus on the "modularity measure" in my first work. Modularity measure is quantitative measure of network modularity commonly used for module identification. It was showed that algorithms using this measure can produce modules that are composed of two clearly pronounced sub-modules. Maximum size of module for which there is a risk that is is composed of two sub-modules is called resolution limit of modularity measure. In my first work I generalize resolution limit of modularity measure. The generalized version provide insight to the origin of resolution limit in the null-model used by modularity measure. Moreover it is showed that the risk of omitting of sub-modular structures applies for bigger modules than mentioned in the original publication. The second work is focused on the question how does the modular structure of E. coli metabolic network change if we add regulatory interactions. I find that the modularity of modular core of network slightly increase after regulatory edges addition. The modularity increase is significant with respect to randomized ensemble of regulatory networks. Identified modules...
|
guest ::
