|
Vyučující
|
-
Kuřil Martin, RNDr. Ph.D.
-
Přibyl Jiří, PhDr. Ph.D.
-
Lacková Veronika, RNDr. Ph.D.
|
|
Obsah předmětu
|
1. - 2. Pojem grafu (graf, základní třídy grafů, stupeň vrcholu, podgrafy, isomorfismus grafů, implementace grafů). 3. - 4. Souvislost grafů (souvislost grafu, komponenty grafu, prohledávání grafu, vyšší stupně souvislosti). 5. Eulerovské grafy (kreslení jedním tahem, hamiltonovské grafy). 6. - 7. Vzdálenost a metrika v grafu (vzdálenost v grafu, určení vzdáleností neboli výpočet metriky, vzdálenost v ohodnocených grafech, nejkratší cesta v ohodnoceném grafu). 8. Stromy (základní vlastnosti stromů, kostra grafu). 9. - 11. Barevnost a kreslení grafů (barevnost grafů, rovinné nakreslení grafů, rozpoznávání rovinných grafů, barvení map a rovinných grafů). 12. - 14. Toky v sítích (definice sítě, hledání největšího toku, zobecnění sítí, další aplikace algoritmu pro hledání největšího toku - párování v bipartitním grafu a Hallova věta).
|
|
Studijní aktivity a metody výuky
|
|
Přednášení
|
|
Výstupy z učení
|
1. - 2. Pojem grafu (graf, základní třídy grafů, stupeň vrcholu, podgrafy, isomorfismus grafů, implementace grafů). 3. - 4. Souvislost grafů (souvislost grafu, komponenty grafu, prohledávání grafu, vyšší stupně souvislosti). 5. Eulerovské grafy (kreslení jedním tahem, hamiltonovské grafy). 6. - 7. Vzdálenost a metrika v grafu (vzdálenost v grafu, určení vzdáleností neboli výpočet metriky, vzdálenost v ohodnocených grafech, nejkratší cesta v ohodnoceném grafu). 8. Stromy (základní vlastnosti stromů, kostra grafu). 9. - 11. Barevnost a kreslení grafů (barevnost grafů, rovinné nakreslení grafů, rozpoznávání rovinných grafů, barvení map a rovinných grafů). 12. - 14. Toky v sítích (definice sítě, hledání největšího toku, zobecnění sítí, další aplikace algoritmu pro hledání největšího toku - párování v bipartitním grafu a Hallova věta).
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
Známkou, Písemná zkouška
Zápočet - V průběhu semestru se budou psát dvě zápočtové písemné práce. První zápočtová písemná práce se píše v průběhu výukové části semestru a bude týden dopředu oznámena. Druhá zápočtová písemná práce se píše v prvním týdnu zkouškového období. - Za první zápočtovou písemnou práci je možné získat 0-100 bodů. Počet získaných bodů je označen zp1. - Za druhou zápočtovou písemnou práci je možné získat 0-100 bodů. Počet získaných bodů je označen zp2. - Dále je možné získat body za řešení problémových úloh, přičemž rozsah bodů problémové úlohy je stanoven na základě obtížnosti úlohy. Body za vyřešení problémové úlohy získává pouze první student, který své správné řešení prezentoval. Počet všech bodů získaných za problémové úlohy je označen pu. - Zápočet bude udělen pokud pu + zp1 + zp2 > 119. - Pokud student nesplní podmínky pro získání zápočtu, má možnost psát opravnou zápočtovou písemnou práci, přičemž má nárok na dva pokusy. Za opravnou zápočtovou písemnou práci je možné získat 0-200 bodů. Počet získaných bodů je označen ozp. - Zápočet bude udělen pokud pu + ozp > 119. Zkouška - Zkouška je písemná. - Zkouška je obvykle monotematická, přičemž téma zkoušky není dopředu známo. - Obvykle bývá 5-7 termínů, přičemž alespoň jeden je vždy ve druhé části zkouškového období.
|
|
Doporučená literatura
|
-
Demel, J. Grafy a jejich aplikace. Praha: Academia, 2002. ISBN 80-200-0990-6.
-
Hliněný, P. Základy teorie grafů pro (nejen) informatiky.
-
Matoušek, J. & Nešetřil, J. Kapitoly z diskrétní matematiky. Praha: Karolinum, 2009. ISBN 978-80-246-1740-4.
|