M5140 Teorie grafů

Přírodovědecká fakulta
podzim 2011 - akreditace

Údaje z období podzim 2011 - akreditace se nezveřejňují

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
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í
Písemná a ústní zkouška.
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
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
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 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.