457-0925/01 – Teorie grafů I (TGI)

Garantující katedraKatedra aplikované matematikyKredity10
Garant předmětudoc. Mgr. Petr Kovář, Ph.D.Garant verze předmětudoc. Mgr. Petr Kovář, Ph.D.
Úroveň studiapostgraduálníPovinnostvolitelný odborný
RočníkSemestrzimní + letní
Jazyk výukyčeština
Rok zavedení1995/1996Rok zrušení2009/2010
Určeno pro fakultyFEIUrčeno pro typy studiadoktorské
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+0
kombinovaná Zápočet a zkouška 2+0

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

Student by měl - analyzovat reálný problém - přeformulovet jej do řeči teorie grafů - vyřešit příslušný problém užitím příslušných 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

Předmět pokrývá klasická i mírně pokročilá témata teorie grafů, přesahuje i do dalších disciplín (algenra, kombinatorika). Smyslem je získat přehled o typických problémech z teorie grafů a metodách jejich řešeni. Součástí je řešení praktických problémů užitím teorie grafů, vybrané aplikace a používané algoritmy.

Povinná literatura:

J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum Praha (2003), ISBN 80-246-0084-6. D. Fronček: Úvod do teorie grafů, Slezská univerzita Opava, (1999) ISBN 80-7248-044-8. D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001), ISBN 0-13-0144400-2. P. Kovář, Teorie grafů, pracovní text on-line (2010).

Doporučená literatura:

Bondy, U.S.R. Murty: Graph Theory with Applications, American Esevier Publishing Co., New York, 1976, ISBN 0-444-19451-7. Behzad, G. Chartrand, L. Lesniak-Foster: Graphs and Digraphs, Prindle, Weber and Schmid, Boston, 197, ISBN 0-87150-261-5.

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: Grafy a jednoduché grafy. Isomorfismus grafů. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu. Cesty a cykly. 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í. Hranové barvení. Chromatický index grafu. Vizingova věta. Vrcholové barvení. Chromatické číslo grafu. Brooksova věta. Rovinné grafy. Duální graf. Eulerův vzorec. Kuratowského věta, věta o čtyřech barvách. Orientované grafy. Orientované cesty, orientované cykly. Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu. Eulerovské a Hamiltonovské grafy.

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

Prezenční forma (platnost od: 1960/1961 letní semestr, platnost do: 2012/2013 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.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2009/2010 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika K čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony K čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika K čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika K čeština Ostrava povinně volitelný stu. plán
2009/2010 (P3646) Geodézie a kartografie (3602V002) Geoinformatika P čeština Ostrava volitelný odborný stu. plán
2009/2010 (P3646) Geodézie a kartografie (3602V002) Geoinformatika K čeština Ostrava volitelný odborný stu. plán
2008/2009 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2612) Elektrotechnika a informatika (2612V015) Elektronika K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P3646) Geodézie a kartografie (3602V002) Geoinformatika K čeština Ostrava volitelný odborný stu. plán
2008/2009 (P3646) Geodézie a kartografie (3602V002) Geoinformatika P čeština Ostrava volitelný odborný stu. plán
2007/2008 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2007/2008 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (P2102) Nerostné suroviny (2102V009) Úpravnictví K čeština Ostrava povinný stu. plán
2007/2008 (P2102) Nerostné suroviny (3902V010) Automatizace technologických procesů K čeština Ostrava povinný stu. plán
2007/2008 (P2110) Geologické inženýrství (2101V003) Geologické inženýrství K čeština Ostrava povinný stu. plán
2007/2008 (P2111) Hornictví (2101V009) Hornictví K čeština Ostrava povinný stu. plán
2007/2008 (P3646) Geodézie a kartografie (3602V002) Geoinformatika K čeština Ostrava povinný stu. plán
2007/2008 (P3646) Geodézie a kartografie (3646V001) Důlní měřictví a geodézie K čeština Ostrava povinný stu. plán
2007/2008 (P3904) Inženýrská ekologie (3904V012) Ochrana životního prostředí v průmyslu K čeština Ostrava povinný stu. plán
2006/2007 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2006/2007 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2005/2006 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (1801V002) Informatika a aplikovaná matematika P čeština Ostrava 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