Detail předmětu

Teorie grafů

FAST-HA53Ak. rok: 2020/2021

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

Studenti budou seznámeni se základními pojmy teorie obyčejných grafů a orientovaných grafů a multigrafů. Porozumí souvislosti mezi planárností a barevností grafu. Budou znát základní metody řešení kombinatorických problémů na grafech zvládnutelných v polynomiálním čase i úlohy obchodního cestujícího jako zástupce NP úplných úloh.

Prerekvizity

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

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.

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.