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

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.Zaměření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

Hodnocení Výuky

Předmět neobsahuje žádné hodnocení.