Grafové algoritmy a jejich praktická implementace (Bc)
Cílem této práce je nastudovat některou z klasických algorimticky (efektivně) řešitelných úloh teorie grafů, a implementovat některé z algoritmů pro jejich řešení. Důraz bude kladen z jedné strany na teoretický rozbor časové a paměťové složitosti vybraných algoritmů, a z druhé strany též na praktickou implementaci a použití vhodných datových struktur.
Několik konkrétních úloh k výběru:
- Určení vrcholové resp. hranové souvislosti grafu,
- Nalezení délky nejkratších cest s použitím vhodných datových struktur haldového typu,
- Nalezení největšího toku v sítích,
- Nalezení nejtěžšího perfektního párování v grafu s vahami hran.
Literatura:
- M. Mareš, T. Valla: Průvodce labyrintem algoritmů, 2022.
- A. Schrijver: Combinatorial optimization – Polyhedra and Efficiency, 2004.
Důkazy barevnostních vět v teorii grafů s pomocí počítače (např. Goldberg-Seymourovy domněnky) (Mgr)
Tématem této práce je jeden z nejznámějších problémů z oblasti hránové barevnosti grafů, kde je cílem pokrýt množinu hran grafu co nejmenším počtem párování. Jinými slovy, chceme všem hranám přiřadit barvy tak, aby každé dvě sousední hrany dostaly různou barvu.
Goldberg-Seymourova domněnka o hranové barevnosti multigrafů říká, že libovolný multigraf jehož každý vrchol má stupeň nejvýše D lze hranově obarvit pomocí max(D+1, w) barev, kde w značí nejmenší přirozené číslo takové, že pro všechny H podgrafy G s lichým počtem vrcholů číslo w shora odhaduje zlomek 2|E(H)|/(|V(H)|-1). Číslo w je zajisté dolním odhadem, a stejně tak je dolním odhadem i číslo D. Přestože Petersenův graf má D=3 i w=3, je známo, že není hranově-3-obarvitelný, a proto je max(D+1,w) nejlepší horní odhad, v jaký lze doufat.
Cílem této práce je nastudovat nedávný důkaz Goldberg-Seymourovy domněnky a případně též navrhnout verifikaci pomocných tvrzení v tomto důkazu pomocí počítače.
Literatura:
- G. Chen, G. Jing, W. Zhang: Proof of the Goldberg-Seymour Conjecture on Edge-Colorings of Multigraphs (preprint)
- A. Bondy, U.S.R. Murty: Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008
- Goldberg-Seymour Conjecture @Wikipedia