457-0305/02 – 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ý
Ročník2Semestrletní
Jazyk výukyčeština
Rok zavedení2003/2004Rok zrušení2009/2010
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské, navazují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 problémy skutečné úlohy - přeformulovet je 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ě 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

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). Součástí je řešení praktických problémů užitím teorie grafů.

Povinná literatura:

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).

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 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

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. Isomorfismus grafů. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu. Cesty a cykly. 2) Stromy, mosty a oddělující množiny (řezy). Artikulace. Souvislost grafů, bloky. Párování a pokrytí v grafech a biparitních grafech. Perfektní párování. 3) Hranové barvení. Chromatický index grafu. Vizingova věta. 4) Vrcholové barvení. Chromatické číslo grafu. Brooksova věta. 5) Rovinné grafy. Duální graf. Eulerův vzorec pro souvislé planární grafy. Kuratowského věta, věta o čtyřech barvách. 6) Eulerovské a hamiltonovské grafy. 7) Orientované grafy. Orientované cesty, orientované cykly. 8) Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu. Cvičení: 1) Grafy a jednoduché grafy. Podgrafy. Stupeň vrcholu. Cesty a cykly. Významné třídy grafů. 2) Stromy, mosty a oddělující množiny (řezy). Artikulace. 3) Souvislost grafů. 4) Párování a pokrytí v grafech a biparitních grafech. Perfektní párování. 5) Hranové barvení. Chromatický index grafu. 6) Vrcholové barvení. Chromatické číslo grafu. 7) Rovinné grafy. Eulerův vzorec pro libovolné planární grafy. 8) Eulerovské a hamiltonovské grafy. 9) Orientované grafy. Orientované cesty, orientované cykly.

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

Prezenční forma (platnost od: 1960/1961 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
        Zkouška Zkouška 80  41
        Zápočet Zápočet 20  10
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2009/2010 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2009/2010 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný stu. plán
2005/2006 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 2 povinně volitelný stu. plán
2005/2006 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 2 povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 2 povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (1103T021) Počítačová matematika K č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