Ludek Cienciala
Ludek Cienciala
Identifikační číslo: Heslo: Registruj
19.03.2024
OBSAHOVÁ NÁPLŇ PŘEDNÁŠEK A CVIČENÍ:
  1. Grafy a podgrafy. Grafy a jednoduché grafy, izomorfismus grafů. Podgrafy, stupeň vrcholu. Incidenční matice a matice sousednosti. Cesty a cykly.
  2. Důležité třídy grafů. Souvislé a nesouvislé grafy. Kompletní grafy, bipartitní a multi-partitní grafy. Stromy, kostra grafu.
  3. Vrcholová a hranová souvislost grafů. Mosty a artikulace, oddělující množiny (řezy). Vrcholová souvislost, hranová souvislost, bloky.
  4. Párování a pokrytí. Párování, perfektní párování. Pokrytí. Párování a pokrytí v bipartitních grafech.
  5. Hranové a vrcholové barvení grafu. Hranové barvení, chromatický index grafu, Vizingova věta. Vrcholové barvení, chromatické číslo grafu. Brooksova věta.
  6. Rovinné a planární grafy. Rovinné grafy, Eulerův vzorec. Kuratowského věta, duální graf, věta o čtyřech barvách. Míra neplanarity grafů. Eulerovské a hamiltonovské grafy, Eulerovské grafy, nutná a postačující podmínka. Hamiltonovské grafy, postačující podmínky. Orientované grafy. Orientované grafy, orientované cesty a cykly. Silně souvislé grafy. Turnaje.
  7. Sítě. Toky v sítích. Věta o maximálním toku a minimálním řezu.

Literatura:
  1. BEHZAD, M. - CHARTRAND, G. - LESNIAK-FOSTER, L. Graphs and Digraphs. Prindle: Weber & Schmidt, 1979.
  2. Bollobas, B. Modern Graph Theory. New York: Springer, 1998.
  3. BONDY, J. A. - MURTY, U. S. R. Graph Theory with Applications. The Macmillan Press, 1976.
  4. DIESTEL, R. Graph Theory. New York: Springer, 1997.
  5. FRONČEK, D. Úvod do teorie grafů. Opava: FPF SU, 2000.
...
Student prezenčního studia píše v rámci cvičení dva zápočtové testy bodované maximálně 20 body za každý. K získání zápočtu je zapotřebí 20 bodů. V rámci semestru mohou studenti získat prémiové body.
Zkouška se skládá ze dvou částí. První část: jednoduchý test obsahující 10 otázek. K úspěšnému zvládnutí testu je potřeba alespoň 7-krát zodpovědět správně. Pouze studeni úspěšní v tomto testu mohou obdržet zadání druhé části. Druhá část se skládá z pěti otázek, každá je bodována maximálně 10 body. K počtu bodů získaných ve druhé části se studentovi připočítává 10 bodů z části první. Celkem je tedy ze zkouškové písemky možno získat 60 bodů. Pro úspěšné vykonání je potřeba získat 30 bodů. Známka je stanovena součtem bodů za zkoušku a bodů, které student získal v rámci semestru.
Hodnocení
Prezenční studiumKombinované studium
Výborně1008660 - 50
Velmi dobře66-8540 - 49
Dobře50-6530 - 39