Graph Theory and Applications - AP413001
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: anglič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, P413001
Termíny zkoušek   
Anotace -
Poslední úprava: Pátková Vlasta (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: Pátková Vlasta (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: Pátková Vlasta (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. (14.05.2019)

https://um.vscht.cz/

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: Pátková Vlasta (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ů.

Vstupní požadavky -
Poslední úprava: Borská Lucie RNDr. Ph.D. (16.09.2019)

Matematika A, B

Studijní prerekvizity -
Poslední úprava: Borská Lucie RNDr. Ph.D. (16.09.2019)

nejsou

Podmínky zakončení předmětu -
Poslední úprava: Pátková Vlasta (08.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.