§ 24. Объединение и пересечение матроидов
Пусть М1и М2 — два матроида на множестве элементов Е с наборами независимых множеств I1 и I2 соответственно. Положим
Как показывает прямая проверка, множество I удовлетворяет аксиомам независимости. Следовательно, (Е, I) — матроид, для которого I служит набором независимых множеств. Этот матроид называется объединением матроидов М1 и М2 и обозначается через М1 M2.
Очевидно, что операция объединения матроидов ассоциативна, и можно говорить об объединении нескольких матроидов.
Теорема 24.1. Пусть {Mi: i = 1,…,к} — семейство матроидов, определенных на одном и том же множестве Е, с ранговыми функциями ρi соответственно, k>1, M — объединение всех этих матроидов. Тогда ранговая функция ρ матроида М определяется для любого подмножества ХE равенством
> Рассмотрим отдельно два случая.
1. ρ (Х)=|Х|. В этом случав ρ (A)=|A| для любого подмножества AХ. Очевидно, что
поэтому
При А=Ø получаем
Равенство (1) доказано.
2. ρ(Х) < |Х|. Воспользуемся индукцией по k. Вначале пусть k = 2. По определению ρ(Х) = |В|, где В— максимальное независимое подмножество в X. Очевидно, что В = (В∩А) (В ∩ (Х\А)) для любого АХ. Так как
то для любого АХ
Теперь получим нижнюю оценку для ρ(Х). Пусть М2` — копия матроида М2, определенная на множестве Е`, имеющем пустое пересечение с Е. Более точно: Е = {e1,e2, ...,en}, Е`= {e`1,e`2, ..., е`n], Е∩Е`' = Ø, множество {e`i1, e`i2,…,e`im } независимо относительно матроида М`2 тогда и только тогда, когда {ei1, ei2,…,eim } независимо относительно М2. Очевидно, что можно определить матроид на множестве Е Е`, объявив его независимыми множествами объединения X Y, где ХЕ независимо относительно матроида M1, YE` — относительно М`2. Обозначим этот матроид и его ранговую функцию через М1М`2 и ρ` соответственно.
Пусть теперь X — произвольное подмножество множества Е. Положив Si = {еi, е`i}, S= (Si: eiX), получим семейство S подмножеств множества Е Е`. Согласно следствию 22.2 для любого t≤|Х| частичная трансверсаль мощности t семейства S, независимая относительно матроида М1М`2, существует тогда и только тогда, когда для любых r подмножеств Si выполняется условие
Объединение множеств, заключенное в скобки, представим в виде A А`, где А Е, А' Е'. Ясно, что
поэтому условие (3) можно переписать так:
С другой стороны, легко понять, что следующие два утверждения равносильны:
существует частичная трансверсаль мощности t семейства подмножеств S, независимая относительно матроида М1М`2;
ρ(Х)≥t.
В самом деле, пусть Т — такая трансверсаль и пусть, . для определенности,
Тогда
и, следовательно,
т. е. выполняется условие (2).
Обратно, если выполняются условия (2) и (6), причем
то множество Т, определяемое условиями (5), является частичной трансверсалью мощности t семейства подмножеств S, независимой относительно матроида М1М`2.
Равносильность утверждений 1) и 2) доказана.
Из предыдущего вытекает, что ρ(Х)≥t тогда и только тогда, когда для любого подмножества А множества X верно неравенство (4). Следовательно, при t = ρ(Х)+ 1 в X существует такое подмножество Ао, которое не удовлетворяет неравенству (4), т. е.
откуда
Из (7) и (2) вытекает
Последнее равенство в сочетании с неравенством (2) приводит к формуле
Для k = 2 теорема доказана.
Пусть теперь k > 2 и теорема верна для объединения менее чем k матроидов. Если ρ` — ранговая функция объединения М1 М2... Мk-1, то в силу доказанного выше и индуктивного предположения имеем
Поскольку АВ и |B\A| + |X\B| = |Х\A|, то рассматриваемый минимум достигается лишь при А = В, и потому получаем
<
Ниже через (Е, ρ) обозначается матроид с множеством элементов Е и ранговой функцией ρ.
Следствие 24.2. Матроид (Е, ρ) имеет l попарно непересекающихся баз тогда и только тогда, когда для любого АЕ верно неравенство
> Пусть lМ — объединение l экземпляров матроида М, ρ` — ранговая функция этого объединения. Очевидно, что ρ`(lM) ≤ lρ(M) и М имеет l попарно непересекающихся баз только при условии ρ`(lM) = lρ(M). Теперь нужное утверждение непосредственно вытекает из предыдущей теоремы. <
Следствие 24.3. Для представимости множества Е в виде объединения не более чем l независимых подмножеств матроида М = (Е, ρ) необходимо и достаточно, чтобы любое подмножество АЕ удовлетворяло условию
> Множество Е представимо в виде указанного объединения только тогда, когда ρ`(lM) = |Е|. Согласно теореме 24.1 последнее равносильно неравенству |E| ≤ lρ(А)+ ||,в свою очередь равносильному неравенству (9). <
Применим два предыдущих следствия к циклическому матроиду M(G) непустого графа G. В рассматриваемой ситуации независимыми множествами матроида служат множества ребер ациклических подграфов. Объединим каждый такой подграф со всеми не входящими в него вершинами G и будем считать подграф остовным. Для любого остовного подграфа Н верно равенство ρ(М(Н)) = n(G) - k(H). Если H — остовный подграф с множеством ребер А, то неравенства (8) и (9) превращаются в неравенства
и, соответственно,
Поэтому верны следующие два утверждения.
Следствие 24.4. В непустом графе G имеется l реберно непересекающихся остовов тогда и только тогда, когда любой его остовный подграф удовлетворяет неравенству (10).
Следствие 24.5. Для того чтобы непустой граф G был объединением не более чем l своих остовов, не имеющих общих ребер, необходимо и достаточно выполнение условия (11) для любого его остова Н.
Аналогично введенному выше понятию объединения матроидов можно ввести понятие их пересечения. Пусть Mj = (E, Ij) (j = 1,…,k) — k матроидов на множестве элементов Е с наборами независимых множеств Ij. Пару М = (Е, I),
назовем пересечением матроидов Mj (j = 1,…,k) и обозначим
Разумеется, пересечение матроидов также может оказаться матроидом. Например, пересечение тривиального матроида и любого матроида с тем же множеством элементов есть тривиальный матроид. Но, как правило, пересечение матроидов М не является матроидом с набором независимых множеств I, поскольку I может не удовлетворять аксиоме независимости I.2. Например, пересечение двух матроидов М1=(Е, I1) и М2=(Е, I2), где Е = {1, 2, 3, 4}, I1 = {Ø, {1}, {2}, {3}, {4}, {1, 3}, {1, 4}, {2, 3}, {2, 4}}, I2={ Ø, {1}, {2}, {3}, {4}, {1, 2}, {1, 4}, {2, 3}, {3, 4}}, не есть матроид, так как множество
I1 ∩ I2 ={0, {1}, {2}, {3}, {4}, {1, 4}, {2, 3}} не удовлетворяет условию I.2.
В § 28 читатель столкнется со следующей задачей:
Задача о пересечении k матроидов. Даны k матроидов на одном и том же множестве элементов Е. Требуется найти в Е наибольшее по числу элементов подмножество, являющееся независимым множеством каждого из заданных матроидов.
Пусть, например, заданы два графа G и Н, причем |EG| = |ЕН| = т. Пусть ребра этих графов занумерованы с помощью одних и тех же меток: EG = EH = {1, 2, ..., т}. Очевидно, что задача нахождения в Е наибольшего по числу элементов подмножества, не содержащего циклов ни первого, ни второго графов, и есть задача о пересечении двух графических матроидов M(G) и М(Н).
Задача о пересечении лишь двух матроидов стоит особняком: она эффективно решается методом чередующихся последовательностей (см., например, [25]). Идея этого метода демонстрируется в § 77.
При k > 2 задача о пересечении k матроидов становится очень трудоемкой. Даже для решения ее простейшего варианта — задачи о пересечении трех матроидов разбиений — не найдено, и скорей всего не существует, эффективных алгоритмов.
УПРАЖНЕНИЯ
1. Пусть М — матроид порядка п. Покажите, что число его баз не превосходит , а число его циклов не превосходит
2. Пусть М = (Е, I) — матроид с набором независимых множеств I, Ø ≠ A Е. Пусть, далее, I` = {X I: X ∩ А = Ø }. Докажите, что M` = (Е, I`) — матроид с набором независимых множеств I`. Матроид M` называется сужением матроида М посредством А.
Пусть в обозначениях предыдущего упражнения I`` = { X ∩ А : X I}. Докажите, что M`` = (Е, I``) —матроид с набором независимых множеств I``. Матроид M`` называется ограничением матроида М на А.
Пусть Е — непустое конечное множество, k ≤ |Е|. Докажите, что множество β всех k-элемеятных подмножеств множества Е удовлетворяет аксиомам баз и, следовательно, (Е, β) — матроид. Его называют однородным матроидом ранга k.
Пусть D — ориентированный граф, и пусть Е и Y — два непересекающихся подмножества его вершин. Подмножество АЕ называется независимым, если существует |A| вершинно непересекающихся простых орцепей из A в Y. Докажите, что эти независимые множества задают некоторый матроид.
Пусть М — матроид с ранговой функцией ρ. Докажите, что для любого подмножества А его элементов
ρ*(А) = |A| + ρ() - ρ (M),
где ρ* — коранговая функция матроида М.
Для каких k и п существуют однородные матроиды порядка п и ранга k, являющиеся матроидами циклов некоторого графа?
Исследуйте циклические матроиды М(К5) и М(К3,3). Докажите, что они не являются кографическими.
Покажите, что с точностью до изоморфизма число матроидов порядка п не превосходит .
Охарактеризуйте графы, матроиды циклов и разрезов которых изоморфны.
Покажите, что с точностью до изоморфизма существует ровно 4 матроида порядка 2 и 8 матроидов порядка 3. Сколько среди них представимых над каким-либо полем?
Пусть M1 и М2 — матроиды на множестве Е с ранговыми функциями ρ1 и ρ2. Докажите, что М1 и M2 имеют общее независимое множество мощности k тогда и только тогда, когда ρ1(A) + ρ2 () ≥ к для любого А Е.
Докажите, что каждый однородный матроид является трансверсальным.
Докажите, что трансверсальные матроиды и только они представимы в виде объединений матроидов ранга 1.
Докажите, что циклический матроид М(К4) не является трансверсальным.
Докажите, что матроид, двойственный к трансверсальному, не обязательно является трансверсальным.
Докажите, что с точностью до изоморфизма число трансверсальных матроидов порядка п не превосходит .
18. Необходимо выполнить на ЭВМ множество заданий. Все задания требуют для выполнения одинакового времени. Каждому из заданий присвоен крайний срок выполнения.
а) Покажите, что набор всех подмножеств заданий, которые можно выполнить с соблюдением сроков выполнения, образует набор независимых подмножеств некоторого матроида.
б) Допустим, что за каждое не выполненное в срок задание необходимо заплатить штраф, величина которого одинакова для всех заданий. В каком порядке следует выполнять задания, чтобы общий штраф был минимальным?
19. Пусть М — матроид, элементам е которого приписаны не отрицательные веса w(e). Докажите, что
где β — множество баз матроида М, φ* — множество коциклов матроида М.