OBSAHOVÁ NÁPLŇ PŘEDNÁŠEK A CVIČENÍ:
|
- Grafy a podgrafy. Grafy a jednoduché grafy, izomorfismus grafů. Podgrafy, stupeň vrcholu. Incidenční matice a matice sousednosti. Cesty a cykly.
- Důležité třídy grafů. Souvislé a nesouvislé grafy. Kompletní grafy, bipartitní a multi-partitní grafy. Stromy, kostra grafu.
- Vrcholová a hranová souvislost grafů. Mosty a artikulace, oddělující množiny (řezy). Vrcholová souvislost, hranová souvislost, bloky.
- Párování a pokrytí. Párování, perfektní párování. Pokrytí. Párování a pokrytí v bipartitních grafech.
- Hranové a vrcholové barvení grafu. Hranové barvení, chromatický index grafu, Vizingova věta. Vrcholové barvení, chromatické číslo grafu. Brooksova věta.
- 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.
- Sítě. Toky v sítích. Věta o maximálním toku a minimálním řezu.
|
Literatura: |
- BEHZAD, M. - CHARTRAND, G. - LESNIAK-FOSTER, L. Graphs and Digraphs. Prindle: Weber & Schmidt, 1979.
- Bollobas, B. Modern Graph Theory. New York: Springer, 1998.
- BONDY, J. A. - MURTY, U. S. R. Graph Theory with Applications. The Macmillan Press, 1976.
- DIESTEL, R. Graph Theory. New York: Springer, 1997.
- 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í studium | Kombinované studium |
Výborně | 100 | – | 86 | 60 | - | 50 |
Velmi dobře | 66 | - | 85 | 40 | - | 49 |
Dobře | 50 | - | 65 | 30 | - | 39 |
|