MA010 Teorie grafů

Fakulta informatiky
podzim 2002
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučující
doc. RNDr. Josef Niederle, CSc. (přednášející)
Garance
doc. RNDr. Josef Niederle, CSc.
Fakulta informatiky
Rozvrh
Čt 10:00–11:50 D2
Předpoklady
! M010 Kombinatorika a grafy
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory
předmět má 6 mateřských oborů, zobrazit
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, skóre grafu, metrika v 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
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.
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 2003, podzim 2004, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017.

Nahoru | Aktuální datum a čas: 20. 4. 2018 04:44, 16. (sudý) týden

Kontakty: istech(zavináč/atsign)fi(tečka/dot)muni(tečka/dot)cz, studijní odd., správci práv, is-technici, e-technici, IT podpora | Použití cookies | Více o Informačním systému