čeština

2

Ústav matematiky a deskriptivní geometrie (MAT)

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í kombinatorické pojmy vyučované na středních školách. Manipulace se symboly.

Podmínky pro úspěšné ukončení předmětu stanoví každoročně aktualizovaná vyhláška garanta předmětu.

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

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í stanoví každoročně aktualizovaná vyhláška garanta předmětu.

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

26 hod., povinná