10.2. Фундаментальные свойства

В этом разделе мы установим несколько фундаментальных свойств матроидов. Все они известны в теории графов.

Сначала рассмотрим независимые множества и базы матроида М.

Теорема 10.2 (теорема добавления). Пусть X и Y — произвольные независимые подмножества в матроиде М. Если то существует такое независимо в М.

Доказательство. Пусть — такое множество, что независимо в М; 3) если для любого независимо в М, то Допустим, что Тогда существует множество Поскольку независимо в М, по аксиоме 1.3 найдется такой элемент что независимо в М. Множество противоречит выбору Следовательно, что доказывает теорему.

Следствие 10.2.1. Все базы матроида М на множестве 5 имеют одинаковую мощность, равную рангу М.

Доказательство. Допустим противное. Пусть базы и . Тогда по теореме добавления существует такое что — независимое множество. Однако это противоречит максимальности в

С помощью теоремы добавления можно доказать также обобщение этого результата.

Следствие 10.2.2. Пусть М — матроид на множестве S, Тогда все максимальные независимые подмножества А имеют одинаковую мощность. Другое следствие из теоремы 10.2 сформулируем без доказательства. Следствие 10.2.3. Если и — базы магроида М и то существует такое что является базой матроида М.

Теперь изучим свойства функции ранга матроида.

Теорема 10.3. Функция ранга магроида М на множестве обладает следующими свойствами:

4. Подмодульное неравенство .

Доказательство. Первые три свойства следуют непосредственно из определения функции ранга.

Докажем свойство 4. Пусть X — максимальное независимое подмножество По теореме добавления существует максимальное независимое подмножество содержащее. Пусть где Так как — независимое подмножество — независимое подмножество В, то получим Следовательно,

Свойство 5 является следствием свойства 4.

Перейдем к рассмотрению циклов матроида. Сформулируемые ниже свойства непосредственно следуют из определения цикла.

1. Любое собственное подмножество цикла — независимо. Поэтому если различные циклы, то

2. Если С — цикл, то

3. Матроид М на множестве S не содержит циклов тогда и только тогда, когда все подмножества S — независимы. Таким образом, множество S является единственной базой такого матроида М.

Теорема 10.4. Если различные циклы матроида М и то существует такой цикл что

Доказательство. Пусть . Покажем, что С — зависимо, т. е. , доказывая тем самым теорему.

Поскольку и — различные циклы, является собственным подмножеством как так Поэтому независимо. Таким образом, Кроме того, Теперь, используя этот результат и подмодульность функции ранга (теорема 10.3), получим

Поскольку имеем также

Объединив выражения (10.1) и (10.2), получим

Следствие 10.4.1. Если А — независимое множество матроида М на множестве S, то для любого содержит не более одного цикла.

Доказательство. Допустим, что для некоторого существуют два таких различных цикла что Тогда по предыдущей теореме существует цикл Следовательно, — зависимое множество. Но что противоречит независимости множества А.

Следствие 10.4.2. Если В — база матроида М на множестве 5 и то существует такой единственный цикл , что

Доказательство. Поскольку В — максимальное независимое множество, в содержится цикл. По предыдущему следствию этот цикл единственный.

Определенный в этом следствии цикл называется базисным циклом элемента по отношению к базе В.

Докажем теперь более сильный результат, чем теорема 10.4.

Теорема 10.5. Если — различные циклы матроида и то для любого существует такой цикл С, что

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

По теореме 10.4 существует цикл Из выбора х и у очевидно, что Кроме того, в противном случае что противоречит тому факту, что — минимальное зависимое множество. Пусть тогда

Теперь для циклов справедливы следующие утверждения:

— собственное подмножество поскольку Из выбора следует, что существует такой цикл что

Для циклов С, и имеем так как

— собственное подмножество поскольку

Из выбора также следует, что существует такой цикл что

Поскольку — собственное подмножество цикл таков, что а это противоречит выбору