|
|
|
||
Poslední úprava: MAXOVAJ (08.06.2018)
|
|
||
Poslední úprava: MAXOVAJ (08.06.2018)
Studenti si osvojí základní pojmy teorie grafů. Naučí se analyzovat rozličné inženýrské úlohy a řešit je pomocí známých grafových algoritmů. Dále se naučí rozpoznávat výpočetně náročné úlohy a získají přehled o mnoha problémech řešitelných pomocí teorie grafů.
|
|
||
Poslední úprava: MAXOVAJ (08.06.2018)
Z: Turzík, Pavlíková: Diskrétní matematika, skripta, VŠCHT Praha, 2007, ISBN:978-80-7080-667-8
Z: Demel J.: Grafy a jejich aplikace. Academia, Praha, 2002. ISBN 80-200-0990-6.
Z: Matoušek J., Nešetřil J.: Kapitoly z Diskrétní matematiky. Matfyzpress, Praha, 1996. ISBN 80-85863-17-0.
D: Diestel R.: Graph Theory (Graduate Texts in Mathematics). Springer, 2010. ISBN 978-3642142789. (anglicky)
|
|
||
Poslední úprava: MAXOVAJ (07.06.2018)
www.vscht.cz/mat/ |
|
||
Poslední úprava: MAXOVAJ (24.09.2018)
přednášky, konzultace, samostatná práce na projektu |
|
||
Poslední úprava: MAXOVAJ (08.06.2018)
1. Základní pojmy teorie grafů. Reprezentace grafů.
2. Cesty v grafech. Úloha nejkratší cesty.
3. Souvislost grafu, komponenty souvislosti, 2-souvislé grafy.
4. Stromy. Rychlé třídění.
5. Kostra grafu. Hladový algoritmus pro hledání minimální kostry.
6. Systém různých reprezentantů. Párování v bipartitních grafech.
7. Párování v obecných grafech.
8. Eulerovské grafy. Problém čínského pošťáka.
9. Hamiltonovské grafy. Problém obchodního cestujícího.
10. Rovinné grafy a jejich charakteristika.
11. Barevnost. Barevnost rovinných grafů.
12. Toky v sítích.
13. Teorie složitosti. Problémy třídy P a NP. Dobrá charakteristika.
14. Příklady aplikací teorie grafů. |
|
||
Poslední úprava: Mareš Jan doc. Ing. Ph.D. (03.10.2018)
nejsou |
|
||
Poslední úprava: MAXOVAJ (07.06.2018)
Předmět je zakončen ústní zkouškou, před jejím absolvováním je třeba úspěšně vyřešit 3 z úloh zadaných v průběhu semestru. |