Матроид
Материал из Википедии — свободной энциклопедии
Матроид — пара (X,I), где X — конечное множество, называемое носителем матроида, а I — некоторое подмножество множества всех подмножеств X, называемое семейством независимых множеств, то есть I⊂2X. При этом должны выполняться следующие условия:
- ∅∈I
- Если A∈I и B⊂A, то B∈I
- Если A,B∈I и мощность A больше мощности B, то существует x∈A\B
такой, что B∪{x}∈I
Базами матроида называются максимальные по включению независимые множества.
Содержание |
[править] Примеры
- Универсальный матроид Un k. Множество X имеет мощность n, независимыми множествами являются подмножества мощностью не больше k. Базы — подмножества мощностью k.
- Графический матроид. Множество X — множество ребер графа, независимые множества — ациклические подмножества этих ребер. Базами являются остовные леса графа.
[править] Дополнительные понятия
- Двойственным данному матроиду называется матроид, носитель которого совпадает с носителем данного матроида, а базы — дополнения баз данного матроида до носителя. То есть X*=X, а множество баз двойственного
матроида — это множество таких B*, что B*=X\B, где B — база данного матроида.
- Циклом в матроиде называется такое множество A⊂X, что A∉I, и для любого B⊂A, если B≠A, B∈I
- Рангом матроида называется мощность его баз.
[править] Теоремы
- Все базы матроида имеют одинаковую мощность.
- Матроид однозначно задается носителем и базами.
- Цикл не может быть подмножеством другого цикла
- Если C1 и C2 — циклы, то для любого x∈C1∪C2 C1∪C2\{x} содержит цикл
- Если B — база и x∉B, то B∪{x} содержит ровно один цикл.
[править] Применение
Матроиды хорошо описывают класс задач, допускающих «жадное» решение. См. жадный алгоритм Радо — Эдмондса
 |
У этой статьи нет ссылок на другие языковые разделы. Вы можете помочь проекту, найдя и добавив их в статью. |
