|
|
Výpočetní složitost v teorii grafů
Ondráčková, Eva ; Kratochvíl, Jan (advisor) ; Sgall, Jiří (referee)
Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this thesis, we study the computational complexity the problem S(P) for a certain graph property P: given a graph G, determine if G is switching-equivalent to a graph having P. First, we give an overview of known results, including both properties P for which S(P) is polynomial, and those for which S(P) is NP-complete. Then we show the NP-completeness of the following problem for each c (0; 1): determine if a graph G can be switched to contain a clique of size at least cn, where n is the number of vertices of G. We also study the problem if, for a xed graph H, a given graph is switching-equivalent to an H-free graph. We show that for H isomorphic to a claw, the problem is polynomial. Further, we give a characterization of graphs witching-equivalent to a K1;2-free graph by ten forbidden induced subgraphs, each having ve vertices.
|
|
|
Restrictions of the land ownership (causes and legal forms)
Kratochvíl, Jan ; Franková, Martina (advisor) ; Žákovská, Karolina (referee)
In the context of efficiency the new legislation particularly of the private law and also within the changes regarding public law this thesis attempts to substantiate and specify various forms of restrictions of land ownership. It also deals with the specification of causes that lead to these restrictions and emphasize the nature of ownership. Emphasis is besides explaining of necessary legal concepts devoted also to the analyse new legal principles, institutes and provisions as well as their impact on the regulatory environment. According to the factual division the thesis analyzes and explains by the existing and new legislation selected restrictions of land ownership within the private and public law. Evidence of these various restrictions and even the potential harm compensations also have their importance, and are therefore also in the thesis included.
|
|
|
Metaphysical essentials of Ladislav Klíma's philosophy
Kratochvíl, Jan ; Hogenová, Anna (referee) ; Rybák, David (referee)
This work focuses on the analysi s of methaphysical philosophy of a Czech writer and philosopher Ladislav Klíma. It studies his discourse with older philosophical tradition and his own sources of inspiration and demonstrates essential contradictions of the resulting philosophy - egosolism. The main focus of this work is in analysis of the transition of a certain methaphysical view on the world to ethical challenge and criticism of Christian faith as Klíma understood it. It is rather emotional than rational as Klíma's literary works show. They are also used to demonstrate his adherence to traditional methaphysical points of view. The final part of this work sums up Klíma's philosophical ideas from which inevitably stem these contradictions. A way of reading Klíma's body of work is offered which is indifferent to incoherences of Klíma's intelectual construct.
|
|
| |
|
|
Chromatic invariants in graph drawing
Štola, Jan ; Kratochvíl, Jan (advisor) ; Valtr, Pavel (referee)
This paper studies the question: What is the maximum integer kb,n such that every kb,n-colorable graph has a b-bend n-din1ensional orthogonal box drawing? We give an exact answer for the orthogonal line drawing in all dimensions and for the 3-dimensional rectangle visibility representation. We present an upper and lower bound for the 3-dimensional orthogonal drawing by rectangles and general boxes. Particularly, we improve the best known upper bound for the 3-dimensional orthogonal box drawing from 183 to 42 and the lower bound from 3 to 22. Powered by TCPDF (www.tcpdf.org)
|
|
|
Marxism, neo-marxism - views of education
Kratochvíl, Jan ; Kopecký, Martin (advisor) ; Mužík, Jaroslav (referee)
The work talks about education in a sociological and philosophical context. It is based on the Marxist, or rather Neomarxist, point of view, introduced in the first part of the work. It mainly focuses on Marx's historical theory and the alienation of man in capitalism. Furthermore, the works of certain authors, who wrote about these topics, as well as criticised some of the features of the late capitalistic society are briefly discussed. The term education is then put in a social context and introduced in different culturally dependent variations. The goal of this section of the work is to show the dependence of the perception of education on the current historical and social context and to elaborate on its perception in the late capitalistic society. Then a certain theoretical definition is formed, which could be essential in solving certain problems based on the current structure of social relationships. The final part investigates school and reveals it as a certain institucional conservant of the current understanding of education. It shows that even school tuition depends on the historically and socially conditioned values and therefore cannot become the primary source for redefining the meaning of education, so that it could aid in solving some of the structural problems of society.
|
|
|
Structural and complexity questions of graph theory
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Hliněný, Petr (referee) ; Fomin, Fedor (referee)
DOCTORAL THESIS ABSTRACT Tomáš Gavenčiak Structural and complexity questions of graph theory The original cops and robber game, proposed in 1983 by Nowakowski and Winkler, and independently by Quilliot, is a two-player combinatorial pursuit game on a graph. Many related games have been introduced and studied since then, both with a purely game theoretic motivation and for their applications in graph theory and connections with graph width parameters. We give an overview of the field and present three particular results: We show bounds on the required number of cops for various connected intersection graph classes, most notably we show that on connected string graphs 15 cops always win. We show the game of cops and fast robber to be polynomially decidable on interval graphs and as a tool we generalise the problem of defensive domination and show a polynomial algorithm for interval graphs. Finally we propose and examine generalisations of tree-depth, marshals and robber games, and minors to hypergraphs and hypergraph pairs.
|
|
|
Hry na grafech ve vztahu k zdvihovým parametrům grafů
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Smrž, Otakar (referee)
We consider a variant of a cop and robber game with an in nitely fast robber and its relations to other similar games. We compare the helicopter game characterizing tree-width, the classical cop and robber game and its versions with various speeds of the robber. We study the complexity of the in nitely fast robber variant and give an explicit characterization of all the graphs where one cop can win. As the main result, we show a polynomial time algorithm deciding the game on interval graphs. This answers a question from the paper Fomin et al.: On tractability of Cops and Robbers game, IFIP TCS 2008, 171-185. To show the polynomiality of the game on interval graphs, we introduce a new auxiliary game on an interval representation of the graph and show the polynomiality of that game. Then we use game strategy reductions to show the equivalence of the two games.
|
|
|
Numerical simulations of flows of visco-elastic fluid-like materials, as asphalt in particular
Kratochvíl, Jan ; Málek, Josef (advisor) ; Rajagopal, K.R. (referee)
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.
|
|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (advisor) ; Telle, Jan Arne (referee) ; Obdržálek, Jan (referee)
Title: Parameterized Complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisor's e-mail address: honza@kam.mff.cuni.cz Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving the best running time. In the questions we study typically the first-choice parameter is unsuccessful, in which case we propose to use less standard ones. The first family of problems investigated provides a common general- ization of many well known and studied domination and independence problems. Here we suggest using the dual parameterization and show that, in contrast to the standard solution-size, it can confine the in- evitable combinatorial explosion. Further studied problems are ana- logues of the Steiner problem in directed graphs. Here the parameter- ization by the number of terminals to be connected seems to be previ- ously unexplored in the directed setting. Unfortunately, the problems are shown to be...
|
guest ::
RSS feed.