Дискретно-непрерывная математика (стр. 10 )

1.8.1. Ведение в теорию матроидов

Ранее мы определили остовное дерево связного графа как связный подграф графа G, не содержащий циклов и включающий каждую вершину изб. Ясно, что остовное дере­во не может содержать в качестве собственного подграфа другое остовное дерево. Можно также показать, что если В1, и В2 — остовные деревья графа G и е — любое ребро из В1, то можно найти такое ребро f из В2, что (В1 — {е}) {f}, (т. е. граф, полученный из В1 заме­ной е на f), также является остовным деревом в G.

Аналогичные результаты имеют место в теории векторных пространств и в теории трансверсалей. Если V—векторное пространство, а В1 и В2 — его базисы, то для любого эле­мента е из В1 найдется элемент f из В2, обладающий тем свойством, что множество (В1 — {е}) {f} также является базисом в V. Соответствующий результат из теории трансвер­салей сформулирован ранее. Отправляясь от этих трех примеров, дадим теперь наше первое определение матроида.

Матроидом М называется пара (Е, B), где Е — непустое конечное множество, a B — непустая совокупность его подмножеств (называемых базами), удовлетворяющая сле­дующим условиям:

(Bi) никакая база не содержит в качестве собственного подмножества другую базу;

(Bii) если В1 и В2 — базы и е — любой элемент из В1, то существует элемент f из В2, обладающий тем свойством, что (B1 — {е}) {f} также является базой.

Применяя достаточное число раз свойство (Bii), можно показать (это несложное упражнение), что любые две базы матроида М содержат одинаковое число элементов; это чис­ло называется рангом М.

Как указывалось выше, с любым графом G можно естест­венным образом связать некоторый матроид, взяв в качестве Е множество ребер графа G, а в качестве баз— ребра остовных лесов графа G. По причинам, которые выяснятся позд­нее, этот матроид называется циклическим матроидом графа G и обозначается через M(G). Аналогично, если Е — конеч­ное множество векторов в векторном пространстве V, то можно задать матроид на Е, взяв в качестве баз всевозмож­ные линейно независимые подмножества из Е, порождающие то же подпространство, что и Е. Матроид, полученный таким образом, называется векторным матроидом. Позднее мы рассмотрим такие матроиды более подробно.

Подмножество множества Е называется независимым, если оно содержится в некоторой базе матроида М. Следова­тельно, базы М являются в точности максимальными неза­висимыми множествами, т. е. такими независимыми мно­жествами, которые не содержатся ни в каких более крупных независимых множествах. Таким образом, любой матроид однозначно определяется своими независимыми множествами. В случае векторного матроида подмножество из Е независимо тогда и только тогда, когда его элементы, рассматриваемые как векторы в векторном пространстве, линейно независимы. Если G— граф, то независимыми множествами в M(G) являются те множества ребер из G, которые не содержат циклов, други­ми словами, множества ребер лесов, содержащихся в G.

Так как матроид можно полностью описать перечислени­ем его независимых множеств, то возникает вопрос: нельзя ли проще определить матроид в терминах его независимых множеств? Сейчас мы дадим одно из таких определений.

Матроидом М называется пара (Е, J), где Е — пустое конечное множество, a J — непустая совокупность подмно­жеств из Е (называемых независимыми множествами), удов­летворяющая следующим условиям:

(J i) любое подмножество независимого множества неза­висимо;

(Jii) если I и J — независимые множества, содержащие соответственно k и k + 1 элементов, то существует элемент е, принадлежащий J и не принадлежащий I, такой, что I{е} независимо.

(Заметим, что если исходить из этого определения, то базой следует называть любое максимальное независимое множество; многократно используя свойство (Jii), можно показать, что любое независимое множество можно расши­рить до базы.)

Если матроид М = (Е, J) определен в терминах незави­симых множеств, то подмножество множества Е называют зависимым, когда оно не является независимым; минималь­ное зависимое множество называется циклом. Заметим, что если M(G) — циклический матроид некоторого графа G, то циклами в M(G) являются как раз циклы графа G. Понятно, что подмножество из Е независимо тогда и только тогда, когда оно не содержит циклов; поэтому матроид можно оп­ределить и в терминах его циклов.

Прежде чем перейти к некоторым примерам матроидов, дадим еще одно определение матроида в терминах ран­говой функции ρ.

Если матроид М = (Е, J) определен в терминах своих независимых множеств и если А — подмножество из Е, то мощность наибольшего содержащегося в А независимого множества называется рангом А и обозначается ρ(A). Заме­тим, что определенный ранее ранг матроида М равняется ρ(E). Поскольку подмножество А из Е независимо тогда и только тогда, когда ρ(A) = | А |, то отсюда следует, что матроид можно определить в терминах его ранговой функ­ции. Сейчас мы это и покажем.

Теорема 1. Матроид можно определить как пару (Е, ρ), где Е — непустое конечное множество, а ρ — при­нимающая целые значения функция, определенная на множест­ве подмножеств множества Е и удовлетворяющая таким ус­ловиям:

Доказательство. Предположим сначала, что матроид М = (Е, J) определен в терминах своих независимых мно­жеств; нам надо доказать свойства (ρi) — (ρii). Свойства (ρi) и (ρii) тривиально выполняются, а чтобы доказать (ρiii), обозначим через X базу (т. е. максимальное неза­висимое подмножество) множества A ∩ В; так как X -

независимое подмножество в A, то X можно расширить до базы Y множества А и (аналогичным образом) до базы Z множества А В. Поскольку X(Z — Y), очевидно, является независимым подмножеством в В, отсюда следует, что

что и требовалось.

Обратно, пусть матроид М = (Е, ρ) определен в терми­нах ранговой функции ρ. Назовем независимыми те и только те подмножества А из Е, для которых ρ (A) = | А |.

Свойство (Ji) доказывается непосредственно. Чтобы до­казать (Jii), обозначим через I и J независимые множества, содержащие k и k + 1 элементов соответственно, и пред­положим, что для любого элемента е, принадлежащего J и не принадлежащего I, ρ (I е) = k. Если е и f — два та­ких элемента, то

отсюда следует, что ρ(Iеf)=k. Продолжим эту процедуру, добавляя каждый раз по одному новому элемен­ту из J; так как на каждом шаге ранг равен k, то получаем, что ρ (I J) = k и, следовательно (согласно (ρii)), ρ(J)≤k, что невозможно. Значит, существует элемент f, принадлежащий J, не принадлежащий I и обладающий тем свойством, что ρ (I f) = k +1.

В заключение этого параграфа дадим два простых опре­деления. Петлей матроида М = (Е, ρ) называется элемент е из Е,удовлетворяющий равенству ρ({е})=0; парой па­раллельных элементов матроида М называется пара {е, f} элементов из Е, не являющихся петлями и удовлетворяю­щих равенству ρ ({е, f})= 1. Читателю следует проверить, что если М — циклический матроид некоторого графа G, то петли и параллельные элементы в М соответствуют пет­лям и кратным ребрам в G.

УПРАЖНЕНИЯ

(1) Покажите, что любые две базы матроида на множестве Е содержат одинаковое количество элементов; более того, если А — произвольное подмножество из Е, то любые два макси­мальных независимых подмножества из А содержат одинако­вое число элементов.

(2) Пусть М = (E, ρ)— матроид с ранговой функцией ρ. Докажи­те, что М*=(E, ρ*), где ρ* определяется равенством ρ*(А)=|А|+ρ(Е— А)—ρ(Е), также является матроидом. Покажите также, что В является базой М тогда и только тог­да, когда Е — В является базой М*. (Это упражнение будет решено ниже.)