English

VTG Teorie grafů

předmět stupeň ročník semestr obor
VTG 2 2 zimní Aplikovaná informatika a řízení
VTG 2 2 zimní Aplikovaná informatika a řízení (P)
VTG-A 2 1 zimní Strojní inženýrství
VTG-K 2 2 zimní Aplikovaná informatika a řízení
VTG-K 2 2 zimní Aplikovaná informatika a řízení (P)

Garant

prof. RNDr. Ing. Miloš Šeda, Ph.D.

Anotace

Předmět je úvodem do teorie grafů a seznamuje studenty s jeho základními pojmy. Zabývá se následujícími tématy: Reprezentace grafu v počítači. Časová složitost algoritmů. Datové struktury pro grafové algoritmy binární halda, disjunktní množiny, ...). Eulerovské tahy, hamiltonovské cesty. Prohledávání grafů (do šířky, do hloubky), backtracking, metoda větví a mezí. Souvislost a dosažitelnost. Nejkratší cesty. Síťové grafy. Stromy a kostry. Steinerovy stromy. Základy počítačové geometrie, Voronoiovy diagramy a Delaunayho triangulace. Toky v sítích. Barvení grafů. Párování v grafech.

Další informace: VTG, VTG-K, VTG-A