MA010 Teorie grafů

Fakulta informatiky
podzim 2006
Rozsah
2/1. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
Mgr. et Mgr. Pavlína Moravcová Vařeková (cvičící)
doc. Mgr. Jan Obdržálek, PhD. (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Fakulta informatiky
Kontaktní osoba: prof. RNDr. Petr Hliněný, Ph.D.
Rozvrh
St 18:00–19:50 D3
  • Rozvrh seminárních/paralelních skupin:
MA010/01: každý sudý čtvrtek 16:00–17:50 C511, P. Moravcová Vařeková
MA010/02: každý lichý čtvrtek 16:00–17:50 C511, P. Moravcová Vařeková
MA010/03: každý sudý čtvrtek 18:00–19:50 C511, P. Moravcová Vařeková
MA010/04: každý lichý čtvrtek 18:00–19:50 C511, P. Moravcová Vařeková
MA010/05: každý sudý čtvrtek 14:00–15:50 C511, J. Obdržálek
MA010/06: každý lichý čtvrtek 14:00–15:50 C511, J. Obdržálek
Předpoklady
! M010 Kombinatorika a grafy
Základy matematiky, množiny, relace, indukce. (Zhruba na úrovni matematických pasáží povinného předmětu IB000.)
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 150 stud.
Momentální stav registrace a zápisu: zapsáno: 0/150, pouze zareg.: 0/150, pouze zareg. s předností (mateřské obory): 0/150
Mateřské obory/plány
Cíle předmětu
Tento kurs je úvodem do teorie grafů s důrazem na aplikace. Uvádí základní pojmy a jejich vlastnosti, formulace jednoduchých grafových úloh a základní efektivní algoritmy jejich řešení.
Třebaže grafy jsou jen jednou z mnoha struktur v diskrétní matematice, vydobyly si svou užitečností a názorností tak důležité místo na slunci, až se dá bez nadsázky říci, že teorie grafů je asi nejvýznamnější součástí soudobé diskrétní matematiky. Znalost teorie grafů se jeví nezbytná ve většině oblastí moderní informatiky, včetně těch aplikovaných. Proto se náš kurz teorie grafů bude ve velké míře zaměřovat právě na jejich informatické aplikace (ale vcelku bez nutnosti informatiku ovládat, tj. naše látka je nez problémů přístupná i ne-informatikům).
Osnova
  • Pojem grafu, jeho souvislost s relacemi. Podgrafy, isomorfizmus, stupně vrcholů, indukované podgrafy. Realizace grafu, orientovaný graf.
  • Souvislost grafu, algoritmy procházení do hloubky a do šířky. Vícenásobná souvislost, hranová souvislost. Mengerova věta. Eulerovské grafy -- kreslení jedním tahem.
  • Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Metrika grafu a její výpočet.
  • Stromy a jejich charakterizace, isomorfizmus stromů. Kořenové stromy. Kostra grafu, (počet koster), problém minimální kostry.
  • Hladový algoritmus. Aplikace na hledání minimální kostry, algoritmy Jarníka a Borůvky. Matroidy.
  • Toky v sítích: definice a modelované problémy. Ford-Fulkersonův algoritmus pro nalezení maximálního toku. Aplikace na párování, souvislost a různé reprezentanty.
  • Barvení grafů, bipartitní grafy, vyšší barevnost. Nezávislost, klika, Hamiltonovská kružnice, vrcholové pokrytí. Relevantní algoritmicky těžké problémy.
  • Rovinné kreslení grafu, Eulerův vztah. Barvení rovinných grafů. Průsečíkové číslo a jeho využití.
  • Vybrané pokročilé partie (dle zájmu a času): Průnikové reprezentace grafů, chordální grafy, stromová šířka, minory, kreslení grafů na plochy a rovinné pokrytí, praktické kreslení grafů - "pružinový" algoritmus, apod.
Literatura
  • Petr Hliněný, Teorie grafů, http://www.fi.muni.cz/~hlineny/Vyuka/GT/Grafy-text07.pdf.
  • MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. Vyd. 2., opr. Praha: Karolinum, 2000, 377 s. ISBN 8024600846. info
  • NEŠETŘIL, Jaroslav a Jiří MATOUŠEK. Invitation to discrete mathematics. Oxford: Clarendon Press, 1998, xv, 410 s. ISBN 0-19-850207-9. info
  • 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
Metody hodnocení
Zkouška je písemná, skládá se z aplikačně zaměřených základů a z teoretické důkazové části.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/~hlineny/Vyuka/TG.html
Studenti jsou povinni číst informace na web stránce učitele předmětu! Požadavkem k úspěšnému vykonání zkoušky je teoretické i praktické zvládnutí látky v rozsahu probraném na přednášce.
Účast na cvičeních se bude zaznamenávat, ale neovlivní vaše hodnocení. Jenom pokud byste žádali o dodatečné konzultace či výjimky, k účasti se patřičně přihlédne.
Semestrální písemka se předpokládá během přednášky (už!) 25.10.
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 2002, podzim 2003, podzim 2004, 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.