Teorie grafů

Garant předmětu:

Marie Demlová

Přednášející:

Marie Demlová

Cvičící:

Marie Demlová

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:

https://moodle.fel.cvut.cz/courses/XP01TGR

Rozvrh na zimní semestr 2023/2024:

	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:C2-83 Demlová M. 08:15–09:00 (přednášková par. 1 paralelka 101) Dejvice cvičebnamístnost T2:C2-83 Demlová M. 09:15–10:45 (přednášková par. 1) Dejvice cvičebna
Čt
Pá

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Doktorské studium, prezenční forma (povinně volitelný předmět)
• Doktorské studium, kombinovaná forma (povinně volitelný předmět)
• Doktorské studium, strukturované prezenční (povinně volitelný předmět)
• Doktorské studium, strukturované kombinované (povinně volitelný předmět)