470-6302/01 – Teorie grafů I (TGI)

Garantující katedraKatedra aplikované matematikyKredity10
Garant předmětudoc. Mgr. Petr Kovář, Ph.D.Garant verze předmětudoc. Mgr. Petr Kovář, Ph.D.
Úroveň studiapostgraduálníPovinnostpovinně volitelný typu B
RočníkSemestrzimní + letní
Jazyk výukyčeština
Rok zavedení2010/2011Rok zrušení
Určeno pro fakultyHGF, FEIUrčeno pro typy studiadoktorské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
KOV16 doc. Mgr. Petr Kovář, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zkouška 28+0
kombinovaná Zkouška 28+0

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Student by měl - analyzovat reálný problém - přeformulovet jej do řeči teorie grafů - vyřešit příslušný problém užitím příslušných postupů teorie grafů - interpretovat teoretické výsledky v kontextu původní úlohy Současně je nutno 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

Předmět pokrývá klasická i mírně pokročilá témata teorie grafů, přesahuje i do dalších disciplín (algenra, kombinatorika). Smyslem je získat přehled o typických problémech z teorie grafů a metodách jejich řešeni. Součástí je řešení praktických problémů užitím teorie grafů, vybrané aplikace a používané algoritmy.

Povinná literatura:

D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2019), ISBN 9780131437371. P. Kovář, Teorie grafů, text on-line (2022).

Doporučená literatura:

J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum Praha (2010), ISBN 978-80-246-1740-4.

Další studijní materiály

Forma způsobu ověření studijních výsledků a další požadavky na studenta

Aktivní účast na přednáškách. Konzultace projektu. Zkouška má písemnou a ústní část.

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

Osnova přednášek 1) Grafy, jednoduché grafy. Podgrafy. Stupeň vrcholu. Incidenční matice a matice sousednosti. 2) Cesty a cykly. Vzdálenost a excentricita. 3) Stromy a kostry, bipartitní grafy. 4) Isomorfismus grafů, automorfismy. 5) Souvislost grafů, mosty, oddělující množiny (řezy), bloky, artikulace. 6) Párování a pokrytí v grafech a bipartitních grafech. Přiřazovací problém. Úplné párování. 7) Hranová barvení a jejich aplikace. Chromatický index grafu. Vizingova věta. 8) Vrcholová barvení a jejich aplikace. Chromatické číslo grafu. Brooksova věta. 9) Planární grafy a jejich aplikace. Eulerův vzorec. Kuratowského věta, věta o čtyřech barvách. 10) Neplanární grafy, míry neplanarity 11) Eulerovské a hamiltonovské grafy. 12) Orientované grafy. Orientované cesty, cykly, turnaje. 13) Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu. V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty.

Podmínky absolvování předmětu

Kombinovaná forma (platnost od: 2013/2014 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Zkouška Zkouška   3
Rozsah povinné účasti:

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2024/2025 (P0541D170005) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2024/2025 (P0541D170005) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2024/2025 (P0613D140005) Informatika P čeština Ostrava povinně volitelný typu B stu. plán
2024/2025 (P0613D140005) Informatika K čeština Ostrava povinně volitelný typu B stu. plán
2024/2025 (P0613D140032) Informatika a výpočetní vědy K čeština Ostrava povinně volitelný typu B stu. plán
2024/2025 (P0613D140032) Informatika a výpočetní vědy P čeština Ostrava povinně volitelný typu B stu. plán
2024/2025 (P0714D060001) Komunikační technologie P čeština Ostrava povinně volitelný typu B stu. plán
2024/2025 (P0714D060001) Komunikační technologie K čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0714D060001) Komunikační technologie K čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0714D060001) Komunikační technologie P čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0613D140032) Informatika a výpočetní vědy P čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0613D140032) Informatika a výpočetní vědy K čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0541D170005) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0541D170005) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0613D140005) Informatika P čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P0613D140005) Informatika K čeština Ostrava povinně volitelný typu B stu. plán
2023/2024 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2023/2024 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2023/2024 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2023/2024 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2023/2024 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2023/2024 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2022/2023 (P0541D170005) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2022/2023 (P0541D170005) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2022/2023 (P0613D140005) Informatika P čeština Ostrava povinně volitelný typu B stu. plán
2022/2023 (P0613D140005) Informatika K čeština Ostrava povinně volitelný typu B stu. plán
2022/2023 (P0714D060001) Komunikační technologie P čeština Ostrava povinně volitelný typu B stu. plán
2022/2023 (P0714D060001) Komunikační technologie K čeština Ostrava povinně volitelný typu B stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2022/2023 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2022/2023 (P0613D140032) Informatika a výpočetní vědy P čeština Ostrava povinně volitelný typu B stu. plán
2022/2023 (P0613D140032) Informatika a výpočetní vědy K čeština Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0541D170005) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0541D170005) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0613D140005) Informatika P čeština Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0613D140005) Informatika K čeština Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0714D060001) Komunikační technologie K čeština Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0714D060001) Komunikační technologie P čeština Ostrava povinně volitelný typu B stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2020/2021 (P0541D170005) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0541D170005) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140005) Informatika K čeština Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140005) Informatika P čeština Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0714D060001) Komunikační technologie P čeština Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0714D060001) Komunikační technologie K čeština Ostrava povinně volitelný typu B stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2019/2020 (P0613D140005) Informatika P čeština Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0714D060001) Komunikační technologie P čeština Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0541D170005) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0541D170005) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0613D140005) Informatika K čeština Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0714D060001) Komunikační technologie K čeština Ostrava povinně volitelný typu B stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2014/2015 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2014/2015 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2014/2015 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2014/2015 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2014/2015 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2014/2015 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2014/2015 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2014/2015 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K angličtina Ostrava povinně volitelný stu. plán
2013/2014 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2013/2014 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2013/2014 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2013/2014 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2013/2014 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2013/2014 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2012/2013 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2012/2013 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2012/2013 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2012/2013 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2012/2013 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2012/2013 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2011/2012 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2011/2012 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2011/2012 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2011/2012 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2011/2012 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2011/2012 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán
2010/2011 (P2612) Elektrotechnika a informatika (2601V013) Telekomunikační technika P čeština Ostrava povinně volitelný stu. plán
2010/2011 (P2612) Elektrotechnika a informatika (2601V013) Telekomunikační technika K čeština Ostrava povinně volitelný stu. plán
2010/2011 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2010/2011 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2010/2011 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P čeština Ostrava povinně volitelný stu. plán
2010/2011 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K čeština Ostrava povinně volitelný stu. plán
2010/2011 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2010/2011 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2010/2011 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie P čeština Ostrava povinně volitelný stu. plán
2010/2011 (P1807) Informatika, komunikační technologie a aplikovaná matematika (2601V018) Komunikační technologie K čeština Ostrava povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku

Hodnocení Výuky



2019/2020 letní