Algoritmy teorie grafů 11Y1TG je povinně volitelný předmět, zakončený klasifikovaným zápočtem.

Anotace

Základní teoretické poznatky o možnosti použití teorie grafů při řešení konkrétních úloh z oblasti dopravních a logistických problémů. Klasické úlohy, zaměření na dopravní sítě. Seznámení s problematikou algoritmizace.

Obsah předmětu

Obsah předmětu:
Orientované a neorientované grafy, ohodnocený graf, matice popisující graf, minimální kostra
grafu, nejkratší cesta, Eulerovské tahy, prohledávání grafu, párování v bipartitních grafech, toky
v sítích.
Algoritmy řešení existenčních a optimalizačních úloh. Přístup k řešení NP-těžkých úloh,
heuristické postupy.