Dekompozice orientovaných a neorientovaných grafů
| Název práce v češtině: | Dekompozice orientovaných a neorientovaných grafů |
|---|---|
| Název v anglickém jazyce: | Decompositions of directed and undirected graphs |
| Klíčová slova: | graf, dekompozice, cyklus, eulerovská procházka, algoritmus |
| Klíčová slova anglicky: | graph, decomposition, cycle, closed eulerian walk, algorithm |
| Akademický rok vypsání: | 2018/2019 |
| Typ práce: | diplomová práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | prof. RNDr. Martin Loebl, CSc. |
| Řešitel: | Mgr. Petra Pelikánová - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 02.11.2018 |
| Datum zadání: | 10.09.2019 |
| Datum potvrzení stud. oddělením: | 16.06.2020 |
| Datum a čas obhajoby: | 01.07.2021 13:00 |
| Datum odevzdání elektronické podoby: | 16.09.2020 |
| Datum odevzdání tištěné podoby: | 25.05.2021 |
| Datum proběhlé obhajoby: | 01.07.2021 |
| Oponenti: | Mgr. Tereza Klimošová, Ph.D. |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| 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 |