Detail předmětu

Teorie grafů

FAST-HA53Ak. rok: 2024/2025

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)

Vstupní znalosti

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

Pravidla hodnocení a ukončení předmětu

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

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.
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.

Základní literatura

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

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.