English

9GRA Grafové algoritmy

předmět stupeň ročník semestr obor

Garant

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

Anotace

Předmět se zaměřuje na teorii grafů a seznamuje studenty s jejími základními pojmy a algoritmy. 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 - grafy viditelnosti, Voroného diagramy a Delaunayho triangulace. Toky v sítích. Barvení grafů. Párování v grafech.

Další informace: 9GRA