Předmět Teorie grafů (UI / N1004)

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 UI / N1004 - Teorie grafů, Filozoficko-přírodovědecká fakulta, Slezská univerzita v Opavě (SU).

Materiál	Typ	Datum	Počet stažení

Obsah

1. Grafy a jednoduché grafy, stupeň vrcholu.2. Podgrafy, reprezentace grafů pomocí matic, cesty, cykly, dosažitelnost, souvislost, souvislé, nesouvislé grafy, vzdálenost v grafu, excentricita vrcholu, průměr a poloměr grafu.3. Stromy, třídy grafů.4. Další třídy grafů - kompletní grafy, bipartitní a multi-partitní grafy, izomorfismus, automorfismus. Vrcholová a hranová souvislost, bloky.5. Párování, pokrytí, hranové barvení grafů, párování a pokrytí v bipartitních grafech, algoritmus hledající nesaturované alternující cesty.6. Vrcholové barvení grafů, planární grafy.7. Problém 4 barev, Neplanární grafy, Eulerovské grafy, Úlohy typu bludiště - Tarryho algoritmus, Trémauxův algoritmus.8. Hamiltonovské grafy, orientované grafy.9. Orientované grafy, turnaje, sítě, toky a řezy.10. Algoritmus nalezení minimální kostry grafu, Primův algoritmus, Kruskalův, Obecné schéma prohledávání grafu - značkování vrcholů.11. Prohledávání grafů do šířky, do hloubky, Backtracking.

Získané způsobilosti

Teoretické porozumění tématům obsahového vymezení předmětu. Praktické dovednosti při práci s jednotlivými tématy.

Literatura

Demel, J. Grafy. Praha, SNTL, 1988. Kolář, J. Grafy. Praha, ČVUT, 1984. Kolář, J. Grafy - cvičení. Praha, ČVUT, 1984. Bosák, J. Grafy a ich aplikácie. Bratislava, Alfa, 1980. Diestel, R. Graph Theory. New York, Springer, 1997. Bondy, J. A. Graph Theory with Applications. The Macmillan Press, 1976. Behzad, M., Chartrand, G. Graphs and Digraphs. Weber, Schmidt, 1979. Bollobas, B. Modern Graph Theory. New York, Springer, 1998. Fronček, D. Úvod do teorie grafů. Opava, FPF SU, 2000.

Požadavky

Student prezenčního studia píše v rámci cvičení dva zápočtové testy bodované maximálně 20 body za každý. K získání zápočtu je zapotřebí 20 bodů. V rámci semestru mohou studenti získat prémiové body.Zkouška se skládá ze dvou částí. První část: jednoduchý test obsahující 10 otázek. K úspěšnému zvládnutí testu je potřeba alespoň 7-krát zodpovědět správně. Pouze studenti úspěšní v tomto testu mohou obdržet zadání druhé části. Druhá část se skládá z pěti otázek, každá je bodována maximálně 10 body. K počtu bodů získaných ve druhé části se studentovi připočítává 10 bodů z části první. Celkem je tedy ze zkouškové písemky možno získat 60 bodů. Pro úspěšné vykonání je potřeba získat 30 bodů. Známka je stanovena součtem bodů za zkoušku a bodů, které student získal v rámci semestru.HodnoceníPrezenční studium Kombinované studiumA 100 - 91 60 - 55B 90 - 81 54 - 49C 80 - 71 48 - 43D 70 - 61 42 - 37E 60 - 50 36 - 30F 49 - 0 29 - 0

Garant

RNDr. Luděk CIENCIALA, Ph.D.

Vyučující

RNDr. Luděk CIENCIALA, Ph.D.RNDr. Luděk CIENCIALA, Ph.D.Mgr. Jan DrastikMgr. Martina FOLDYNOVÁMgr. Adam KOŽANÝMgr. Marek MENŠÍK, Ph.D.Mgr. Michal PERDEK