|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (advisor) ; Sereni, Jean-Sébastien (referee)
In this work we study two random procedures in cubic graphs with large girth. The first procedure finds a probability distribution on edge-cuts such that each edge is in a randomly chosen cut with probability at least 0.88672. As corollaries, we derive lower bounds for the size of maximum cut in cubic graphs with large girth and in random cubic graphs, and also an upper bound for the fractional cut covering number in cubic graphs with large girth. The second procedure finds a probability distribution on independent sets such that each vertex is in an independent set with probability at least 0.4352. This implies lower bounds for the size of maximum independent set in cubic graphs with large girth and in random cubic graphs, as well as an upper bound for the fractional chromatic number in cubic graphs with large girth.
|
|
|
Chessboard problems in combinatorics
Chybová, Lucie ; Slavík, Antonín (advisor) ; Šmíd, Dalibor (referee)
This master thesis discusses various mathematical problems related to the placement of chess pieces. Solutions to the problems are mostly elementary (yet sometimes quite inventive), in some cases rely on basic knowledge of graph theory. We successively focus on different chess pieces and their tours on rectangular boards, and then examine the "independence" and "domination" of chess pieces on square boards. The text is complemented with numerous pictures illustrating particular solutions to given problems.
|
|
|
Approximation of independence number of planar graphs
Berg, Michal ; Dvořák, Zdeněk (advisor) ; Fiala, Jiří (referee)
The independent set problem is a well-known NP-complete problem, which is NP- complete even for planar graphs. But unlike general graphs, there exists an polynomial- time approximation scheme for planar graphs. We are going to describe an exact algorithm for maximum independent set problem in planar graphs based on dynamic programming. This algorithm can be easily modified to an polynomial-time approximation scheme. We implemented both versions of this algorithm and tested them. We used a few random planar graph generators for that. We compared the exact algorithm with another two algorithms. We compared the approximation algorithm with its exact version and measured its real approximation ratio and also its time complexity in comparison with the exact version. We discovered that the exact algorithm usually finishes the computation faster than the other two algorithms. We also discovered that the approximation version has a better approximation ratio compared to the theoretical minimum with good time complexity. 1
|
|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (advisor) ; Sereni, Jean-Sébastien (referee)
In this work we study two random procedures in cubic graphs with large girth. The first procedure finds a probability distribution on edge-cuts such that each edge is in a randomly chosen cut with probability at least 0.88672. As corollaries, we derive lower bounds for the size of maximum cut in cubic graphs with large girth and in random cubic graphs, and also an upper bound for the fractional cut covering number in cubic graphs with large girth. The second procedure finds a probability distribution on independent sets such that each vertex is in an independent set with probability at least 0.4352. This implies lower bounds for the size of maximum independent set in cubic graphs with large girth and in random cubic graphs, as well as an upper bound for the fractional chromatic number in cubic graphs with large girth.
|
guest ::
