Sylabus
Hlavní témata:
§ Definice základních pojmů (obecné grafy a speciální případy: úplný graf, kružnice, cesta, strom, bipartitní graf). Skóre grafu.
§ Souvislost grafu, vzdálenost v grafu, uzavřené tahy, Hamiltonova kružnice, Eulerovy grafy.
§ Reprezentace grafu: matice sousednosti, matice incidence.
§ Nezávislost grafu, teorie kódování.
§ Kreslení grafů, rovinné grafy a mapy, barvení grafu.
Anotace
Cílem semináře seznámit studenty se základyními pojmy a metodami teorie grafů. Základními probíranými pojmy budou pojem grafu, isomorfismus grafů, různé způsoby zadávání grafů, stromy, úplné grafy, kostra grafu, rovinné grafy, pojem cesty, Eulerovské grafy, pojem kružnice, Hamiltonovské grafy, barvení grafů, algoritmy na grafech. Doporučená literatura je: Bosák: Grafy a ich aplikácie (Alfa, Bratislava 1980), Sedláček: Úvod do teorie grafů (Academia, Praha 1981), Fuchs: Diskrétní matematika pro učitele (MU Brno, 2001) a Matoušek a Nešetřil: Kapitoly z diskrétní matematiky (UK Praha, 2003).