|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (advisor) ; Paulusma, Daniel (referee) ; Šámal, Robert (referee)
Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles
|
|
|
KBang
Čevora, Michal ; Lidický, Bernard (advisor) ; Dokulil, Jiří (referee)
The aim of this work is to transform the card game called Bang! into a computer game that will be playable over computer network. In the beginning of the work I present the basic concepts of the game and I deal with solving problems related to implementation of the game. In the subsequent text I outline the architecture of the application with respect to server and client. From general architecture I proceed to the description of concrete implementation. First I acquaint the reader with the Qt, mentioning the reasons for its use, afterwards I describe the implementation of all parts of the project. In the conclusion of the work there is the user manual.
|
|
|
Variants of the coloring problem
Lidický, Bernard
The choice number is a graph parameter that generalizes the chromatic number. In this concept vertices are assigned lists of available colors. A graph is k-choosable if it can be colored whenever the lists are of size at least k. It is known that every planar graph without triangles is 4-choosable and there is an example of a non-3-choosable planar graph without triangles. In this work we study the choice number of planar graph without triangles and other short cycles.
|
|
|
Monkey Bank Robbers
Škoda, Dominik ; Lidický, Bernard (advisor) ; Cibulka, Josef (referee)
The project concerns of creation of computer game inspirated by the game RoboRally. The program is based on Client-Server architecture and allowes players to play together via Internet. The application running on server manages individual games and takes care of synchronization between players. The program allowes to implement artificial inteligence which can join individual game with another players. Each player can create any map and play a game with any map. The project is designed for simple extension in future. The program is developed in JAVA language.
|
|
|
Hledání shluků v grafech
Navrátil, Jan ; Lidický, Bernard (advisor) ; Mareš, Martin (referee)
The goal of this thesis is to create an application which will be able to identify clusters in graphs. The application contains modified algorithms from cluster analysis and graph algorithms used for identifying communities in complex networks. The purpose of this work is not speed optimalisation of implementation but the opportunity to try and compare results of each algorithm and verify whether special graph algorithms are truly better. The core of this task was to modify algorithms from classical cluster analysis (four were chosen, with a set of settings each) to work with graphs and implement and present them within one application along with community detection algorithms (two, in more versions each).
|
|
|
MP3 editor
Löffelmann, Petr ; Mareš, Martin (advisor) ; Lidický, Bernard (referee)
Title: MP3 editor Author: Petr Löffelmann Department: Department of Applied Mathematics Abstract: The thesis focuses on digitized sound in MPEG 1 Layer III (MP3) format and its main goal it to implement an audio library which provides its user with selected editing operations. The text provides an overview of methods used during sound compression, then it describes structure of an MP3 file and finally analyses the decompression process. Further on the library implementation and the steps that need to be taken in order to execute the editing actions while putting the earlier obtained knowledge into practise are explained. In the end the programmer documentation and CD containing working copy of the library is attached. Keywords: MP3, editor, compression
|
|
|
Elevator scheduling algorithms
Hlísta, Peter ; Cibulka, Josef (advisor) ; Lidický, Bernard (referee)
This thesis compares various systems of elevator solutions in high-rise buildings using computer simulation. These systems are compared according to the various criteria. The basic criterion is the average waiting time for the elevator. The other criteria are the costs of the transport and the longest waiting time. The algorithms for the management of the various types of elevators are tested on the larger group of people than in the most of the available literature that examine the improvements mostly on two or three persons. The results show that it is meaningful to consider all algorithms because each of them has its advantages and disadvantages.
|
|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (advisor) ; Paulusma, Daniel (referee) ; Šámal, Robert (referee)
Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles
|
|
|
Solution techniques for the frequency assignment problem
Ježek, Lukáš ; Lidický, Bernard (referee) ; Nejedlý, Pavel (advisor)
Wireless communication is used in a growing number of situations, for example in mobile telephony, wireless networks (WLAN), television and radio broadcasting, satellite communication or in military operations. It is necessary to solve the frequency assignment problem in each of the above situations, so that the communicating sides get connected and their connection is not interfered by other communicating subjects and connections. It is very important to be able to solve the problem well since the number of the participants in the wireless communication is rapidly growing. This work provides introduction to the frequency assignment problem along with the overview of the most frequently used techniques for solving it. Selected methods are described in more details and are also implemented in the enclosed program.
|
|
|
Soccer
Beneš, Jan ; Babilon, Robert (referee) ; Lidický, Bernard (advisor)
The purpose of this thesis was to design and implement an association football (soccer) match simulator and to compare the resulting implementation with other programs of similar function. A model after which both out eld players and goalkeepers play in an association football match was designed. It is possible to run the program in an interactive mode, whereby the players of one of the teams are controlled by the user, or to spectate a match of arti cial intelligencies. Included in the simulation are the physics of the football and deflections off the crossbar and the posts.
|
guest ::
