|
Vyučující
|
|
|
|
Obsah předmětu
|
1. Základné pojmy teórie grafov (grafy a podgrafy, sledy, ťahy, cesty, súvislosť, špeciálne triedy grafov, stupeň vrchola, postupnosti stupňov v grafoch). 2. Stromy (charakterizácia stromov, kostra grafu a problém minimálnej kostry). 3. Vrcholová a hranová súvislosť v grafoch (miera súvislosti grafu, mosty, artikulácie a 2-súvislé grafy, Mengerove vety). 4. Eulerovké a Hamiltonovské grafy (Eulerovské grafy a ich charakterizácia, vybrané výsledky týkajúce sa Hamiltonovských grafov). 5. Farbenia grafov (vrcholové a hranové farbenie grafu, ohraničenia pre chromatické čísla grafu). 6. Planárne grafy (Eulerov vzorec a jeho dôsledky, Platónske telesá, charakterizácia planárnych grafov, farbenie planárnych grafov). 7. Vnorenie grafov na dvojrozmerné plochy (rod plochy, príklady vnorení grafov na plochy rozličných rodov).
|
|
Studijní aktivity a metody výuky
|
|
Monologická (výklad, přednáška, instruktáž)
|
|
Výstupy z učení
|
Oboznámenie sa so základnými pojmami a technikami používanými v rámci teórie grafov
1. Znalosti Študenti definujú základné pojmy teórie grafov, vyšetrujú ich vlastnosti a vzťahy medzi nimi.
|
|
Předpoklady
|
Predpokladá sa elementárna znalosť týkajúca sa konečných množín.
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška, Písemná zkouška
Študent musí byť schopný porozumieť základným pojmom a byť schopný vyriešiť praktické úlohy.
|
|
Doporučená literatura
|
-
A.Bodny,R.M.Murty. (2008). Graph Theory. Springer London.
-
Chajda I. (2000). Vybrané kapitoly z algebry. PřF UP Olomouc.
-
J. Matoušek, J. Nešetřil. (2002). Kapitoly z diskrétní matematiky. Karolinum.
-
J.Demel. (2002). Grafy a jejich apliakce. Academia.
-
Korte B., Vygen J. (2018). Combinatorial Optimization (Theory and Algorithms). Springer.
-
R. Disestel. (2017). Graph Theory. Springer-Verlag Berlin Heidelberg.
|