Kombinatorika a grafy I

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Kombinatorika a grafy I
Kód předmětu: NDMI011
Přednáší: Jan Kratochvíl

Anotace

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

  • 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

Viz také