Předmět Teorie grafů (TGR)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu TGR - Teorie grafů, Mendelova univerzita v Brně (MENDELU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
1.Motivace, historie a základní terminologie (dotace 6/2) a.Vybrané úlohy teorie grafů. Vznik teorie grafůb.Definice grafu, vlastnosti grafu. Úplný graf, bipartitní graf, rovinný grafc.Opakování z TZI2.Implementace grafu (dotace 2/2) a.Statická implementace -- matice sousednosti, matice incidence.b.Dynamická implementace -- výčet sousedů, dynamická reprezentace grafu3.Stromy a kostry (dotace 4/2) a.Charakterizace, vlastnosti a využití stromů.b.Kořenové stromy, uspořádané kořenové stromy. Aplikace stromůc.Kostra grafu. Aplikace koster, hledání minimální kostry4.Prohledávání grafu a jeho aplikace (dotace 2/2) a.Prohledávání do šířky. Distanční rozklad množiny uzlů.b.Prohledávání do hloubky. Pre-order, in-order, post-order.5.Hledání optimálních sledů (dotace 4/2) a.Moorův algoritmus, Dijkstrův algoritmus, Fordův algoritmusb.Metoda kritické cesty, cesty s největší propustnostíc.Praktické aplikace optimálních sledů6.Toky v sítích a jejich aplikace (dotace 2/2) a.Definice sítě, definice toku. Věta o maximálním toku a minimálním řezub.Fordův-Fulkersonův algoritmus. Aplikace sítí a toků v technologické praxi7.Úlohy řešené pomocí grafů (dotace 4/0) a.Graf řízení programu, přechodový diagram a jejich použitíb.Rovinné grafy, obarvení grafu. Párování v bipartitních grafech
Získané způsobilosti
Všeobecné kompetence: -dovednosti spojené s využíváním a zpracováním informací-kapacita k učení se-schopnost analýzy a syntézy-schopnost aplikace znalosti v praxi-schopnost komunikovat s experty v jiném oboru-schopnost řešit problémy-schopnost samostatné práce-základní profesní znalosti-základní všeobecné znalosti-základní výpočetní dovednostiOborově specifické kompetence: -Schopnost implementace a kritického hodnocení grafových algoritmů-Schopnost řešit reálné problémy formálním aparátem teorie grafů-Využití znalostí grafových algoritmů při tvorbě programových modulů -Znalost algoritmů pro řešení grafových problémů-Znalost terminologie teorie grafů
Literatura
TypAutorNázevMísto vydáníNakladatelRokISBNZFOLTÝNEK, T. -- DANNHOFEROVÁ, J.Teorie grafůBrnoMendelova univerzita v Brně2011978-80-7375-500-3ZŽAMBOCHOVÁ, M.Teorie grafů v příkladechÚstí nad LabemFakulta sociálně ekonomická UJEP2007978-80-7044-962-2ZGROSS, J L. -- YELLEN, J.Handbook of graph theoryBoca RatonCRC Press20041-58488-090-2DDEMEL, J.Grafy a jejich aplikacePrahaAcademia200280-200-0990-6DFUCHS, E.Kombinatorika a teorie grafůPrahaSPN1986DGROSS, J L. -- YELLEN, J.Graph theory and its applicationsBoca RatonChapman & Hall/CRC20061-58488-505-XDPLESNÍK, J.Grafové algoritmyBratislavaVEDA1993
Požadavky
Celkové hodnocení se skládá z hodnocení domácích úkolů (5 x 10 b. = 50 b.) a z bodů získaných v závěrečném testu (50 b.).Hodnotící stupnice: A85, B77, C70, D62, E55.
Garant
prof. RNDr. Ing. Jiří Šťastný, CSc.
Vyučující
Ing. Jan Kolomazník, Ph.D.Ing. Vít Ondroušek, Ph.D.prof. RNDr. Ing. Jiří Šťastný, CSc.