Popis předmětu - XP01TGR

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
XP01TGR Teorie grafů Rozsah výuky:2+1
Garanti:Demlová M. Role:S Jazyk výuky:CS
Vyučující:Demlová M. Zakončení:ZK
Zodpovědná katedra:13101 Kreditů:4 Semestr:Z

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: 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.

Obsah:

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.

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.

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

Požadavky:

Nejsou.

Webová stránka:

http://math.feld.cvut.cz/demlova/teaching/grafy_vyuka.html

Klíčová slova:

Orientované a neorientované grafy, k-souvislost, silná souvislost, hamiltonovské grafy, toky v sítich, párování, nezávislé množiny, kliky, vrcholové a hranové pokrytí, barvení (vrcholové a hranové), grafy a vektorové prostory.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
DOKP Před zařazením do oboru S
DOKK Před zařazením do oboru S


Stránka vytvořena 24.5.2019 17:51:57, semestry: Z,L/2020-1, L/2019-20, Z,L/2018-9, Z/2019-20, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.