Dekompozice orientovaných a neorientovaných grafů
| Thesis title in Czech: | Dekompozice orientovaných a neorientovaných grafů |
|---|---|
| Thesis title in English: | Decompositions of directed and undirected graphs |
| Key words: | graf, dekompozice, cyklus, eulerovská procházka, algoritmus |
| English key words: | graph, decomposition, cycle, closed eulerian walk, algorithm |
| Academic year of topic announcement: | 2018/2019 |
| Thesis type: | diploma thesis |
| Thesis language: | čeština |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. RNDr. Martin Loebl, CSc. |
| Author: | Mgr. Petra Pelikánová - assigned and confirmed by the Study Dept. |
| Date of registration: | 02.11.2018 |
| Date of assignment: | 10.09.2019 |
| Confirmed by Study dept. on: | 16.06.2020 |
| Date and time of defence: | 01.07.2021 13:00 |
| Date of electronic submission: | 16.09.2020 |
| Date of submission of printed version: | 25.05.2021 |
| Date of proceeded defence: | 01.07.2021 |
| Opponents: | Mgr. Tereza Klimošová, Ph.D. |
| Guidelines |
| Cílem práce je prostudování problému dekompozice orientovaných a neorientovaných grafů na cykly či eulerovské podprocházky. Součástí práce je pochopení literatury související s hypotézami, které se týkají dekompozic eulerovských grafů. Dále také zkoumání algoritmů pro rozhodování o existenci dekompozic a jejich hledání. Teoretické poznatky budou uplatněny při zkoumání složitosti a při pokusu o řešení optimalizačního problému zimní údržby silnic. |
| References |
| COOK, William J., et al. Combinatorial Optimization. Wiley-Interscience, 1998.
BOLLOBÁS, Béla. Modern graph theory. Springer Science & Business Media, 2013. HUANG, Hao, et al. Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs. Combinatorics, Probability and Computing, 2013, 22.6: 859-873. CHUDNOVSKY, Maria; SEYMOUR, Paul; SULLIVAN, Blair. Cycles in dense digraphs. Combinatorica, 2008, 28.1: 1-18. FOX, Jacob; KEEVASH, Peter; SUDAKOV, Benny. Directed graphs without short cycles. Combinatorics, Probability and Computing, 2010, 19.2: 285-301. další časopisecká literatura dle doporučení vedoucího |