Теория матроидов — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
Строка 1: | Строка 1: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Основные факты теории матроидов == | == Основные факты теории матроидов == | ||
* [[Определение матроида]] | * [[Определение матроида]] |
Текущая версия на 19:29, 4 сентября 2022
Основные факты теории матроидов
- Определение матроида
- Примеры матроидов
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- Теорема о базах
- Аксиоматизация матроида базами
- Теорема о циклах
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- Аксиоматизация матроида рангами
- Двойственный матроид
- Оператор замыкания для матроидов
- Покрытия, закрытые множества
- Матроид Вамоса
Пересечение матроидов
- Пересечение матроидов, определение, примеры
- Граф замен
- Алгоритм построения базы в пересечении матроидов
- Многогранник пересечения матроидов*