|
|
Hamiltonian cycles in cubic graphs
Melka, Jakub ; Pergel, Martin (referee) ; Kratochvíl, Jan (advisor)
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.
|
|
| |
|
|
Numerical simulations of flows of visco-elastic fluid-like materials, as asphalt in particular
Kratochvíl, Jan ; Rajagopal, K.R. (referee) ; Málek, Josef (advisor)
In this thesis we deal with numerical simulations for flows of viscoelastic fluids. First, we introduce two models for viscoelastic fluids: (i) the Oldroyd-B, which is a classical model for viscoelastic fluids and (ii) a new nonlinear model which might be thought of as a generalization of Oldroyd-B to the case of large elastic deformations. Then, the flow at three different situations is discussed. The first of them is stress relaxation in parallel plate flow, which is an example of a 1D problem. The second one is a 4:1 planar contraction flow, which is a standard benchmark for viscoelastic flows. The third problem is stress relaxation in axially symmetric cylinder flow, which is solved as a 1D as well as a 2D problem. If it is possible, the problems are solved analytically, otherwise they are solved numerically with the aid of the finite element method using the software Comsol Multiphysics 3.3. Experimental data that document the stress relaxation of asphalt are available in the cylindrical geometry. Thus, finally, these data are fitted using both considered models.
|
|
|
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
Herman, Jan ; Flusser, Jan (referee) ; Kratochvíl, Jan (advisor)
Seidel's switching is a graph operation , which for a given graph G and one of its vertices v gives the graph derived from G by replacing edges adjacent to v by non-edges and vice-versa. A graph H is called a switch of G, if H can be obtained from G by a sequence of switches of its vertices. In the thesis we introduce known results ab out computational complexity of problems if for a given graph G t here exists its switching lying in a given graph class (}. For different graph classes g, we later study a characterization of the class of all graphs, which can be switched into g, in terms of minimal forbidden induced subgraphs. We introduce a full characterization of a class of graphs switchable to a disjoint union af cutworms, respectively partial pairings by forbidden subgraphs. We also prove that a class of graphs switchable to chordal has infinit ely many non-isomorphic forbidden subgraphs. At the end we deal with the relationship between swit ching and other graph operations and graph classes operations.
|
|
| |
|
|
Ramsey-type theorems in geometry
Stolař, Rudolf ; Kratochvíl, Jan (referee) ; Valtr, Pavel (advisor)
Euclidean Ramsey theory is examining konfigurations of points, for which there exists n such that for every coloring of n-dimensional Euclidean space with r colors we can find translated and/or rotaded copy of our configuration in a single color. Asymetric branch deals with situations when we look for different configurations in every color. In this work we concern about asymetrical ramsey-type theorems and properties of n-cubes, for which we show several new bounds. Major part is dedicated to colorings with more colors and obtained results are closely related to the famous problem of chromatic number of Euclidean space. We will mention possible generalization of the chromatic number and some aspects of such generalization. We also consider problems connected to multi-color configurations and we will introduce upper bound for special case of two-color square.
|
guest ::
RSS feed.