|
|
Visualization algorithms for graphs
Kuča, Tomáš ; Mareš, Martin (referee) ; Valla, Tomáš (advisor)
In the present work we study the algorithms for graph drawing. We focus mainly on planar graphs, but we also show a few algorithms for non-planar graphs and the methods which convert a non-planar graph into a planar one. We extend the algorithm based on the areas of inner faces by a new force, taking into account the size of angles. We describe how to use the algorithm for nding maximum independent set on circle graphs in planarization. Finally, we present a plugin for editor VRR developed to test these algorithms.
|
|
|
Ramsey theory and combinatorial games
Valla, Tomáš ; Nešetřil, Jaroslav (advisor)
Ramsey theory studies the internal homogenity of mathematical structures (graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called Ramsey number, and on the minimum object size such that the rst player has a winning strategy in the corresponding combinatorial game, called game number. In this thesis, we describe such Ramsey-type theorems where the Ramsey number is substantially greater than the game number. This means, we show the existence of rst player's winning strategies, together with Ramsey and game numbers upper bounds, and we compare both numbers.
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Valtr, Pavel (referee) ; Nešetřil, Jaroslav (advisor)
Ramsey theory studies the internal homogenity of mathematical structures (graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called Ramsey number, and on the minimum object size such that the rst player has a winning strategy in the corresponding combinatorial game, called game number. In this thesis, we describe such Ramsey-type theorems where the Ramsey number is substantially greater than the game number. This means, we show the existence of rst player's winning strategies, zogether with Ramsey and game numbers upper bounds, and we compare both numbers.
|
guest ::
