470-4302/01 – Teorie grafů (TG)

Garantující katedraKatedra aplikované matematikyKredity6
Garant předmětudoc. Mgr. Petr Kovář, Ph.D.Garant verze předmětudoc. Mgr. Petr Kovář, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
RočníkSemestrletní
Jazyk výukyčeština
Rok zavedení2010/2011Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
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í Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 10+10

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:

D. B. West, Introduction to graph theory, Prentice-Hall, Upper Saddle River NJ, (2019), ISBN 9780131437371.

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 a cvičení: 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) Turnaje a grafové modely 14) Další témata: toky v sítích, řezy.

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

Kombinovaná forma (platnost od: 2011/2012 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)		Min. počet bodůMax. počet pokusů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 20 (20) 10
                Zápočtový projekt Projekt 20  10
        Zkouška Zkouška 80 (80) 41 3
                Písemná zkouška Písemná zkouška 60  30
                Teoretická část zkoušky Ústní zkouška 20  5
Rozsah povinné účasti: účast na cvičeních je povinná, lze omluvit 20% neúčast účast na přednáškách je předpokládaná

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP: Splnění všech povinných úkolů v individuálně dohodnutých termínech.

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2023/2024 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika NMS P čeština Ostrava 2 povinný stu. plán
2023/2024 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika NMS K čeština Ostrava 2 povinný stu. plán
2023/2024 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC P čeština Ostrava volitelný odborný stu. plán
2023/2024 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC K čeština Ostrava volitelný odborný stu. plán
2022/2023 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika NMS K čeština Ostrava 2 povinný stu. plán
2022/2023 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika NMS P čeština Ostrava 2 povinný stu. plán
2021/2022 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2021/2022 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2020/2021 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2020/2021 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2020/2021 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2019/2020 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2019/2020 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika P čeština Ostrava povinně volitelný typu B stu. plán
2019/2020 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika K čeština Ostrava povinně volitelný typu B stu. plán
2018/2019 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný 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í
2018/2019 letní
2017/2018 letní
2016/2017 letní
2015/2016 letní
2014/2015 letní
2013/2014 letní
2012/2013 letní