M5145 Teorie grafů

Přírodovědecká fakulta
jaro 2009
Rozsah
2/1/0. 3 kr. (příf plus uk plus > 4). Ukončení: zk.
Vyučující
doc. RNDr. Eduard Fuchs, CSc. (přednášející)
RNDr. Pavel Šišma, Dr. (cvičící)
Garance
doc. RNDr. Eduard Fuchs, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Čt 14:00–15:50 01031
  • Rozvrh seminárních/paralelních skupin:
M5145/01: Po 11:00–11:50 01031, P. Šišma
Předpoklady
M1555 Kombinatorika && ! M5140 Teorie grafů && !( FI:MA010 Teorie grafů )
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Tento kurs je úvodem do teorie grafů. Uvádí základní pojmy a jejich vlastnosti, formulace jednoduchých grafových úloh a standardní efektivní algoritmy jejich řešení.
Osnova
  • Základní terminologie: Definice grafu, podgrafu
  • Sledy: Sledy, tahy, cesty, kružnice, souvislost a komponenty
  • Eulerovské a hamiltonovské grafy
  • Stromy: Charakterizace a vlastnosti, počet stromů na dané množině, izomorfismus stromů
  • Kostra grafu: Hledání minimální kostry
  • Hledání optimální cesty: Moorův algoritmus, Dijkstrův algoritmus, Fordův algoritmus, Toky v sítích: Věta o maximálním toku a minimálním řezu, Fordův-Fulkersonův algoritmus
  • Párování: Bipartitní grafy, párování
  • Rovinné grafy: Eulerův vzorec a jeho důsledky, obarvení rovinného grafu pěti barvami
Literatura
  • KUČERA, Luděk. Kombinatorické algoritmy. 2., nezměn. vyd. Praha: SNTL - Nakladatelství technické literatury. 286 s. 1989. info
  • NEŠETŘIL, Jaroslav. Teorie grafů. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury. 316 s. 1979. URL info
  • PLESNÍK, Ján. Grafové algoritmy. 1. vyd. Bratislava: Veda. 343 s. 1983. info
  • NEŠETŘIL, Jaroslav. Kombinatorika. Vyd. 1. Praha: Státní pedagogické nakladatelství. 173 s. 1983. URL info
  • FUCHS, Eduard. Diskrétní matematika pro učitele. 1. vyd. Brno: Masarykova univerzita. 178 s. ISBN 80-210-2703-7. 2001. info
  • FUCHS, Eduard. Diskrétní matematika a Teorie množin pro učitele (CD-ROM). Brno: Masarykova univerzita. 890 s. Matematika na CD-ROM, sv. 2. ISBN 80-210-2463-1. 2000. info
Metody hodnocení
Ústní zkouška
Další komentáře
Předmět je vyučován každoročně.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích jaro 2008 - akreditace, jaro 2003, jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/sci/jaro2009/M5145