Kombinatorika a grafy I

Z ωικι.matfyz.cz
Verze z 19. 2. 2011, 09:52, kterou vytvořil 77.104.246.171 (diskuse)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
Kombinatorika a grafy I
Kód předmětu: NDMI011
Přednáší: Jan Kratochvíl

Anotace[editovat | editovat zdroj]

Základní kurs oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.

Sylabus[editovat | editovat zdroj]

  • Prostor cyklu v grafu.
  • Hallova věta o systémech různých reprezentantů, maximální párování v bipartitních grafech. Birkhoffova věta o bistochastických maticích.
  • Faktory v grafech, Tuttova věta o 1-faktoru.
  • Maximální párování v obecných grafech.
  • Toky v sítích. Souvislost grafu, Mengerova a Ford-Fulkersonova věta.
  • Vytváření 3-souvislých grafů, důkaz Kuratowského věty.

Odkazy[editovat | editovat zdroj]

Viz také[editovat | editovat zdroj]