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

Garantující katedra	Katedra aplikované matematiky	Kredity	4
Garant předmětu	doc. RNDr. Dalibor Fronček, CSc., Ph.D.	Garant verze předmětu	doc. RNDr. Dalibor Fronček, CSc., Ph.D.
Úroveň studia	pregraduální nebo graduální	Povinnost	povinný
Ročník	2	Semestr	letní
		Jazyk výuky	čeština
Rok zavedení	1992/1993	Rok zrušení	2002/2003
Určeno pro fakulty	FEI	Určeno pro typy studia	magisterské

Rozsah výuky pro formy studia
Forma studia	Zp.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 úlohy	Typ úlohy	Max. 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ý rok	Program	Obor/spec.	Spec.	Forma	Jazyk výuky	Konz. stř.	Ročník	Typ 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 bloku	Akademický rok	Forma studia	Jazyk výuky	Ročník	Z	L	Typ bloku	Vlastník bloku

Hodnocení Výuky

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