Kombinatorika a grafy I

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

• Skripta Tomáše Vally

Viz také

• Kombinatorika a grafy II (DMI012)