ЛКШ 2016. Группа A. День 9. Матроиды: базовые понятия.

1. Базовые понятия теории матроидов
1. Аксиоматизация матроидов с помощью независимых множеств
2. Примеры матроидов: универсальный, разноцветный, графовый, трансверсальный
3. Базы матроидов
2. Основые инструменты теории матроидов
1. Функция ранга. Теорема о полумодулярности ранга
2. Взвешенный матроид. Алгоритм Радо-Эдмондса
3. Прямая сумма матроидов
4. Двойственный матроид
5. Аксиоматизация матроидов с помощью баз