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, podzim 2018.

Nahoru | Aktuální datum a čas: 19. 9. 2018 21:10, 38. (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