|
|
The Building on Obilní trh
Čuláková, Michaela ; Ježková, Tereza (referee) ; Kratochvíl, Jan (advisor)
The bachelor thesis focuses on the design of a modern and transparent office building in Brno on the Grain Market. Due to the proximity of the community garden, Špilberk and the incompleteness of the building of the environmental department in Brno, the Institute for the Environment was chosen. The building provides also catering and accommodation for guest collaborators, along with areas for office promotion, which include a lecture hall and a gallery. The shape of the building closes the southern part of the Grain Market and thanks to the vertical garden that forms the facade contributes to improving the microclimate.
|
|
|
Hamiltonian cycles in cubic graphs
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Pergel, Martin (referee)
In this work we study the complextity of Thomasson's algorithm over a special class of cubic graphs. This algorithm nds another hamiltonian circuit, if it starts with a rst one. An open problem is the complexity of this algorithm, but a class of cubic graphs has been found, where for each graph in this class, there exists a hamiltonian circuit and an edge on it, for which Thomasson's algorithm needs exponential number of steps. The goal of this work was to gure out, if Thomasson's algorithm needs exponential number of steps for any hamiltonian circuit and any edge on graphs from this class. We succeeded in proving, that indeed is so.
|
|
|
Graph Drawing: Visualisation and Geometric Representations of Graphs and Networks
Vyskočil, Tomáš ; Kratochvíl, Jan (advisor) ; Felsner, Stefan (referee) ; Kaiser, Tomáš (referee)
Title: Graph Drawing: Visualization and Geometric Representations of Graphs and Networks Author: Tomáš Vyskočil Department: Department of applied mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., KAM Abstract: This thesis is devoted to studying of representations of graphs. In Chapters 2-4 we study intersection graphs in the plane. In Chapter 5 we consider problems of modifications of graphs. Regarding intersection graphs, we prove that all complements of partial 2- trees are intersection graphs of segments. We show complexity of recognition of intersection graphs of path in the grid with bounded number of bends and intersection graphs of connected regions (we call them islands) in the extended grids. In the part devoted to modification problems we present a fixed-parameter tractable (FPT) algorithm which answers the question whether a given graph can be made planar with at most k contractions and we also provide gener- alization of this problem. Keywords: graph theory, graph representations, combinatorics
|
|
| |
|
|
Extending Partial Representations of Graphs
Klavík, Pavel ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In this thesis, we study geometric intersection representations of graphs. For a fixed class, the well-known recognition problem asks whether a given graph belongs to this class. We study a generalization of this problem called partial representation extension. Its input consists of a graph with a partial representation, so a part of the graph is pre-drawn. The problems asks whether this partial representation can be extended to a representation of the entire graph. We study this problem for classes of interval graphs, proper interval graphs, unit interval graphs and chordal graphs (in the setting of subtrees-in-tree representations). We give linear-time algorithms for the first two classes and an almost quadratic-time algorithm for unit interval graphs. For chordal graphs, we consider different versions of the problem and show that almost all cases are NP-complete. Even though the classes of proper and unit interval graphs are known to be equal, the partial representation extension problem distinguishes them. For unit interval graphs, it poses additional restrictions concerning precise positions of intervals, and we describe a new structure of unit interval representations to deal with this. 1
|
|
|
Representations and Visualization of Graphs
Štola, Jan ; Kratochvíl, Jan (advisor) ; Valtr, Pavel (referee) ; Wood, David (referee)
The 3D visibility (graph) drawing is a graph drawing in IR3 where vertices are represented by 2D sets placed into planes parallel to xy-plane and the edges correspond to z-parallel visibility among these sets. We continue the study of 3D visibility drawing of complete graphs by rectangles and regular polygons. We show that the maximum size of a complete graph with a 3D visibility drawing by regular n-gons is O(n4). This polynomial bound improves signifficantly the previous best known (exponential) bound 6n3 3n1 3 26n.We also provide several lower bounds. We show that the complete graph K2k+3 (resp. K4k+6) has a 3D visibility drawing by regular 2k-gons (resp.(2k + 1)-gons). We improve the best known upper bound on the size of a complete graph with a 3D visibility drawing by rectangles from 55 to 50. This result is based on the exploration of unimodal sequences of k-tuples of numbers. A sequence of numbers is unimodal if it rst increases and then decreases. A sequence of k-tuples of numbers is unimodal if it is unimodal in each component. We derive tight bounds on the maximum length of a sequence of k-tuples without a unimodal subsequence of length n. We show a connection between these results and Dedekind numbers, i.e., the numbers of antichains of a power set P(1; : : : ; k) ordered by inclusion.
|
|
|
Computational complexity in graph theory
Doucha, Martin ; Kratochvíl, Jan (advisor) ; Dvořák, Zdeněk (referee)
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
|
|
|
Computational complexity in graph theory
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results
|
|
|
Transmitted means of communication in history
Kratochvíl, Jan ; Smetáček, Vladimír (advisor) ; Machytka, Jan (referee)
Cílem této bakalářské práce je popsat vývoj vybraných přenosových prostředků komunikace v historii. Práci lze rozdělit na dvě části, ve kterých se postupně setkáváme s různými přenosovými prostředky. První se věnuje optickým telegrafním systémům od antiky přes pochodňové telegrafy do poloviny 17. stol. Druhá část je zaměřena na vyspělé telegrafy R. Hooka (1635-1703), C. Chappeho (1763-1805), A. N. Edelcrantze (1754-1821), G. Murraye (1761-1803). U přenosových prostředků je hlavně zkoumáno: dosah komunikace, její důvod, rychlost a utváření komunikačních sítí.
|
|
|
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...
|
guest ::
RSS feed.