Detail předmětu

Teorie grafů

FSI-VTGAk. rok: 1999/2000

Základní pojmy teorie grafů. Aplikace úloh o cestách. Síťové grafy. Prohledávání grafů, backtracking., metoda větví a mezí. Souvislost a dosažitelnost. Nejkratší cesty. Stromy a kostry. Toky v sítích. Párování. Barevnost grafů. Fuzzy grafy.

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

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

Zajišťuje ústav

Ústav automatizace a informatiky (ÚAI)

Výsledky učení předmětu

Viz cíle a úkoly kursu

Způsob a kritéria hodnocení

Implementace netriviálního grafového algoritmu na počítači
s odpovídající úrovní prezentace (např. Borland Delphi, C++).
Studium zahraniční literatury z teorie grafů (Internet, knihy,
časopisy).

Učební cíle

Seznámení s algoritmy, které rozšířují znalosti získané v předmětech
se zaměřením na umělou inteligenci, operační výzkum, projektové řízení
a počítačové sítě.
Osvojení specifických oblastí teorie grafů s důrazem na praktické
aplikace.

Základní literatura

Chartrand, G. and Oellermann, O.R. : Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp.
Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991.

Doporučená literatura

Demel, J.: Grafy a jejich aplikace. ACADEMIA, Praha, 2002.
Kolář, J.: Theoretical Computer Science. ČVUT FEL, Praha, 1998.

Zařazení předmětu ve studijních plánech

  • Program M2301-5 magisterský

    obor , 2. ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

22 hod., nepovinná

Vyučující / Lektor

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

Osnova

1. Definice grafu a základní pojmy.
2. Prohledávání grafů
3. Backtracking, metoda větví a mezí
4. Aplikace úloh o cestách, nejkratší cesty
5. Síťové grafy
6. Eulerovské tahy.
7. Hamiltonovské cesty a kružnice.
8. Komponenty souvislosti, stromy a kostry.
9. Steinerovy stromy.
10. Reprezentace grafu v počítači.
11. Barvení grafů, nezávislost, kliky.
12. Toky v sítích.
13. Párování.
14. Fuzzy grafy

Cvičení na počítači

22 hod., povinná

Vyučující / Lektor

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

Osnova

Implementace algoritmů na počítači.
Vyhledávání a testování softwaru ze studované oblasti na Internetu.