Теория матроидов

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

• Определение матроида
• Примеры матроидов
• Прямая сумма матроидов
• Теорема Радо-Эдмондса (жадный алгоритм)
• Теорема о базах
• Аксиоматизация матроида базами
• Теорема о циклах
• Аксиоматизация матроида циклами
• Ранговая функция, полумодулярность
• Аксиоматизация матроида рангами
• Двойственный матроид
• Оператор замыкания для матроидов
• Покрытия, закрытые множества
• Матроид Вамоса[math]^\star[/math]

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

• Пересечение матроидов, определение, примеры
• Граф замен
• Алгоритм построения базы в пересечении матроидов
• Многогранник пересечения матроидов*

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

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