Detail předmětu

Teorie grafů

FAST-HA53Ak. rok: 2013/2014

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.

Osnovy výuky

1. Pojem grafu, definice grafu orientovaného, neorientovaného, prostého. Příklady.
2. Cesta v grafu, souvislost grafu, komponenta grafu. Stromy.
3. Homomorfismus a isomorfismus grafů. Eulerovské grafy a Hamiltonovské grafy, aplikace.
4. Barevnost grafů nezávislost grafů. Planarita grafů, Kuratowského věta. Problém čtyř barev.
5. Základní kombinatorické úlohy. Pojem dobré charakteristiky úlohy.
6. Úlohy na grafech řešitelné v polynomiální čase I.
7. Úlohy na grafech řešitelné v polynomiální čase II.
8. Úloha obchodního cestujícího, metoda větví a mezí, heuristické metody.
9. NP úplné úlohy.
10. Opakování.

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.