| Název předmětu | Teorie grafů |
|---|---|
| Kód předmětu | KMA/K215 |
| Organizační forma výuky | Přednáška + Cvičení |
| Úroveň předmětu | Bakalářský |
| Rok studia | 1 |
| Semestr | Letní |
| Počet ECTS kreditů | 5 |
| Vyučovací jazyk | Čeština |
| Statut předmětu | Povinný |
| Způsob výuky | Kontaktní |
| Studijní praxe | Nejedná se o pracovní stáž |
| Doporučené volitelné součásti programu | Není |
| Vyučující |
|---|
|
| Obsah předmětu |
|
1) Pojem grafu (graf, základní třídy grafů, stupeň vrcholu, podgrafy, isomorfismus grafů, implementace grafů). 2) Souvislost grafů (souvislost grafu, komponenty grafu, prohledávání grafu, vyšší stupně souvislosti). 3) Eulerovské grafy (kreslení jedním tahem, hamiltonovské grafy). 4) 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). 5) Stromy (základní vlastnosti stromů, kostra grafu). 6) Barevnost a kreslení grafů (barevnost grafů, rovinné nakreslení grafů, rozpoznávání rovinných grafů, barvení map a rovinných grafů). 7) 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 |
| nespecifikováno |
| Výstupy z učení |
| Předpoklady |
|
nespecifikováno
|
| Hodnoticí metody a kritéria |
|
nespecifikováno
Zápočet bude udělen za A) získání alespoň 51 bodů, přičemž body je možné získat následovně: 1) 0-80 bodů je možné získat ze zápočtové písemné práce 2) 0-12 bodů je možné získat z domácích úkolů 3) 0-8 bodů je možné získat za docházku V případě, že získáte 0-50 bodů máte možnost psát opravnou zápočtovou písemnou práci, přičemž jsou dva pokusy. B) napsání opravné zápočtové písemné práce na alespoň dvě třetiny bodů. Zkouška má dvě části - písemnou a ústní, přičemž k ústní části se přistoupí v nerozhodném případě. |
| Doporučená literatura |
|
| Studijní plány, ve kterých se předmět nachází |
| Fakulta | Studijní plán (Verze) | Kategorie studijního oboru/specializace | Doporučený semestr | |
|---|---|---|---|---|
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Informační systémy (A14) | Kategorie: Informatické obory | 1 | Doporučený ročník:1, Doporučený semestr: Letní |
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Matematika (dvouoborové) (A14) | Kategorie: Matematické obory | 1 | Doporučený ročník:1, Doporučený semestr: Letní |
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Matematika (dvouoborové) (A14) | Kategorie: Matematické obory | 1 | Doporučený ročník:1, Doporučený semestr: Letní |