ЛКШ 2016. Группа A. День 10. Матроиды: пересечение и объединение.

1. Пересечение матроидов
1. Задача о пересечении матроидов, примеры
2. Граф замен. Алгоритм пересечения матроидов
3. Лемма о единственном паросочетании в графе замен (без доказательства)
4. Лемма о единственности паросочетания, индуцированном кратчайшем путем в графе замен
5. Теоерема Эдмоднса-Лоулера (равенство для рангов)
2. Объединение матроидов
1. Задача об объединении матроидов, примеры
2. Проверка множества на независимость в объединении матроидов: сведение к задаче о пересечении матроидов
3. Объединение матроидов - матроид