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

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

С другой стороны, если D* является циклом в (M(G))*, то D* не содержится ни в какой базе из (M(G))*. Следова­тельно, D* пересекается с каждой базой из M(G), т. е. с каждым остовным лесом графа G. Из известного утверждения вытекает, что D* содержит разрез. Отсюда и следует нужный резуль­тат.

Прежде чем продолжить наше изложение, удобно ввести еще несколько терминов. Будем говорить, что множество элементов матроида М образует коцикл в М, если это мно­жество является циклом в М*. Заметим, что по теореме 3 коциклами циклического матроида графа G являются в точ­ности разрезы графа G. Аналогично, назовем кобазой в М множество, являющееся базой в М*. Соответствующие оп­ределения можно дать для коранга, конезависимого мно­жества и т. д. Будем также называть матроид М кографическим тогда и только тогда, когда двойственный ему матроид М* является графическим; по теореме 3 это определение согласуется с данным в предыдущем параграфе. Введение таких «ко-названий» обусловлено тем, что они позволяют нам ограничиться рассмотрением одного матроида М, не об­ращаясь к М*.

Для иллюстрации докажем теорему.

Теорема 4. Всякий коцикл матроида пересекается с любой из его баз.

Доказательство. Пусть С* — коцикл матроида М, и пусть существует база В в М, обладающая тем свойством, что С* ∩В пусто. Тогда С* содержится в Е — В и поэто­му является циклом в М*, содержащимся в базе матроида М*. Это противоречие и доказывает нужный результат. Следствие 1. Всякий цикл матроида пересекается с любой кобазой.

Доказательство. Применим теорему 4 к матроиду М*.

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

В качестве следующего примера упрощения, которое дает теория матроидов, рассмотрим еще раз известный пример.

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

Обратимся теперь к планарным графам и, в частности, покажем, что определения геометрической двойственности, абстрактной двойственности и двойственности по Уитни для графов являются следствиями определения двойственно­сти для матроидов. Начнем с абстрактной двойственности.

Теорема 5. Если граф G* абстрактно двойствен графу G, то матроид M(G*) изоморфен (M(G))*.

Доказательство. Так как граф G* абстрактно двойствен графу G, то существует взаимно однозначное соответствие между их ребрами, обладающее тем свойством, что циклы в G соответствуют разрезам в G*, и наоборот. Отсюда сразу вытекает, что циклы в М(G) соответствуют коциклам в М(G*) и, следовательно, по теореме 3,

М(G *) изоморфен (M(G))*, что и требовалось.

Следствие 2. Если граф G* геометрически двойст­вен связному планарному графу G, то M(G*) изоморфен (M(G))*.

Доказательство. Этот результат сразу следует из теоремы 5.

Заметим, что (как указывалось ранее) планарный граф может иметь несколько различных двойственных графов, тогда как матроид имеет только один двойственный матроид. Это объясняется тем, что, как легко проверить, если G* и Gх — два (возможно, неизоморфных) двойственных графа для G, то циклические матроиды для G* и Gx изоморфны. Теперь мы подошли к двойственности по Уитни.

Теорема 6. Если граф G* двойствен по Уитни гра­фу G, то M(G*) изоморфен (M(G))*.

Доказательство. Как известно, граф G* двойствен по Уитни графу G тогда и только тогда, когда G* абстрактно двойствен графу G. Поэтому наше утверждение сразу следует из теоремы 5. Можно рассуж­дать и по-другому: определяющее соотношение для двойст­венности по Уитни нетрудно вывести из формулы для ρ*, данной в следствии 1. Детали этого рассуждения мы пре­доставляем читателю. В заключение этого параграфа ответим на следующий вопрос: при каких условиях данный матроид М является графическим? Нетрудно найти необходимые условия. На­пример, из нашего обсуждения представимых матроидов следует, что такой матроид должен быть бинарным. Более того, ясно, что М не содержит в качестве минора никакой из матроидов

M*(K5), M*(K3,3), F или F* (где F— матроид Фано). В теореме Татта, которую мы сейчас сформулируем, утверждается, что эти необходимые условия на самом деле являются и достаточ­ными; доказательство этого результата слишком сложно и поэтому здесь не приводится.

Теорема 7 (Татт). Матроид М является графичес­ким тогда и только тогда, когда он бинарен и не содержит ни одного минора, изоморфного M*(K5), M*(K3,3), F или F*.

Применяя теорему 7 к М* и используя тот факт, что матроид, двойственный бинарному, тоже би­нарен, мы сразу получаем необходимые и достаточные усло­вия для того, чтобы матроид был кографическим.

Следствие 3. Матроид М является кографическим тогда и только тогда, когда он бинарен и не содержит ни одного минора, изоморфного M*(K5), M*(K3,3), F или F*.

Татт, кроме того, доказал, что бинарный матроид регу­лярен тогда и только тогда, когда он не содержит минора, изоморфного F или F*. Этот результат в сочетании с теоре­мой 7 и следствием 3 позволяет немедленно вывести следующий матроидный аналог известной теоремы:

Теорема 8. Матроид является планарным тогда и только тогда, когда он регулярен и не содержит миноров, изоморфных M*(K5), M*(K3,3) или двойственным им матрои-дам.

УПРАЖНЕНИЯ

(1) Покажите на примере, что матроид, двойственный трансвер-сальному матроиду, не обязательно трансверсален.

(2) Покажите, что если М — матроид на множестве Е и А — подмножество из Е, то сужение М. А представляет собой матроид, коциклами которого являются те и только те коцик­лы из М, которые содержатся в А. Покажите также, что (М. А)*= М*×А и (M× А)* = М*.А, и выведите отсю­да, что если А — отделяющее подмножество в М, то А явля­ется отделяющим подмножеством в М*, и наоборот.

(3) Докажите, что для любого цикла С и любого коцикла С* матроида М имеем |С∩С*| ≠1. Более того, докажите, что М би­нарен тогда и только тогда, когда |С∩С*| четно, и выведи­те отсюда, что матроид, двойственный бинарному, сам бинарен.

(4) Пусть М — бинарный матроид на множестве E Используя результат предыдущего упражнения, докажите что если М эйлеров, то М* двудолен; докажите также (применив индук­цию по |Е|), что верно и обратное. Рассмотрев 5-однородный матроид на множестве из одиннадцати элементов, покажите что условие бинарности матроида М не может быть опущено.

(5) Покажите, как определить векторное про­странство V, ассоциированное с матроидом М на множестве Е. Докажите, что если матроид М бинарен, то сумму любых двух подмножеств из Е можно представить в виде объединения непересекающихся циклов в М; выведите отсюда, что мно­жество всех объединений непересекающихся циклов в М образует подпространство в V (называемое циклическим под­пространством матроида М). Воспользовавшись двойствен­ностью, получите соответствующий результат для коциклов.

(6) Покажите, что для бинарных матроидов определение двойст­венного матроида обобщает определение алгебраически двой­ственного графа.

1.8.4. Матроиды и теория трансверсалей

В предыдущем параграфе было показано, что существует тесная связь между результатами теории матроидов и теории графов; здесь мы рассмотрим связь между теорией матроидов и теорией трансверсалей. Сначала покажем, как можно су­щественно упростить доказательства некоторых приведен­ных ранее утверждений из теории трансверсалей перехо­дом на матроидно-теоретическую точку зрения.