MA010 Teorie grafů

Fakulta informatiky
podzim 2007
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í)
Mgr. et Mgr. Pavlína Moravcová Vařeková (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Fakulta informatiky
Kontaktní osoba: prof. RNDr. Petr Hliněný, Ph.D.
Rozvrh
St 10:00–11:50 D1
  • Rozvrh seminárních/paralelních skupin:
MA010/01: každý lichý čtvrtek 12:00–13:50 C511, P. Moravcová Vařeková
MA010/02: každý sudý čtvrtek 12:00–13:50 C511, P. Moravcová Vařeková
MA010/03: každý lichý čtvrtek 14:00–15:50 C511, P. Moravcová Vařeková
MA010/04: každý sudý čtvrtek 14:00–15:50 C511, P. Moravcová Vařeková
MA010/05: každou lichou středu 18:00–19:50 B011, J. Bouda
MA010/06: každou sudou středu 18:00–19:50 B011, J. Bouda
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 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
Metody hodnocení
Výuka probíhá formou přednášky 2h a cvičení 2h co dva týdny. Účast na cvičeních se bude zaznamenávat, ale neovlivní přímo vaše hodnocení. (Jenom pokud byste žádali o dodatečné konzultace či výjimky, k účasti se patřičně přihlédne.)
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. Zkouška bude písemná, skládá se z aplikačně zaměřených základů a z teoretické důkazové části. Samotné zkoušce předcházejí povinné semestrální testy a volotelný domácí referát; ze semestru bude požadován minimální bodový zisk (asi 10% z 30% celkového.)
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 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.