|
|
Combinatorial applications of linear algebra
Tesař, Marek ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
A covering projection from graph G onto graph H is "local isomorphism": a mapping from the vertex set of G onto the vertex set of H such that, for every v V (G), the neighborhood of v is mapped bijectively onto the neighborhood (in H) of the image of v. We study the computational complexity of the H-cover (deciding if a given graph G covers H), where G is a regular graph with 8 vertices and edges of two colors, where edges of one color create two disjoint 4-cycles. We present full characterization of H-cover problem for such 3-regular graphs. We solve polynomial cases by reduction to system of linear equations and we show some graphs for which this method doesn't work (even though H-cover is polynomial).
|
|
|
Geometrické reprezentace grafů
Klavík, Pavel ; Kratochvíl, Jan (advisor) ; Pergel, Martin (referee)
Intersection graphs are a well studied field of graph theory. Complexity questions of recognition have been studied for several years. Given a graph, we ask whether the graph belongs to a fixed class. In this thesis, we introduce a new problem of partial representation extension. In this problem, aside from a graph, a part of a representation is also fixed. We ask whether it is possible to extend this partial representation to the whole graph. This problem is at least as hard as recognition. We study the partial representation extension problem for several intersection defined classes. We solve extending of interval graphs in time O(n2) and proper interval graphs in time O(mn). Using an approach described by Golumbic, we further show that comparability and permutation graphs are extendable in time O( · m). There are some classes that are known to be equal, for example unit interval graphs and proper interval graphs. Surprisingly, in the case of extending, we need to distinguish them. Similarly, we show that extending of function graphs and extending of co-comparability graphs are completely different problems.
|
|
| |
|
|
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.
|
guest ::
