Moodle FEL ČVUT
Teorie grafů
B232 - Letní 23/24
Teorie grafů - XP01TGR
| Kredity | 4 |
| Semestry | zimní |
| Zakončení | zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 2P+1S |
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
\\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/XP01TGR
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.
Osnovy 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.
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.
Osnovy cvičení
Cvičení jsou vedeny formou domácí práce s možností konzultací.
Literatura
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
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
Požadavky
Nejsou.