Теория матроидов — различия между версиями
Shersh (обсуждение | вклад) (Новая страница: «== Основные факты теории матроидов == * Определение матроида * Примеры матроидов * [[Пря...») |
Ivan (обсуждение | вклад) (→Пересечение матроидов) |
||
| Строка 19: | Строка 19: | ||
* [[Граф замен]] | * [[Граф замен]] | ||
* [[Алгоритм построения базы в пересечении матроидов]] | * [[Алгоритм построения базы в пересечении матроидов]] | ||
| + | * [[Многогранник пересечения матроидов]]* | ||
== Объединение матроидов == | == Объединение матроидов == | ||
Версия 21:15, 29 апреля 2017
Основные факты теории матроидов
- Определение матроида
- Примеры матроидов
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- Теорема о базах
- Аксиоматизация матроида базами
- Теорема о циклах
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- Аксиоматизация матроида рангами
- Двойственный матроид
- Оператор замыкания для матроидов
- Покрытия, закрытые множества
- Матроид Вамоса
Пересечение матроидов
- Пересечение матроидов, определение, примеры
- Граф замен
- Алгоритм построения базы в пересечении матроидов
- Многогранник пересечения матроидов*
