MA010 Teorie grafů

Fakulta informatiky
podzim 2008
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í)
doc. RNDr. Jan Bouda, Ph.D. (cvičící)
RNDr. Robert Ganian (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Fakulta informatiky
Kontaktní osoba: prof. RNDr. Petr Hliněný, Ph.D.
Rozvrh
Čt 17:00–18:50 D1
  • Rozvrh seminárních/paralelních skupin:
MA010/01: každou sudou středu 8:00–9:50 B410, J. Bouda
MA010/02: každou lichou středu 8:00–9:50 B410, J. Bouda
MA010/03: každý sudý čtvrtek 14:00–15:50 B011, P. Hliněný
MA010/04: každý lichý čtvrtek 14:00–15:50 B011, R. Ganian
MA010/05: každý sudý pátek 8:00–9:50 B003, R. Ganian
MA010/06: každý lichý pátek 8:00–9:50 B003, R. Ganian
Předpoklady
! PřF:M5140 Teorie grafů &&! NOW ( PřF:M5140 Teorie grafů )
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 180 stud.
Momentální stav registrace a zápisu: zapsáno: 0/180, pouze zareg.: 0/180, pouze zareg. s předností (mateřské obory): 0/180
Mateřské obory/plány
předmět má 21 mateřských oborů, zobrazit
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 pro 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).
Úspěšný student by měl porozumnět problematice grafů v matematice a umět grafy používat v aplikacích, především těch informatických. Taktéž by se měl naučit dokazovat tvrzení o grafech a řešit nové grafové úlohy, ne které v aplikacích narazí.
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
  • MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Invitation to discrete mathematics. Oxford: Clarendon Press, 1998. xv, 410. ISBN 0198502087. info
Metody hodnocení
Výuka probíhá formou přednášky 2h a cvičení 2h co dva týdny. Účast na cvičeních bude v roce 2008 povinná, pro další léta se uvidí.
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 a shrnutém v učebním textu (přičemž závěrečné pokročilé lekce jsou volitelné). Pozor, jedná se o matematický předmět, takže k teorii se požadují i důkazy!
Bodové hodnocení (2008-): Bude jeden semestrální školní test za až 20 bodů, s možností opravy. Nepovinné řešení těžkého bonusového domácího úkolu, s libovolným nezáporným možným počtem bonusových bodů (nenárokové!). V součtu za semestr musíte získat aspoň 10 bodů ke zkoušce. Zkouška pak bude písemná, skládat se bude z aplikačně zaměřených základů (40 bodů) a z teoretické důkazové části (40 bodů). U zkoušky uspěje, kdo v celkovém součtu bude mít více než 50 bodů.
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! Skripta a slidy vyučujícího: Teorie grafů, "http://www.fi.muni.cz/~hlineny/Vyuka/GT/".
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 2006, podzim 2007, 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.