M5140 Teorie grafů

Přírodovědecká fakulta
podzim 2008
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 13:00–14:50 M1,01017
  • Rozvrh seminárních/paralelních skupin:
M5140/01: Po 9:00–9:50 M2,01021, J. Niederle
M5140/02: Po 10:00–10:50 M2,01021, J. Niederle
Předpoklady
! M5145 Teorie grafů && !( FI: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
předmět má 8 mateřských oborů, zobrazit
Anotace
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í.
Klíčová témata
  • 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
Studijní zdroje a 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
Způsob ověření výstupů z učení a požadavky na ukončení
Zkouška je písemná. Účast na cvičení je povinná, jsou povoleny dvě neomluvené neúčasti nebo pozdní příchody.
Odkaz a informace vyučujících
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
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 2009, 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, podzim 2025.