Toky v sítích a jejich aplikace

Abstract

Bakalářská práce se zabývá problematikou toků v sítích a jejich aplikacemi. Teoretická část zavádí základní pojmy teorie grafů a formálně definuje klíčové koncepty - síť, tok, reziduální graf a řez. Podrobně jsou popsány tři algoritmy pro nalezení maximálního toku: Ford-Fulkersonův algoritmus, Edmonds-Karpův algoritmus a Dinicův algoritmus, včetně jejich časové složitosti a vzájemného srovnání. Součástí teoretické části je také přehled praktických aplikací maximálního toku, zahrnující bipartitní párování, přiřazovací problém a modelování dopravních sítí. Praktická část popisuje návrh a implementaci konzolové aplikace v jazyce C# na platformě .NET 8, která implementuje všechny tři algoritmy a umožňuje jejich výkonnostní srovnání na uživatelem definovaných vstupech. Správnost implementace byla ověřena testováním na vzorových sítích s předem známými výsledky. Praktická použitelnost aplikace je demonstrována na modelové logistické úloze zásobování nemocnic.