Fakulta informačních technologií VUT v Brně

Detail předmětu

Grafové algoritmy

GAL Ak. rok 2009/2010 zimní semestr 5 kreditů

Předmět diskutuje různé reprezentace grafů v počítači a grafové algoritmy pro problémy typu prohledávání grafů (do hloubky, do šířky), topologické uspořádání grafů, komponenty grafů a silně souvislé komponenty, stromy a minimální kostry, nejkratší cesty z jednoho vrcholu do všech ostatních či ze všech vrcholů do všech ostatních, maximální tok a minimální řez, maximální párování v bipartitních grafech, Eulerovské grafy a barvení grafů. U všech algoritmů je kladen důraz na pochopení základních principů a na studium složitosti navržených algoritmů.

Garant předmětu

Jazyk výuky

česky

Zakončení

zkouška (kombinovaná)

Rozsah

39 hod. přednášky, 13 hod. projekty

Bodové hodnocení

60 zkouška, 40 projekty

Zajišťuje ústav

Přednášející

Cvičící

Stránky předmětu

Získané dovednosti, znalosti a kompetence z předmětu

Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.

Cíle předmětu

Seznámit se s grafy a grafovými algoritmy včetně jejich složitostí.

Požadované prerekvizitní znalosti a dovednosti

Algoritmické myšlení.

Literatura studijní

  • Text přednášek.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.

Literatura referenční

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.
  • J. Demel, Grafy, SNTL Praha, 1988.
  • J. Demel, Grafy a jejich aplikace, Academia, 2002. (More about the book.)
  • R. Diestel, Graph Theory, Third Edition, Springer-Verlag, Heidelberg, 2000.
  • J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
  • J.A. Bondy, U.S.R. Murty: Graph Theory, Graduate text in mathematics, Springer, 2008.
  • J.L. Gross, J. Yellen: Graph Theory and Its Applications, Second Edition, Chapman & Hall/CRC, 2005.
  • J.L. Gross, J. Yellen: Handbook of Graph Theory (Discrete Mathematics and Its Applications), CRC Press, 2003.

Osnova přednášek

  1. Úvod do problematiky, složitost algoritmu, pojem a reprezentace grafu.
  2. Prohledávání grafu do šírky a do hloubky, dostupnost vrcholů.
  3. Topologické uspořádání vrcholů a hran, test acykličnosti grafu.
  4. Komponenty grafu, silně souvislé komponenty, příklady.
  5. Stromy, minimální kostry, Jarníkův a Borůvkův algoritmus.
  6. Růst minimální kostry, algoritmy Kruskala a Prima.
  7. Nejkratší cesty z jednoho vrcholu, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech.
  8. Dijkstrův algoritmus. Nejkratší cesty ze všech vrcholů.
  9. Nejkratší cesty a násobení matic, Floyd-Warshallův algorithmus.
  10. Toky a řezy v sítích, maximální tok, minimální řez, Ford-Fulkersonův algoritmus.
  11. Párování v bipartitních grafech, maximální párování.
  12. Eulerovské grafy a tahy, Hamiltonovské kružnice a cykly.
  13. Barvení grafů.

Osnova ostatní - projekty, práce

  1. Prezentace řešení přidělených úkolů.

Průběžná kontrola studia

  • Prezentace řešení zadaných úkolů (bodově ohodnoceno, max. 40 bodů, tvoří část zkoušky).
  • Závěrečná písemka (max. 60 bodů).

Kontrolovaná výuka

  • Písemná zkouška na konci semestru. Pro získání bodů ze zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 25 body. V opačném případě bude zkouška hodnocena 0 body.

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

Nahoru