M5140 Teorie grafů

Přírodovědecká fakulta
podzim 2009
Rozsah
2/1/0. 3 kr. (příf plus uk plus > 4). Ukončení: zk.
Vyučující
doc. RNDr. Josef Niederle, CSc. (přednášející)
Garance
doc. RNDr. Josef Niederle, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Po 14:00–15:50 M1,01017
  • Rozvrh seminárních/paralelních skupin:
M5140/01: Po 10:00–10:50 M2,01021, J. Niederle
M5140/02: Po 11:00–11:50 M2,01021, J. Niederle
Předpoklady
! M5145 Teorie grafů && !( FI:MA010 Graph Theory )
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ů. Studenti budou ovládat 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
Výukové metody
Přednášky, cvičení.
Metody hodnocení
Zkouška je písemná. Účast na cvičení je povinná, jsou povoleny dvě neomluvené neúčasti nebo pozdní příchody.
Informace učitele
Požadavkem připuštění ke zkoušce 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. Je proto nutné, abyste se do některé seminární skupiny přihlásili a s touto skupinou cvičení absolvovali. 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. Musíte se však naučit pojmy, terminologii a značení, které používám na přednášce.
Další komentáře
Studijní materiály
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 2007 - akreditace, podzim 1999, podzim 2010 - akreditace, podzim 2000, podzim 2001, podzim 2002, podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2010, podzim 2011, podzim 2011 - akreditace, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.