Шаг 3.
Матроиды. "Жадные" алгоритмы.
Основные понятия теории матроидов

    На этом шаге мы рассмотрим основные понятия теории матроидов.

    Примем сначала важное соглашение: всюду в дальнейшем мы будем рассматривать только конечные матроиды.

    Таким образом, матроид М(Е) для нас - это конечное непустое множество Е вместе с отображением А → 〈А〉 множества ℜ(E) в себя, удовлетворяющее аксиомам:

1. (направленность) А ⊆ 〈А〉 для любого А ⊆ Е;
2. (монотонность) для любых A, B ⊆ Е А ⊆ В => 〈А〉 ⊆ 〈B〉;
3. (идемпотентность) 〈〈А〉〉 = 〈А〉 для любого А ⊆ Е;
4. (аксиома замены) для любых р, q ∈ Е и А ⊆ Е q∉〈А〉, q∈〈А∪p〉 => p∈〈А∪q〉.

    Матроид называется простым, если он удовлетворяет следующей дополнительной аксиоме:

1. 〈∅〉 = ∅ и 〈p〉 = p для любого p ∈ Е.

    Из доказанного ранее вытекает, что решетка Sub E листов (конечного) матроида М(Е) является конечной геометрической решеткой, т.е. она

• конечна;
• точечна (любой её элемент есть объединение конечного числа атомов);
• полумодулярна.

    Перейдем теперь к рассмотрению основных понятий теории матроидов.

    Пусть М = M(Е) - произвольный матроид. Множество А ⊆ Е называется независимым, если р ∉ 〈А\p〉 для любого p ∈ А (в противном случае множество А называется зависимым). Через Ind (M) или просто Ind будем обозначать множество всех независимых подмножеств из Е. Отметим, что ∅ ∈ Ind.

Лемма 1.

1. Любое подмножество независимого множества независимо.
2. Пусть А - независимо и p ∈ Е\А. Тогда множество А∪p независимо в том и только в том случае, когда p ∈ 〈А〉.

Доказательство.

Утверждение 1) очевидно.

    2) Необходимость условия следует из определения. Обратно, пусть p ∉ 〈А〉. Возьмем q ∈ А. Если q ∈ 〈(A\q)∪p)〉, то на основании аксиомы замены и условия q ∉ (А\q) получаем p ∈ 〈(А\q)∪q〉 = 〈А〉. Таким образом, q ∉ 〈(А\q)∪p〉 и, очевидно, p ∉ 〈(A∪p)\p〉, т.е. A ∪ p - независимое множество.

    Пусть A- произвольное подмножество из Е. Любое максимальное независимое подмножество В, содержащееся в А, будем называть базой множества А. Базы множества Е будем называть базами матроида М. Через Bs(M) или просто Bs будем обозначать совокупность всех баз матроида М. Минимальные зависимые подмножества из Е будем называть циклами матроида М. Через Сс1(М) или просто Ccl будем обозначать множество всех циклов матроида М.

Лемма 2.

Для любого подмножества А из Е выполняется

1. 〈B〉 = 〈A〉 для любой базы B множества A;
2. если I - независимое множество из A и B - база множества A, то |I| ≤ |B|; в частности, все базы множества A равномощны;
3. любое независимое подмножество, содержащееся в A, может быть расширено до базы множества А.

Доказательство.

1. Пусть B - база множества А. Если p ∈ А\В, то В∪p зависимо и поэтому p ∈ 〈B〉 в силу леммы 1. Следовательно, А ⊆ 〈B〉, т.е. 〈А〉 ⊆ 〈B〉 ⊆ 〈A〉. Откуда вытекает равенство 〈A〉 = 〈B〉.

2. Если I ⊆ B, то, очевидно, |I| ≤ |B|. Пусть p₁ ∈ I\В. Тогда p₁ ∉ 〈I\p₁〉 и множество B∪p₁ зависимо. По лемме 1 имеем р₁ ∈ 〈B〉. Следовательно, В ⊄ (I\p₁). Тогда существует q₁ ∈ B такой, что q₁ ∉ (I\p₁).

       В силу леммы 1 множество I₁ = (I\p₁) ∪ q₁ независимо и |I₁| - |I|, |I₁∩B|>|I∩B|. Продолжая действовать аналогичным образом, мы найдем независимое множество I_t ⊆ В такое, что |I| = |I_t| ≤ |В|.

3. Очевидно.

    Рангом r(А) подмножества А из Е называется общая мощность всех баз из А. Число r=r(М)=r(Е) называется рангом матроида M(Е).

Лемма 3.

Для любого подмножества A из Е выполняется:

1. 0 ≤ r(А) ≤ |А|;
2. r(А) = |А| ⇔ А - независимое множество;
3. r(А) = r(〈А〉) = dim(〈А〉), где dim - функция размерности в решетке Sub Е листов матроида М.

Доказательство.

1) и 2) очевидны.

    3) Пусть В = {b₁, ..., b_k} - база множества А. По лемме 2 имеем 〈B〉 - 〈А〉. Если p ∈ 〈А〉\В, то p ∈ (В) и множество В ∪ p зависимо в силу леммы 1. Следовательно, B - база для 〈A〉 и мы получаем r(А) = r(〈А〉)=k.

    В силу независимости B для любого i = 1, ..., k-1 выполняется

B_i+1 ∉ 〈b₁, ..., b_i〉.

    Тогда, применяя лемму 2 из предыдущего шага, получаем цепочку покрытий

〈∅〉 ⊂ 〈b₁〉 ⊂ 〈b₁,b₂〉 ⊂, ..., ⊂ 〈b₁,b₂, ..., b_k〉 = 〈A〉

т.е. k = dim(〈A〉) в решетке Sub E.

    Пусть A - лист матроида М. Говорят, что множество H ⊆ А является порождающим для листа А, если 〈H〉 = А. Порождающие множества листа Е называются порождающими множествами матроида М.

Лемма 4.

Минимальные порождающие множества листа A и только они являются базами для А.

Доказательство.

    =>. Пусть A = 〈H〉 и В - база для H. Так как r(Н) = r(А), B - база и для А. Тогда (В) = А и, следовательно, H = B в силу минимальности H.

    <=. Пусть B - база для листа А. Тогда А = 〈B〉. Если H ⊂ В и 〈H〉 = А, то r(А) = r(H) < r(В), что противоречиво.

Лемма 5.

Для любого A ⊆ Е и p ∈ Е выполняется

1. р ∈ 〈A〉 ⇔ р ∈ А или существует I ⊆ А такое, что I ∈ Ind и I∪р ∉ Ind;
2. р ∈ 〈A〉 ⇔ р ∈ А или существует С ∈ Ccl такое, что p ∈ С ⊆ A∪p;
3. p ∈ 〈A〉 ⇔ r(A∪p) = r(А).

Доказательство.

    1) Пусть р ∈ 〈A〉\A и B - база для А. В силу леммы 3 имеем r(А) = r(〈A〉), поэтому В - база и для 〈A〉. Следовательно, В∪p ∉ Ind и, кроме того, В ∈ Ind.

    Обратно, пусть I ⊆ A, I ∈ Ind и I∪p ∉ Ind. Множество I∪p зависимо, поэтому в силу леммы 1 имеем р ∉ 〈I〉 ⊆ (А).

    1) и 2) - эквивалентные утверждения. Это легко заметить, если вспомнить определение цикла.

    3) Так как всегда 〈A∪p〉 ⊇ 〈A〉, получаем р ∈ 〈A〉 эквивалентно 〈A∪p〉 = 〈A〉, что, в свою очередь, эквивалентно r(A∪p) = r(А) в силу леммы 3.

    На следующем шаге мы рассматрим различные аксиоматизации матроидов.

Предыдущий шаг Содержание Следующий шаг