457-0305/01 – Teorie grafů (TG)

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

Rozsah výuky pro formy studia
Forma studia	Zp.zak.	Rozsah
prezenční	Zápočet a zkouška	2+2
kombinovaná	Zápočet a zkouška	2+2

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

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

1. Průměr, poloměr a obvod grafu. 2. Hranové grafy. Definice a konstrukce hranových grafů. Charakteristika hranových grafů. 3. Samokomplementární grafy. Komplement grafu. Vztah mezi průměrem grafu a jeho komplementem. Konstrukce nekonečných tříd samokomplementárních grafů. 4. Rozklady grafů. Rozklady kompletních grafů na izomorfní faktory. Rozklady grafů na faktory s danými průměry. Rozklady kompletních multiparitních grafů. 5. Problém rekonstrukce grafů. 6. Ramseyova teorie. Extremální teorie grafů. Ramseyova čísla. Zobecněná Ramseyova čísla. Další podobné problémy. 7. Grafy a grupy. Grupa amorfismu grafu. Grupa hranového automorfismu grafu. Cayleyho grafy. 8. Grafy s předepsaným okolím. Grafy s konstantním okolím. Extremální problémy. 9. Hypergrafy a designy. Hypergrafy, k uniformní hypergrafy. Designy. 10. Náhodné grafy. Enumerace grafů.

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

Kombinovaná 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.	Zaměření	Forma	Jazyk výuky	Konz. stř.	Ročník	Z	L	Typ povinnosti
2003/2004	(N2646) Informační technologie	(1103T021) Počítačová matematika			P	čeština	Ostrava	2			povinně volitelný	stu. plán
2003/2004	(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 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í.