PředmětyPředměty(verze: 853)
Předmět, akademický rok 2019/2020
  
Teorie grafů a její aplikace - P413001
Anglický název: Graph Theory and Applications
Zajišťuje: Ústav matematiky (413)
Platnost: od 2019
Semestr: oba
Body: 0
E-Kredity: 0
Způsob provedení zkoušky:
Rozsah, examinace: 3/0 Jiné [hodiny/týden]
Počet míst: zimní:neurčen / neurčen (neurčen)
letní:neurčen / neurčen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Úroveň:  
Pro druh: doktorské
Poznámka: předmět je určen pouze pro doktorandy
student může plnit i v dalších letech
předmět lze zapsat v ZS i LS
Garant: Turzík Daniel doc. RNDr. CSc.
Maxová Jana RNDr. Ph.D.
Záměnnost : D413012
Je záměnnost pro: AP413001
Anotace -
Poslední úprava: Maxová Jana RNDr. Ph.D. (08.06.2018)
Probírají se základní pojmy teorie grafů s důrazem na algoritmické řešení úloh a jejich aplikace pro řešení inženýrských problémů.
Výstupy studia předmětu -
Poslední úprava: Maxová Jana RNDr. Ph.D. (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ů.

Literatura -
Poslední úprava: Maxová Jana RNDr. Ph.D. (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)

Studijní opory -
Poslední úprava: Maxová Jana RNDr. Ph.D. (07.06.2018)

www.vscht.cz/mat/

Metody výuky -
Poslední úprava: Maxová Jana RNDr. Ph.D. (24.09.2018)

přednášky, konzultace, samostatná práce na projektu

Sylabus -
Poslední úprava: Maxová Jana RNDr. Ph.D. (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ů.

Studijní prerekvizity -
Poslední úprava: Mareš Jan doc. Ing. Ph.D. (03.10.2018)

nejsou

Podmínky zakončení předmětu -
Poslední úprava: Maxová Jana RNDr. Ph.D. (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.

Hodnocení studenta
Forma Váha
Ústní zkouška 100

 
VŠCHT Praha