{{Předmět|Kombinatorika a grafy I|Jan Kratochvíl|DMI011}}

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é

Category:Matematika%20pro%20informatiky