§ 17. Двойственный матроид

Пусть М = (Е, β) — матроид с множеством баз β. Для произвольного XE положим = Е\Х. Если В β, то множество назовем кобазой матроида М. Пусть β* = { : В β}- множество всех кобаз.

Теорема 17.1. Множество β* удовлетворяет акси­омам баз B.1 и В`.2.

> Справедливость условия В.1 очевидна, рассмотрим условие В`.2. Пусть 1 и 2 — две кобазы, х 1\ 2.

Нужно доказать существование в 2\ 1 такого элемента y, что

A=( 1\x) y  β* (1)

Так как хВ1, то согласно следствию 16.7 множество В1 х содержит цикл С. Поскольку цикл не может со­держаться в базе, то существует уС∩ 2. Так как xB2, то у ≠ х. Следовательно, уВ1. Итак, у 2\ 1.

Теперь докажем, что верно (1). С этой целью рас­смотрим множество ={В1x)\y. В силу следствия 16.7 С является единственным циклом, содержащимся в В1 х. Поэтому не содержит циклов и, следовательно, явля­ется независимым множеством. Далее ||= |B1|, так что —база и потому А — кобаза. <

Из предыдущей теоремы вытекает, что пара (Е, β*) является матроидом с множеством баз β*. Этот матроид называется двойственным к матроиду М и обозначается через М*. Очевидно, что М** = М.

Зависимое (независимое) множество элементов мат­роида М* называется козависимым (конезависимым) в М. Цикл матроида М* называется коциклом матроида М. Ранговая функция матроида М* называется коранговой функцией матроида М и обозначается через ρ *. Очевид­но, что ρ *(М)= |Е| - ρ (М).

Поскольку кобазы, коциклы и т. д. являются базами, циклами и т. д. двойственного матроида, то для любого утверждения о циклах, базах и т. д. матроида сущест­вует аналогичное двойственное утверждение о двойствен­ных объектах — коциклах, кобазах и т. д. Если одно из этих утверждений верно для всех матроидов, то верно и двойственное утверждение.

Очевидно, что в терминах кобаз можно следующим образом определить зависимые множества.

Утверждение 17.2. Произвольное подмножество элементов матроида является зависимым тогда и только тогда, когда оно имеет непустое пересечение с каждой кобазой.

Теорема 17.3. Непустое подмножество X элементов матроида является циклом тогда и только тогда, когда оно удовлетворяет следующим двум условиям:

1. |Х ∩ С| ≠ 1 для каждого коцикла С;

2. X — минимальное относительно включения непустое подмножество, удовлетворяющее условию 1).

Доказательство этой теоремы основано на следующих двух леммах.

Лемма 17.4. Для любого непустого независимого подмножества X элементов матроида существует такой коцикл С, что |Х ∩ С| = 1.

> Множество X содержится в некоторой базе В. Пусть xX. В силу следствия 16.7 множество х со­держит некоторый коцикл С. Очевидно, что С ∩ В — {х} = = С∩ X. <

Лемма 17.5. Для всякого цикла X и любого коцик­ла С матроида верно соотношение |Х∩С| ≠ 1.

• Пусть, напротив, Х ∩ С = {х}. Согласно утверждению 17.2 коцикл С — минимальное подмножество в Е, имеющее непустое пересечение с каждой базой. Следо­вательно, — максимальное подмножество в Е, не содер­жащее баз, и потому х содержит некоторую базу . Множество Х\х независимо и содержится в х. Из ак­сиомы I.2 теперь получаем, что существует база D, удов­летворяющая условию Х\х  D  х. Но не содер­жит баз, поэтому xD, XD. Последнее противоречит аксиоме I.1. <

• Доказательство теоремы 17.3. Необхо­димость. Пусть X — цикл. Тогда на основании леммы 17.5 |Х ∩ С| ≠ 1 для каждого коцикла С. Любое под­множество из X независимо и, в силу леммы 17.4, не удовлетворяет условию 1).

Достаточность. Пусть X — непустое подмноже­ство элементов матроида, удовлетворяющее условиям 1) и 2). Согласно лемме 17.4 множество X зависимо. Все его собственные подмножества не удовлетворяют условию 1) и независимы в силу леммы 17.5. <