Detail předmětu

Teorie grafů

FAST-HA53Ak. rok: 2016/2017

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

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

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.