Лекция by Данил Сагунов

1. Определение

2. Пример: графический матроид
2.1 И доказательство

3. Новые понятия
3.1 Цикл -- минимальное по включению зависимое множество
3.2 База -- максимальное по включению независимое
3.3 Утв: все базы одного размера
3.4 Ранг матроида, ранг множества, проекция матроида

#00:31
4. Аксиоматизация базами
4.1 Эквивалентность обычной

5. Примеры
5.1 Универсальный
5.2 Матричный матроид
5.3 Трансверсальный
(пожалуй стоит не только двудольный рассказывать)

6. Алгоритм Радо-Эдмондса
6.1 Как приложение к Краскалу
6.2 Как приложение к паросочетаниям взвешенным слева
6.3 Доказательство алгоритма
6.3.1 лемма про базы
6.3.2 Вспомогательная лемма про макс по весу базу
(хм, если сформулировать второй один способ аксиоматизации базами,
то из этого всё совсем кустарно доказывается)
(способ где сначала добавляем, потом выкидываем)

------- перерыв -------

7. Задача пересечения
7.1 Пересечение не матроид
7.2 А три вообще np-трудно!

8. Граф замен
8.1 в одном матроиде
8.2 в двух матроидах
8.3 Два легко-добавляемых множества
8.4 Общий план -- искать путь между.

9. Теорема Лоулера-Эдмондса
9.1 Лемма. Пути нет -- нашли максимальное пересечение
9.2 вспомогательная минимакс лемма про ранги (|J| <= rk1(U) + rk2(S\U))
9.3 если нет пути, то верно в другую сторону.

10. Расширяемся
10.1 Если есть путь (кратчайший!) то можно по нему расшириться
10.2 доказательство....