Матроид

Матроид — пара (X,I), где X — конечное множество, называемое носителем матроида, а I — некоторое подмножество множества всех подмножеств X, называемое семейством независимых множеств, то есть I⊂2X. При этом должны выполняться следующие условия:

  1. ∅∈I
  2. Если A∈I и B⊂A, то B∈I
  3. Если A,B∈I и мощность A больше мощности B, то существует x∈A\B

такой, что B∪{x}∈I

Базами матроида называются максимальные по включению независимые множества.

Содержание

Примеры

  1. Универсальный матроид Un k. Множество X имеет мощность n, независимыми множествами являются подмножества мощностью не больше k. Базы — подмножества мощностью k.
  2. Графический матроид. Множество 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} содержит ровно один цикл.

Применение

Матроиды хорошо описывают класс задач, допускающих «жадное» решение. См. жадный алгоритм Радо — Эдмондса

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home