FI:MA032 Cv. Teorie grafů - Informace o předmětu
MA032 Cvičení Teorie grafů
Fakulta informatikypodzim 2003
- Rozsah
- 0/1. 1 kr. (plus ukončení). Ukončení: z.
- Vyučující
- doc. RNDr. Josef Niederle, CSc. (přednášejí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: Po 10:00–10:50 B410, J. Niederle
MA032/02: Po 11:00–11:50 B410, J. Niederle - Předpoklady
- ! M032 Cv. Kombinatorika a grafy && NOW( MA010 Teorie grafů )
- 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
- Aplikovaná informatika (program FI, N-AP)
- Informatika (program FI, M-IN)
- Informatika (program FI, N-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
- Učitelství výpočetní techniky pro střední školy (program FI, N-SS)
- 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
- 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
- Metody hodnocení
- Prvním požadavkem k získání zápočtu je účast na cvičeních. Jsou dovoleny dvě neomluvené neúčasti nebo pozdní příchody. 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.
- 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 nebo pozdní příchody. 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ě.
- Statistika zápisu (podzim 2003, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2003/MA032