|
|
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...
|
|
|
Ecology of pollination networks
Hadrava, Jiří ; Janšta, Petr (advisor) ; Novotný, Vojtěch (referee)
In communities, plants and pollinators are organized into complex network of relations. Description of structure in this network can contribute to understanding of community dynamics and persistence of biodiversity. Better understanding of patterns in assemblages of plants and pollinators may also help in their protection. The aim of this work is to review recent methodological principles in the pollination network analyses and to show potential problems in concept of ecological networks. Graph theory is breefly summarized and applied to the description of pollination networks. As an example, results on comparison of communities from different geographical sites are given.
|
|
|
Statistical evaluation of large-scale data of waste colection problem
Šmídová, Zlata ; Karpíšek, Zdeněk (referee) ; Šomplák, Radovan (advisor)
The bachelor thesis deals with statistical evaluation of large-scale data of waste collection problem and with evaluation these data for the purpose of subsequent traffic optimization. Statistical tests were performed in Microsoft Excel and STATISTICA. After compiling the mathematical model, the processed data were uploaded to the SQLite database and to the General Algebraic Modeling System, which calculated the time spent on each section of the route. The results are important for dealing with traffic and logistics issues that many companies and companies are engaged in. This approach represents a new technique for creating boundary conditions in traffic tasks. The output is high quality input data for optimization in logistics.
|
|
|
Optimization of rail waste transportation
Ambrozková, Anna ; Hrabec, Dušan (referee) ; Pavlas, Martin (advisor)
The bachelor thesis focuses on optimization of rail waste transportation. Theoretical part is about graph theory and optimization, where is introduced for example representation of graphs, network flows or linear programming. Practical part deals with comparison of road and rail networks, motivational example and at least with the application on real data of whole Czech Republic.
|
|
|
Stochastic Optimization of Network Flows
Málek, Martin ; Holešovský, Jan (referee) ; Popela, Pavel (advisor)
Magisterská práce se zabývá stochastickou optimalizací síťových úloh. Teoretická část pokrývá tři témata - teorii grafů, optimalizaci a progressive hedging algoritmus. V rámci optimalizace je hlavní část věnována stochastickému programování a dvoustupňovému programování. Progressing hedging algoritmus zahrnuje také metodu přiřazování scénářů a modifikaci obecného algoritmu na dvou stupňové úlohy. Praktická část je věnována modelům na reálných datech z oblasti svozu odpadu v rámci České republiky. Data poskytl Ústav procesního inženýrství.
|
|
|
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
|
|
|
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.
|
|
|
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
|
|
|
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.
|
|
|
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...
|
guest ::
