Přeskočit na hlavní obsah
Přeskočit hlavičku
Ukončeno v akademickém roce 2009/2010

Teorie grafů

Typ studia navazující magisterské
Jazyk výuky čeština
Kód 457-0305/01
Zkratka TG
Název předmětu česky Teorie grafů
Název předmětu anglicky Graph Theory
Kreditů 4
Garantující katedra Katedra aplikované matematiky
Garant předmětu doc. RNDr. Dalibor Fronček, CSc., Ph.D.

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ů.

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).