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

Garantující katedraKatedra aplikované matematikyKredity4
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ý
Ročník2Semestrletní
Jazyk výukyčeština
Rok zavedení2016/2017Rok zrušení
Určeno pro fakultyUSPUrč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.
KUB59 RNDr. Michael Kubesa, 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) D. Fronček: Úvod do teorie grafů, Slezská univerzita Opava, (1999). J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum Praha (2000).

Doporučená literatura:

D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001).

Způsob průběžné kontroly znalostí během semestru

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

Prezenční forma (platnost od: 2016/2017 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 20  10
        Zkouška Zkouška 80 (80) 41
                Písemná část 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á, jsou akceptovány 2 omluvy účast na přednáškách je předpokládaná, jsou akceptovány 4 omluvy

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramOborSpec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2018/2019 (N2658) Výpočetní vědy (2612T078) Výpočetní vědy P čeština Ostrava 2 povinně volitelný stu. plán
2017/2018 (N2658) Výpočetní vědy (2612T078) Výpočetní vědy P čeština Ostrava 2 povinně volitelný stu. plán
2016/2017 (N2658) Výpočetní vědy (2612T078) Výpočetní vědy P čeština Ostrava 2 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