Detail předmětu

Teorie grafů

FAST-HA53Ak. rok: 2014/2015

Definice a aplikace různých typů grafů. Základní struktury definované nad grafy používané k jejich klasifikaci. Snadno a nesnadno řešitelné kombinatorické úlohy modelované pomocí grafů. Základní algoritmy používané pro řešení grafových úloh. Teorie NP-úplnosti.

Jazyk výuky

čeština

Počet kreditů

2

Garant předmětu

RNDr. Karel Mikulášek, Ph.D.

Zajišťuje ústav

Ústav matematiky a deskriptivní geometrie (MAT)

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

Po absolvování kurzu budou studenti znát základy teorie grafů. Budou je umět aplikovat na řešení kombinatorických úloh, s nimiž se budou setkávat v technické a ekonomické praxi.

Prerekvizity

Základní kombinatorické pojmy vyučované na středních školách. Manipulace se symboly.

Plánované vzdělávací činnosti a výukové metody

Výuka probíhá formou praktických cvičení a samostudia. Účast na cvičeních je povinná.

Způsob a kritéria hodnocení

Studenti odevzdají během kurzu řešení tří zadaných úloh z teorie grafů. Pokud dosáhnou z maxima 100 bodů aspoň 50 bodů a nebudou mít neomluvené absence, obdrží zápočet.

Učební cíle

Po absolvovní kurzu budou studenti znát základy teorie grafů. Budou je umět aplikovat na řešení kombinatorických úloh, s nimiž se budou setkávat v technické a ekonomické praxi.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Vymezení kontrolované výuky a způsob jejího provádění stanoví každoročně aktualizovaná vyhláška garanta předmětu.

Základní literatura

Gross, Y; Yellen, J: Graph Theory. CRC Press, 1999.
Nešetřil, J.: Teorie grafů. SNTL, 1978.

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

  • Program N-P-C-GK magisterský navazující

    obor G , 1 ročník, letní semestr, volitelný

Typ (způsob) výuky

 

Cvičení

26 hod., povinná

Vyučující / Lektor

RNDr. Karel Mikulášek, Ph.D.

Osnova

1. Definice neorientovaného a orientovaného grafu.
2. Speciální neorientované grafy, podgraf, souvislost grafu.
3. Stromy.
4. Homomorfismus a isomorfismus grafů.
5. Orientované grafy, turnaje.
6. Eulerovské grafy, hamiltonovské grafy.
7. Barevnost grafů, planární grafy, rovinné grafy.
8. Kostry grafu, úloha o minimální kostře, Kruskalův algoritmus.
9. Dijkstrův a Warshall-Floydův algoritmus pro nalezení nejkratších cest v grafu.
10. Tok v síti. Ford Fulkersonův algoritmus pro nalezení maximálního toku.
11. Úlohy řešitelné v polynomiálním čase a NP úplné úlohy.
12. Heuristické algoritmy, úloha obchodního cestujícího.
13. Opakování, rezerva.