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íPovinnostpovinně volitelný typu B
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í: - Grafy a jednoduché grafy. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu. - Cesty a cykly v grafu. Excentricita, průměr a poloměr - Stromy, mosty a bipartitní grafy. - Isomorfismus grafů - Vrcholová a hranová souvislost grafů, bloky. Artikulace. Oddělující množiny (řezy). - Párování a pokrytí v grafech a biparitních grafech. Perfektní párování. - Hranové barvení. Chromatický index grafu. Vizingova věta. - Vrcholové barvení. Chromatické číslo grafu. Brooksova věta. - Rovinné grafy. Duální graf. Eulerův vzorec pro souvislé planární grafy. Kuratowského věta, věta o čtyřech barvách. - Nerovinné grafy, míry neplanarity. - Eulerovské a hamiltonovské grafy. - Orientované grafy. Orientované cesty, orientované cykly. - Turnaje a grafové modely

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
2024/2025 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika NMS K čeština Ostrava 2 povinný stu. plán
2024/2025 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika NMS P čeština Ostrava 2 povinný stu. plán
2024/2025 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC P čeština Ostrava volitelný odborný stu. plán
2024/2025 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC K čeština Ostrava volitelný odborný stu. plán
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í