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:

1. Určení vrcholové resp. hranové souvislosti grafu,
2. Nalezení délky nejkratších cest s použitím vhodných datových struktur haldového typu,
3. Nalezení největšího toku v sítích,
4. 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.