Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
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:
https://moodle.fel.cvut.cz/courses/XP01TGR
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ů:
| Stránka vytvořena 26.11.2020 15:50:47, semestry: L/2021-2, Z,L/2020-1, L/2019-20, Z/2021-2, 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) |