M5140 Teorie grafů

Přírodovědecká fakulta
podzim 2017
Rozsah
2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 4). Ukončení: zk.
Vyučující
doc. Mgr. Michal Kunc, Ph.D. (přednášející)
Garance
doc. Mgr. Michal Kunc, Ph.D.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Dodavatelské pracoviště: Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Po 18. 9. až Pá 15. 12. Po 14:00–15:50 M2,01021
  • Rozvrh seminárních/paralelních skupin:
M5140/01: Po 18. 9. až Pá 15. 12. Po 16:00–16:50 M2,01021, M. Kunc
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 kurz je úvodem do teorie grafů. Po absolvování tohoto kurzu budou studenti schopni: používat základní pojmy teorie grafů; definovat a chápat základní vlastnosti grafů, zejména hranovou a vrcholovou souvislost, rovinnost a chromatické číslo; formulovat a aplikovat nejdůležitější výsledky teorie grafů; řešit jednoduché grafové úlohy pomocí standardních efektivních algoritmů.
Osnova
  • Základní pojmy: definice grafu, základní grafy, reprezentace grafů, izomorfismus grafů, podgrafy, skóre.
  • Sledy, tahy, cesty: nejkratší cesty, počet sledů, markovské řetězce.
  • Toky v sítích: věta o maximálním toku.
  • Hranová a vrcholová souvislost: komponenty, mosty, Mengerova věta, 2-souvislé grafy, bloky grafu, 3-souvislé grafy.
  • Procházení grafu: eulerovské a hamiltonovské grafy, problém obchodního cestujícího.
  • Párování: bipartitní párování, Tutteho věta.
  • Stromy: charakterizace stromů, střed stromu, počet stromů, minimální kostry.
  • Obarvování hran: bipartitní grafy, Vizingova věta, Ramseyho věta.
  • Obarvování vrcholů: Brooksova věta, chromatický polynom.
  • Rovinné grafy: Eulerův vztah, platónská tělesa, Kuratowského věta, Fáryho věta, duální graf, maximální počet hran, věta o čtyřech barvách, rod grafu.
  • Minory: věta Robertsona a Seymoura.
  • Orientace grafů: Robbinsova věta, turnaje.
Literatura
  • NEŠETŘIL, Jaroslav. Kombinatorika. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1983, 173 s. URL 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
  • KUČERA, Luděk. Kombinatorické algoritmy. 2., nezměn. vyd. Praha: SNTL - Nakladatelství technické literatury, 1989, 286 s. info
  • Introduction to graph theory. Edited by Robin J. Wilson. 4th ed. Harlow: Prentice Hall, 1996, viii, 171. ISBN 0582249937. info
  • DIESTEL, Reinhard. Graph theory. 3rd ed. Berlin: Springer, 2006, xvi, 410s. ISBN 3540261834. info
Výukové metody
Přednášky a cvičení.
Metody hodnocení
Zkouška písemná (požadováno alespoň 50% bodů) a ústní.
Informace učitele
Zkouška je písemná a ústní. K dosažení hodnocení "vyhovující" (E) je nutné získat z písemné části zkoušky alespoň polovinu možných bodů. Pro získání lepšího hodnocení je třeba navíc absolvovat ústní část, přičemž hodnocení zkoušky je potom dáno výsledky u obou jejích částí. Požadavkem pro připuštění ke zkoušce je účast na cvičeních; jsou povoleny tři neomluvené absence.
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 2009, podzim 2010, podzim 2011, podzim 2011 - akreditace, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.