MA032 Cvičení Teorie grafů

Fakulta informatiky
podzim 2002
Rozsah
0/1. 1 kr. (plus ukončení). Ukončení: z.
Vyučující
doc. RNDr. Josef Niederle, CSc. (cvičící)
Mgr. Andrea Pavliňáková (cvičící)
Garance
doc. RNDr. Jiří Kaďourek, CSc.
Fakulta informatiky
Kontaktní osoba: doc. RNDr. Josef Niederle, CSc.
Rozvrh seminárních/paralelních skupin
MA032/01: Út 17:00–17:50 B011, J. Niederle
MA032/02: Út 18:00–18:50 B011, J. Niederle
MA032/03: Út 19:00–19:50 B011, J. Niederle
MA032/04: Pá 10:00–10:50 B011, A. Pavliňáková
MA032/05: Pá 11:00–11:50 B011, A. Pavliňáková
Předpoklady
! M032 Cv. Kombinatorika a grafy && NOW( 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, 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., nezměn. vyd. Praha: SNTL - Nakladatelství technické literatury, 1989, 286 s. info
  • NEŠETŘIL, Jaroslav. Teorie grafů. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1979, 316 s. URL info
  • PLESNÍK, Ján. Grafové algoritmy. 1. vyd. Bratislava: Veda, 1983, 343 s. info
  • FUCHS, Eduard. Kombinatorika a teorie grafů. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1986, 138 s. info
  • NEŠETŘIL, Jaroslav. Kombinatorika. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1983, 173 s. URL info
Navazující předměty
Informace učitele
Prvním požadavkem k získání zápočtu je účast na cvičeních. Jsou dovoleny dvě neomluvené neúčasti. Započítává se jen účast studenta v té seminární skupině, do které je přihlášen. Při vyjímečném nahrazování musí student požádat o prezenční listinu své seminární skupiny. Druhým požadavkem je, aby student získal alespoň polovinu bodů ze zápočtové písemné práce.
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2003, podzim 2004.