PřF:M5145 Teorie grafů - Informace o předmětu
M5145 Teorie grafů
Přírodovědecká fakultajaro 2004
- Rozsah
- 2/1/0. 3 kr. (příf plus uk plus > 4). Ukončení: zk.
- Vyučující
- doc. RNDr. Eduard Fuchs, CSc. (přednášející)
RNDr. Zuzana Kopečná Voglová (cvičící)
RNDr. Pavel Šišma, Dr. (cvičící) - Garance
- doc. RNDr. Eduard Fuchs, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. RNDr. Eduard Fuchs, CSc. - Rozvrh
- Čt 9:00–10:50 UM
- Rozvrh seminárních/paralelních skupin:
M5145/02: Rozvrh nebyl do ISu vložen. Z. Kopečná Voglová, Rozvrhově doporučeno 3;11+4;12,90 - Předpoklady
- M1555 Kombinatorika && ! M5140 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
- Matematika pro víceoborové studium (program PřF, B-MA)
- Matematika se zaměřením na vzdělávání (program PřF, B-MA)
- Učitelství matematiky pro střední školy (program PřF, M-MA)
- Učitelství matematiky pro střední školy (program PřF, M-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, podgrafu
- Sledy: Sledy, tahy, cesty, kružnice, souvislost a komponenty
- Eulerovské a hamiltonovské grafy
- Stromy: Charakterizace a vlastnosti, počet stromů na dané množině, izomorfismus stromů
- Kostra grafu: Hledání minimální kostry
- Hledání optimální cesty: Moorův algoritmus, Dijkstrův algoritmus, Fordův algoritmus, 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í
- 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
- NEŠETŘIL, Jaroslav. Kombinatorika. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1983, 173 s. URL info
- FUCHS, Eduard. Diskrétní matematika pro učitele. 1. vyd. Brno: Masarykova univerzita, 2001, 178 s. ISBN 80-210-2703-7. info
- FUCHS, Eduard. Diskrétní matematika a Teorie množin pro učitele (CD-ROM). Brno: Masarykova univerzita, 2000, 890 s. Matematika na CD-ROM, sv. 2. ISBN 80-210-2463-1. info
- Další komentáře
- Předmět je vyučován každoročně.
- Nachází se v prerekvizitách jiných předmětů
- M5140 Teorie grafů
!M5145 && !(FI:MA010)
- M5140 Teorie grafů
- Statistika zápisu (jaro 2004, nejnovější)
- Permalink: https://is.muni.cz/predmet/sci/jaro2004/M5145