470-4302/03 – Teorie grafů (TG)
Garantující katedra | Katedra aplikované matematiky | Kredity | 4 |
Garant předmětu | doc. Mgr. Petr Kovář, Ph.D. | Garant verze předmětu | doc. Mgr. Petr Kovář, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
Ročník | 2 | Semestr | letní |
| | Jazyk výuky | čeština |
Rok zavedení | 2016/2017 | Rok zrušení | 2020/2021 |
Určeno pro fakulty | USP | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Student by měl
- analyzovat praktickou úlohu
- přeformulovat ji do řeči teorie grafů
- vyřešit příslušný problém užitím postupů teorie grafů
- interpretovat teoretické výsledky v kontextu původní úlohy
Současně musí kriticky zhodnotit meze použitelnosti ideálního řešení v reálné situaci.
Vyučovací metody
Přednášky
Individuální konzultace
Cvičení (v učebně)
Projekt
Anotace
Obsahem kursu jsou vybraná základní i pokročilejší témata z teorie grafů, přesahující i do dalších disciplín (algebra, kombinatorika).
V rámci předmětu vypracují studenti jeden projekt případně dva projekty zaměřené na řešení praktických problémů užitím teorie grafů.
Povinná literatura:
P. Kovář: Teorie grafů, VŠB (2011)
J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum Praha (2010).
Doporučená literatura:
Forma způsobu ověření studijních výsledků a další požadavky na studenta
V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty.
Témata jsou volena z okruhů probíraných na přednášce.
Termíny odevzdání i jednotlivá zadání jsou k dispozici na stránce vyučujícího nebo v elektronickém informačním systému.
(Na témata se přihlašujte včas před odevzdáním.)
Pro udělení zápočtu je nutné uznání projektu za alespoň 10 bodů.
E-learning
Další požadavky na studenta
Žádné další požadavky na studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
1) Grafy a jednoduché grafy. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu.
2) Cesty a cykly v grafu. Excentricita, průměr a poloměr
3) Stromy, mosty a bipartitní grafy.
4) Isomorfismus grafů
5) Vrcholová a hranová souvislost grafů, bloky. Artikulace. Oddělující množiny (řezy).
6) Párování a pokrytí v grafech a biparitních grafech. Perfektní párování.
7) Hranové barvení. Chromatický index grafu. Vizingova věta.
8) Vrcholové barvení. Chromatické číslo grafu. Brooksova věta.
9) Rovinné grafy. Duální graf. Eulerův vzorec pro souvislé planární grafy. Kuratowského věta, věta o čtyřech barvách.
10) Nerovinné grafy, míry neplanarity.
11) Eulerovské a hamiltonovské grafy.
12) Orientované grafy. Orientované cesty, orientované cykly.
13 a 14) Další témata: toky v sítích, řezy. Modely.
Cvičení:
1) Grafy a jednoduché grafy. Podgrafy. Stupeň vrcholu.
2) Cesty a cykly. Významné třídy grafů. Excentricita vrcholů.
3) Stromy, mosty. Bipartitní grafy a Hallova věta
4) Isomorfismus a automorfismus grafů.
5) Vrcholová a hranová souvislost grafů, oddělující množiny (řezy). Artikulace.
6) Párování a pokrytí v grafech a biparitních grafech. Perfektní párování. Vztah mezi párováním a pokrytím.
7) Hranová barvení grafů. Chromatický index grafu. Třídy grafů I a II.
8) Vrcholová barvení grafů. Chromatické číslo grafu. Odhady chromatického čísla.
9) Rovinné grafy. Eulerův vzorec pro libovolné planární grafy.
10) Nerovinné grafy a míry neplanarity.
11) Eulerovské a hamiltonovské grafy.
12) Orientované grafy. Orientované cesty, orientované cykly.
13 a 14) Další témata: grafové modely a jejich využití.
V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty dle pokynů přednášejícího. Témata jsou volena z okruhů probíraných na přednášce a jsou uvedena na stránce vyučujícího nebo v elektronickém informačním sytému, například:
1) rovinné grafy a jejich využití při řešení praktické úlohy
2) barvení grafů a jejich využití při řešení praktické úlohy
Pro udělení zápočtu je nutné uznání projektu za alespoň 10 bodů.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.