MA010 Teorie grafů

Fakulta informatiky
podzim 2004
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučující
doc. RNDr. Josef Niederle, CSc. (přednášející)
prof. RNDr. Luboš Brim, CSc. (pomocník)
Garance
doc. RNDr. Josef Niederle, CSc.
Fakulta informatiky
Rozvrh
Pá 14:00–15:50 A107
Předpoklady
! M010 Kombinatorika a grafy
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
Mateřské obory/plány
předmět má 6 mateřských oborů, zobrazit
Cíle předmětu
Tento kurs je úvodem do teorie grafů s důrazem na aplikaci. 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, skóre grafu
  • Sledy: Sledy, tahy, cesty, kružnice, souvislost a komponenty
  • Eulerovské a hamiltonovské grafy
  • Stromy: Charakterizace a vlastnosti, počet stromů na dané množině, kořenové stromy, uspořádané kořenové stromy, binární stromy a jejich počet, centrum a bicentrum, izomorfismus stromů
  • Kostra grafu: Hledání minimální kostry
  • Hledání optimální cesty: Moorův algoritmus, Dijkstrův algoritmus, Fordův algoritmus, algoritmus vypouštění zdrojů, metoda kritické cesty, cesty s největší propustností
  • 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í
  • Míry souvislosti grafu: Mengerova věta, 2-souvislé a 3-souvislé grafy
  • Rovinné grafy: Eulerův vzorec a jeho důsledky, obarvení rovinného grafu pěti barvami.
Literatura
  • KUČERA, Luděk. Kombinatorické algoritmy. 2. vyd. Praha: Státní nakladatelství technické literatury, 1989. 286 s. info
  • NEŠETŘIL, Jaroslav. Teorie grafů [Nešetřil, 1979]. 1. vyd. Praha: SNTL - Nakladatelství technické literatury, 1979. 316 s. info
  • PLESNÍK, Ján. Grafové algoritmy. 1. vyd. Bratislava: Veda, 1983. 343 s. info
  • FUCHS, Eduard. Kombinatorika a teorie grafů. 1. vyd. Praha: Státní pedagogické nakladatelství, 1986. 138 s. info
  • NEŠETŘIL, Jaroslav. Kombinatorika. I, Grafy. 1. vyd. Praha: Státní pedagogické nakladatelství, 1983. 173 s. info
Metody hodnocení
Zkouška je písemná.
Navazující předměty
Informace učitele
Kurs je společný s bakalářským studiem matematiky, není zaměřen na aplikace v informatice. Vyžaduje se znalost látky uvedené v osnově v rozsahu přednášky. Každá část je obsažena alespoň v jedné položce zadané literatury. Nestačí přečíst jen některé z nich. Od studentů požaduji, aby měli chuť a vůli na sobě pracovat.
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 podzim 2002, podzim 2003, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021.