Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Teorie grafů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
XP01TGR ZK 4 2P+1S česky
Přednášející:
Marie Demlová (gar.)
Cvičící:
Marie Demlová (gar.)
Předmět zajišťuje:
katedra matematiky
Anotace:

Základní pojmy teorie grafů. Stromy, jejich charakterizace, minimální kostra. Silně souvislé komponenty, prohledávání a kořenové stromy. Nejkratší cesty, Floydův alagoritmus, algebraické souvislosti. Eulerovské grafy a jejich aplikace. Hamiltonovské grafy, Chvátalova věta. Toky v transportních sítích, Ford- Fulkersonova věta. Přípustné toky a přípustné cirkulace. Párování v obecných grafech, párování v bipartitních grafech. Vrcholové pokrytí a nezávislé množiny. Kliky v grafu a barevnost grafu. Rovinné grafy. Grafy a vektorové prostory. Obsah přednášek je upravován podle potřeb studentů.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/XP01TGR

Požadavky:

Nejsou.

Osnova přednášek:

1. Základní pojmy a vlastnosti neorientovaných grafů.

2. Vrcholová a hranová souvislost, artikulace, mosty.

3. Základní pojmy a vlastnosti orientovaných grafů.

4. Tranzitivní uzávěr a tranzitivní redukce orientovaných grafů, minimálně silně souvislé grafy.

5. Hamiltonovské grafy (neorientované, orientované), Chvátalova věta.

6. Toky v sítích. Ford Fulkersonova věta. Myšlenky rychlých algoritmů pro toky v sítích.

7. Přípustné toky a otázky týkající se jejich existence.

8. Párování v obecných grafech a párovnáni v bipartitních grafech.

9. Nezávislé množiny, kliky, vrcholové pokrytí.

10. Hranové pokrytí., Obarvení s důrazem na vrcholové obarvení.

11. Grafy a vektorové prostory. Prostor kružnic a prosto řezů.

12. Dva pohledy na duální grafy; přes rovinné grafy a přes dualitu prostoru řezů a kružnic.

Osnova cvičení:

Cvičení jsou vedeny formou domácí práce s možností konzultací.

Cíle studia:

Cílem předmětu je seznámit studenty s postupy a fakty teorie grafů a jejích aplikací. Důraz je přitom kladen na samostatnou práci studentů. Během semestru dostávají malé úlohy k vlastnímu řešení, kde je vyžadován správný zápis řešení i se zdůvodněním.

Studijní materiály:

1. Reinhard Diestel: Graph Theory. Springer-Verlag, New York, 1997.

Jiří Demel: Grafy a jejich aplikace, Academia, Praha, 2015

M.N.S. Swamy, K. Thulasiraman: Graphs, Networks, and Algorithms, Part 1, Graph Theory, John Wiley & Sons, New York, 1981

Poznámka:
Další informace:
http://math.feld.cvut.cz/demlova/teaching/grafy_vyuka.html
Rozvrh na zimní semestr 2019/2020:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
místnost T2:C3-54
Demlová M.
08:15–09:00
(přednášková par. 1
paralelka 101)

Dejvice
T2:C3-54
místnost T2:C3-54
Demlová M.
09:15–10:45
(přednášková par. 1)
Dejvice
T2:C3-54
Čt

Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 16. 7. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet11506804.html