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

Доказано, что всякий трансверсальный матроид представим над некоторым полем и что он би­нарен тогда и только тогда, когда является графическим. Дальнейшие результаты, относящиеся к трансверсальным матроидам, будут рассмотрены ниже.

Ограничения и сужения. Часто в теории графов удается исследовать граф, рассматривая его подграфы или граф, полученный стягиванием некоторых его ребер. Удобно ввес­ти соответствующие понятия и в теории матроидов. Пусть матроид М определен на множестве Е, и пусть А — под­множество из Е; назовем ограничением матроида М на А (обозначается М×А) матроид, циклами которого явля­ются те и только те циклы из М, которые содержатся в А. Аналогично, определим сужение матроида М на А (обозна­чается М. А) как матроид, циклы которого получаются взя­тием минимальных элементов совокупности {Cі ∩ A}, где Сі — циклы матроида М. (Более простое определение да­ется ниже.) Предоставляем читателю убедиться в том, что так определенные объекты действительно являются матроидами и что они соответствуют графам с вычеркнутыми или стянутыми ребрами. Матроид, полученный из М в резуль­тате конечнократного перехода к ограничениям и сужениям, называется минором матроида М.

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

УПРАЖНЕНИЯ

(1) Покажите, что с точностью до изоморфизма существует ровно четыре матроида на множестве из двух элементов и восемь матроидов на множестве из трех элементов. Сколько их на множестве из четырех элементов?

(2) Покажите, что с точностью до изоморфизма число матроидов на множестве из п элементов равно самое большее , а чис­ло трансверсальных матроидов равно самое большее .

(3) Докажите, что каждый k-однородный матроид трансверсален.

(4) Докажите, что циклический матроид для K4 не трансверсален, и найдите другой нетрансверсальный матроид на множестве из шести элементов.

(5) Пусть М — матроид ранга r на множестве из п элементов, и пусть b и с обозначают соответственно число его баз и циклов; покажите, что

(6) Докажите, что циклические матроиды М(К5) и М (K3,3) явля­ются графическими, но не кографическими; найдите два кографических матроида, не являющихся графическими.

(7) Пусть М — матроид на множестве Е, и пусть А В Е;

докажите, что (i) (М × В) × А = М × А; (ii) (М. В). А = М. А;

(iii) (М. В)× А = (М×(Е — (В—A))).A; (iv) (M×В).А=(М.(Е— (В— А)))× А. (8) Покажите, что если матроид М удовлетворяет любому из следующих условий, то ему удовлетворяет и любой минор матроида М: матроид M(i) графический; (ii) кографический; (iii) бинарный;

(iv) регулярный.

(9) Матроидом Фано F называется матроид, определенный на множестве Е = {1, 2, 3, 4, 5, 6, 7}, базами которого являются подмножества из Е, содержащие три элемента за исключени­ем подмножеств {1,2,3}, {1,4,5}, {1,6,7}, {2 4,7}, {2, 5,6}, {3,4, 6} и {3, 5, 7}. Покажите, что матроид F можно изобразить так, как показано на рис.3; базами F явля­ются в точности те множества из трех элементов, которые не лежат на одной прямой.

Рис. 3.

Покажите также, что матроид F яв­ляется (i) бинарным;

(ii) нерегулярным; (iii) нетрансверсальным; (iv) неграфическим и некографическим; (v) эйлеровым.

(10) Если М — матроид на множестве Е, то нетривиальное подмно­жество А из Е называется отделяющим подмножеством, если

M×А = М. А; докажите, что следующие условия эквивалент­ны: (i) А является отделяющим подмножеством; (ii) каждый цикл из М содержится либо в А, либо в Е —А; (iii) ρ(A) +ρ (E — А) = ρ (Е). Что можно сказать о графе, циклический матроид которого не содержит отделяющих подмножеств?

(11) Пусть D—орграф без петель, и пусть E и Y —два непересе­кающихся множества вершин орграфа D. Подмножество А из Е называется независимым, если существует |А| вершинно непересекающихся простых орцепей из А в Y. Докажите, что эти независимые множества задают некоторый матроид на Е. Докажите также, что всякий трансверсальный магроид можно получить описанным способом (Такой матроид назы­вается гаммоидом.)

1.8.3. Матроиды и теория графов

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

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

Этого можно достичь следующим образом: пусть матро­ид М=(Е, ρ) определен в терминах его ранговой функции; назовем двойственным матроидом для М (обозначается М*) матроид на Е, ранговая функция которого ρ* определяется равенством

Необходимо сначала проверить, что ρ* действительно является ранговой функцией матроида на Е.

Теорема 1. М* = (Е, ρ*) является матроидом на Е.

Доказательство. Нам надо убедиться в том, что функция ρ* удовлетворяет условиям (ρi), (ρii) и (ρiii), перечисленным в разд 1.8.1.

Чтобы доказать (ρi), заметим, что ρ (Е — А) ≤ ρ (Е) и, следовательно,

ρ *(А) ≤| А |. Кроме того (согласно свой­ству (ρiii), примененному к функции ρ), имеем ρ (Е) + ρ (Ø) ≤ ρ (А) + ρ (Е — А), и поэтому

ρ (Е) — ρ (Е —А)≤ρ (А) < | А |. Отсюда сразу вытекает, что ρ*( А) ≥ 0. Доказательство свойства (ρii) тоже проводится непосредст­венно и предлагается читателю в качестве упражнения.

Докажем (ρiii). Для любых А, В Е имеем

(согласно свойству (ρiii), примененному к ρ), что и требова­лось.

Это определение позволяет, как мы сейчас покажем, очень просто описать базы матроида М* в терминах баз матроида М.

Теорема 2. Базами матроида М* являются в точ­ности дополнения баз матроида М.

Замечание. На самом деле этот результат можно исполь­зовать для определения М*.

Доказательство. Покажем, что если В* — база в М*, то Е — В* является базой в М; обратный результат полу­чается простым обращением рассуждений.

Так как В* независимо в М*, то |В*|= ρ *(В*) и, следо­вательно,

ρ (E—В*) = ρ (E). Таким образом, осталось толь­ко доказать, что Е—В* независимо в М. Но это сразу сле­дует из равенства ρ *(В*) = ρ *(E) (и надо применить еще указанное выше выражение для ρ *).

Непосредственным следствием данного выше определе­ния является то, что (в отличие от планарных графов) каж­дый матроид имеет двойственный и этот двойственный един­ствен. Из теоремы 2 также сразу следует, что матроид, двойственный М*, т. е. М**, равен М. В действительности, как мы увидим, этот совсем тривиальный результат является естественным обобщением на матроиды (нетривиальных) результатов. А сейчас мы покажем, что коциклический матроид M*(G) графа G двойствен его циклическому матроиду M(G).

Теорема 3. Для любого графа G имеем М*( G) =^ = (M(G))*.