|
Vyučující
|
-
Lhotka Ctirad, doc. RNDr. Ph.D.
|
|
Obsah předmětu
|
1. týden - zopakování základních pojmů teorie grafů, mosty a artikulace 2. týden - k-souvislost grafů (Mengerova věta), cyklické vlastnosti grafů a jejich aplikace, 3.-4. týden - hamiltonovské grafy - nutné a postačující podmínky, 5. týden - hamiltonovské vlastnosti v mocninách grafů, 6. týden - vektorový prostor kružnic a hranových řezů, 7. týden - vlastní čísla a spektrum grafů, 8. týden - vrcholové barvení grafů, Brooksova věta, 9. týden - hranové barvení grafů, Vizingova věta, 10. týden - úvod do Ramseyovy teorie, 11.-12. týden - úvod do teorie toků a lineární optimalizace, jednoduchý simplexový algoritmus
|
|
Studijní aktivity a metody výuky
|
Přednáška s aktivizací, Studium metodou řešení problémů, Samostudium studentů
- Kontaktní výuka
- 52 hodin za semestr
- Příprava na souhrnný test [6-30]
- 26 hodin za semestr
- Příprava na zkoušku [10-60]
- 52 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| znát základní pojmy teorie grafů v rozsahu předmětu KMA/DMA |
| formulovat základní pojmy a poznatky z teorie grafů, především neorientovaných |
| formulovat základní algoritmy z oblasti neohodnocených i ohodnocených grafů |
| Odborné dovednosti |
|---|
| definovat základní pojmy z teorie grafů, především neorientovaných |
| aplikovat základní důkazové techniky v teorii grafů |
| použít základní maticový kalkulus v teorii grafů |
| Obecné způsobilosti |
|---|
| bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
| bc. studium: uplatňuje při řešení problémů vhodné metody a dříve získané vědomosti a dovednosti, kromě analytického a kritického myšlení využívá i myšlení tvořivé s použitím představivosti a intuice, |
| bc. studium: kriticky přistupuje ke zdrojům informací, informace tvořivě zpracovává a využívá při svém studiu a praxi, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| formulovat základní poznatky z hamiltonovských vlastností grafů |
| mít přehled o základních poznatcích z oblasti vrcholového a hranového barvení grafů - Brooksova věta a Heawoodova věta (vrcholové), Konigova věta a Vizingova věta (hranové) |
| formulovat Ramseyův problém a Ramseyovu větu |
| orientovat se ve spektrální teorie grafů - formulace, základní poznatky, spektra základních tříd grafů |
| formulovat úlohu lineární optimalizace a popsat základní varianty simplexového algoritmu |
| Odborné dovednosti |
|---|
| formulovat hamiltonovské vlastnosti grafů |
| formulovat základních poznatky z vrcholového a hranového barvení grafů |
| popsat a vysvětlit základy Ramseyovy teorie a spektrální teorie grafů |
| řešit jednoduché typy úloh pomocí simplexového algoritmu |
| Obecné způsobilosti |
|---|
| bc. studium: samostatně získávají další odborné znalosti, dovednosti a způsobilosti na základě především praktické zkušenosti a jejího vyhodnocení, ale také samostatným studiem teoretických poznatků oboru, |
| bc. studium: samostatně a odpovědně se na základě rámcového zadání rozhodují v souvislostech jen částečně známých, |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednáška s aktivizací studentů, |
| Řešení problémů, |
| Samostudium, |
| Odborné dovednosti |
|---|
| Přednáška s aktivizací studentů, |
| Samostatná práce studentů, |
| Řešení problémů, |
| Obecné způsobilosti |
|---|
| Přednáška s aktivizací studentů, |
| Řešení problémů, |
| Samostudium, |
| Samostatná práce studentů, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Kombinovaná zkouška, |
| Písemná zkouška, |
| Ústní zkouška, |
| definice pojmů v rozsahu předmětu KMA/UTG, konkrétně hamiltonovských vlastností grafů, vrcholového a hranového barvení, Ramseyovy teorie, spektrální teroie grafů a základů lineárního programování |
| Odborné dovednosti |
|---|
| Ústní zkouška, |
| Písemná zkouška, |
| Kombinovaná zkouška, |
| definice pojmů v rozsahu předmětu KMA/UTG schopnost formulovat matematické věty včetně nástinu důkazů schopnost řešit jednoduché typy úloh pomocí simplexového algoritmu |
| Obecné způsobilosti |
|---|
| Ústní zkouška, |
| Písemná zkouška, |
| Kombinovaná zkouška, |
|
Doporučená literatura
|
-
Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
-
Demel, Jiří. Grafy a jejich aplikace. 1. vyd. Praha : Academia, 2002. ISBN 80-200-0990-6.
-
Diestel, Reinhard. Graph theory. 3rd ed. Berlin : Springer, 2006. ISBN 3-540-26183-4.
-
Gross, Jonathan; Yellen, Jay. Graph theory and its applications. Boca Raton : CRC Press, 1999. ISBN 0-8493-3982-0.
|