Tato práce se zabývá cyklickými vlastnostmi orientovaných grafů. První kapitola je seznámením s některými problémy v oblasti teorie grafů. Ve druhé kapitole definujeme základní pojmy z teorie grafů - nejprve pro neorientované a dále pro orientované grafy. Ve třetí kapitole jsou uvedeny známé věty a hypotézy o hamiltonovských vlastnostech neorientovaných i orientovaných grafů, které kladou podmínky zejména na stupně vrcholů daných grafů. Ve čtvrté kapitole jsou zmíněny postačující podmínky zaměřené na souvislost a nezávislost opět neorientovaných i orientovaných grafů. Poslední kapitola je věnována lokálním verzím Meynielovy věty a Manoussakisovy hypotézy, které popisují cykly na určitých množinách vrcholů.
Anotace v angličtině
This thesis is focused on Hamilton properties of directed graphs. The first chapter is a familiarization with some of the problems of graph theory. In the second chapter we define fundamental terms of graph theory for both undirected and directed graphs. In the third chapter we mention well-known theorems and conjectures about Hamilton properties of undirected and directed graphs which provide particularly sufficient degree conditions. In the fourth chapter we discuss sufficient conditions based on connectivity and independence of given graphs. The last chapter is dedicated to local versions of Meyniel's theorem and Manoussakis' conjecture which characterize cycles on specific sets of vertices.
Klíčová slova
Orientovaný graf, hamiltonovský cyklus, stupňové podmínky, lokální podmínky, souvislost grafu, nezávislost grafu
Klíčová slova v angličtině
Directed graph, Hamilton cycle, degree conditions, local conditions, connectivity, independence
Rozsah průvodní práce
35 s.
Jazyk
CZ
Anotace
Tato práce se zabývá cyklickými vlastnostmi orientovaných grafů. První kapitola je seznámením s některými problémy v oblasti teorie grafů. Ve druhé kapitole definujeme základní pojmy z teorie grafů - nejprve pro neorientované a dále pro orientované grafy. Ve třetí kapitole jsou uvedeny známé věty a hypotézy o hamiltonovských vlastnostech neorientovaných i orientovaných grafů, které kladou podmínky zejména na stupně vrcholů daných grafů. Ve čtvrté kapitole jsou zmíněny postačující podmínky zaměřené na souvislost a nezávislost opět neorientovaných i orientovaných grafů. Poslední kapitola je věnována lokálním verzím Meynielovy věty a Manoussakisovy hypotézy, které popisují cykly na určitých množinách vrcholů.
Anotace v angličtině
This thesis is focused on Hamilton properties of directed graphs. The first chapter is a familiarization with some of the problems of graph theory. In the second chapter we define fundamental terms of graph theory for both undirected and directed graphs. In the third chapter we mention well-known theorems and conjectures about Hamilton properties of undirected and directed graphs which provide particularly sufficient degree conditions. In the fourth chapter we discuss sufficient conditions based on connectivity and independence of given graphs. The last chapter is dedicated to local versions of Meyniel's theorem and Manoussakis' conjecture which characterize cycles on specific sets of vertices.
Klíčová slova
Orientovaný graf, hamiltonovský cyklus, stupňové podmínky, lokální podmínky, souvislost grafu, nezávislost grafu
Klíčová slova v angličtině
Directed graph, Hamilton cycle, degree conditions, local conditions, connectivity, independence
Zásady pro vypracování
Na rozdíl od neorientovaných grafů jsou vlastnosti a struktura orientovaných grafů prozkoumané daleko méně. Řada relativně základních otázek je stále otevřená. Jedná se například o otázky související s hamiltonovskými vlastnostmi, existencí dlouhých cyklů a otázky pokrývání cykly (např. při stupňových postačujících podmínkách a dostatečně vysoké souvislosti). Cílem bakalářské práce je přehledné zpracování problematiky cyklických vlastností orientovaných grafů a práce na vybraném problému.
Zásady pro vypracování
Na rozdíl od neorientovaných grafů jsou vlastnosti a struktura orientovaných grafů prozkoumané daleko méně. Řada relativně základních otázek je stále otevřená. Jedná se například o otázky související s hamiltonovskými vlastnostmi, existencí dlouhých cyklů a otázky pokrývání cykly (např. při stupňových postačujících podmínkách a dostatečně vysoké souvislosti). Cílem bakalářské práce je přehledné zpracování problematiky cyklických vlastností orientovaných grafů a práce na vybraném problému.
Seznam doporučené literatury
G. Chartrand, L. Lesniak, P. Zhang: Graphs & Digraphs, Chapman and Hall/CRC, 2015
J.L. Gross, J. Yellen, M. Anderson: Graph Theory and Its Applications, Chapman and Hall/CRC, 2018
A. Bondy, U.S.R. Murty: Graph Theory, Springer-Verlag London, 2008
J. Bang-Jensen, G.Z. Gutin: Digraphs: Theory, Algorithms and Applications, Springer-Verlag London,
2009
\par Časopisecká literatura bude upřesňována průběžně.
Seznam doporučené literatury
G. Chartrand, L. Lesniak, P. Zhang: Graphs & Digraphs, Chapman and Hall/CRC, 2015
J.L. Gross, J. Yellen, M. Anderson: Graph Theory and Its Applications, Chapman and Hall/CRC, 2018
A. Bondy, U.S.R. Murty: Graph Theory, Springer-Verlag London, 2008
J. Bang-Jensen, G.Z. Gutin: Digraphs: Theory, Algorithms and Applications, Springer-Verlag London,
2009
\par Časopisecká literatura bude upřesňována průběžně.