Теория матроидов:Тикеты

1 Основные факты теории матроидов

1. Определение матроида
2. Примеры матроидов
3. Прямая сумма матроидов
4. Теорема Радо-Эдмондса (жадный алгоритм)
5. Теорема о базах
6. Аксиоматизация матроида базами
7. Теорема о циклах
8. Аксиоматизация матроида циклами
9. Ранговая функция, полумодулярность
10. Аксиоматизация матроида рангами
11. Двойственный матроид
12. Оператор замыкания для матроидов
13. Покрытия, закрытые множества
14. Матроид Вамоса[math]^\star[/math]

2 Пересечение матроидов

1. Пересечение матроидов, определение, примеры
2. Граф замен
3. Алгоритм построения базы в пересечении матроидов

3 Объединение матроидов

1. Объединение матроидов, проверка множества на независимость
2. Объединение матроидов, доказательство того, что объединение является матроидом
3. Алгоритм построения базы в объединении матроидов