| Název předmětu | Diskrétní matematika 2 |
|---|---|
| Kód předmětu | KAG/DM2 |
| Organizační forma výuky | Přednáška + Cvičení |
| Úroveň předmětu | Bakalářský |
| Rok studia | nespecifikován |
| 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. Úvodné pojmy teórie grafov: pojem grafu, podgrafy, významné triedy grafov, sledy, ťahy a cesty, súvislosť, postupnosti stupňov v grafoch. 2. Stromy: charakterizácia stromov, kostra grafu a problém minimálnej kostry. 3. Eulerovké a Hamiltonovské grafy: Eulerovské grafy a ich charakterizácia, postačujúce podmienky pre Hamiltonovské grafy. 4. Farbenia grafov: vrcholové farbenie, hranové farbenie, zovšeobecnené farbenia, známe odhady pre chromatické invarianty grafov. 5. Planárne grafy: Eulerov vzorec a jeho dôsledky, Platónske telesá, charakterizácia planárnych grafov, vrcholové farbenie planárnych grafov. 6. Orientované grafy: orientované sledy, ťahy, cesty a kružnice, silná, unilaterálna a slabá súvislosť, turnaje, acyklické orientované grafy. 7. Problém najkratšej cesty v orientovaných grafoch: Dijkstrov algoritmus. 8. Vybrané problémy teórie grafov: spárenia v bipartitných grafoch, extremálna kombinatorika, Ramseyho čísla a ich odhady.
|
| Studijní aktivity a metody výuky |
| Monologická (výklad, přednáška, instruktáž) |
| Výstupy z učení |
|
Oboznámiť sa so základnými pojmami, tvrdeniami a aplikáciami v teórii grafov.
1. Znalosti: Získanie základných vedomostí v teórií grafov. |
| Předpoklady |
|
Predpokladá sa elementárna znalosť týkajúca sa konečných množín.
|
| Hodnoticí metody a kritéria |
|
Ústní zkouška
Zápočet: aktívne preukázanie znalostí. Skúška: porozumenie predmetu, dôkazy hlavných tvrdení. |
| 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): Matematika (2020) | Kategorie: Matematické obory | 1 | Doporučený ročník:1, Doporučený semestr: Letní |