457-0043/01 – Teorie grafů (TGR)

Garantující katedraKatedra aplikované matematikyKredity4
Garant předmětudoc. RNDr. Dalibor Fronček, CSc.,Ph.D.Garant verze předmětudoc. RNDr. Dalibor Fronček, CSc.,Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
RočníkSemestrletní
Jazyk výukyčeština
Rok zavedení1992/1993Rok zrušení2002/2003
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2

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

Vyučovací metody

Anotace

Předmět pokrývá běžný základní kurs z teorie grafů. Jeho cílem je podat přehled o typických problémech teorie grafů a metodách jejich řešení. Uvedeny jsou i některé aplikace a používané algoritmy.

Povinná literatura:

D. Fronček: Úvod do teorie grafů, Slezská univerzita Opava, 1999. A. Bondy, U.S.R. Murty: Graph Theory with Applications, American Elsevier Publishing Co., New York, 1976, ISBN 0-444-19451-7. Behzad, G. Chartrand, L. Lesniak-Foster: Graphs and Digraphs, Prindle, Weber and Schmid, Boston, 1977, ISBN 0-87150-261-5.

Doporučená literatura:

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

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. 3. Souvislost grafů, bloky. 4. Párování a pokrytí v grafech a biparitních grafech. Perfektní párování. 5. Hranové barvení. Chromatický index grafu. Vizingova věta. 6. Vrcholové barvení. Chromatické číslo grafu. Brooksova věta. 7. Rovinné grafy. Duální graf. Eulerův vzorech. Kuratowského věta, věta o čtyřech barvách. 8. Orientované grafy. orientované cesty, orientované cykly. 9. Toky v sítích, řezy. Věta o maxímálním toku a minimálním řezu. 10. Eulerovské a hamiltonovské grafy.

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 (145) 51
        Zkouška Zkouška 100  0
        Zápočet Zápočet 45  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2005/2006 (M2612) Elektrotechnika a informatika (2612T999) Společný základ pro FEI P čeština Ostrava 2 povinný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2612T999) Společný základ pro FEI P čeština Ostrava 2 povinný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 2 povinný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2612T999) Společný základ pro FEI P čeština Ostrava 2 povinný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 2 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 2 povinný stu. plán
2000/2001 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 2 povinný stu. plán

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

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