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

Доказательство. Как только что упоминалось, расшире­ние теоремы 3 с двух матроидов до k матроидов осуществ­ляется простой индукцией. При этом ранг любого подмно­жества X из Е получается ограничением этого объедине­ния на X с учетом легко проверяемого соотношения

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

Следствие 5. Матроид М = (Е, ρ) содержит k непересекающихся баз тогда и только тогда, когда для лю­бого подмножества А из Е

Доказательство. Матроид М содержит k непересекающих­ся баз тогда и только тогда, когда ранг объединения k эк­земпляров матроида М не меньше kρ(E); теперь утверждение непосредственно вытекает из следствия 4.

Следствие 6. Пусть М = (Е, ρ) — матроид; Е мож­но представить в виде объединения не более чем k независи­мых множеств тогда и только тогда, когда kρ (A) ≥ | А | для любого подмножества А из Е.

Доказательство. В этом случае ранг объединения k экземпляров матроида М равен | Е |. Отсюда и из следствия 4 сразу вытекает, что

kρ (A) + | E — А | ≥ | Е |, что и требовалось.

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

Теорема 7. Связный граф G содержит k реберно непересекающихся остовных деревьев тогда и только тогда, когда для любого его подграфа Н

где через т(Н) и m(G) обозначено число ребер в Н и G соответственно.

Теорема 8. Связный граф G можно разбить на не более чем k деревьев тогда и только тогда, когда kκ(H)≥т(Н) для любого его подграфа Н.

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

УПРАЖНЕНИЯ

(1) Покажите, как модифицировать доказательство теоремы Холла, предложенное Халмошем и Вогеном, чтобы получить доказательство теоремы 1.

(2) Докажите, что в трансверсальном матроиде М = M(S1, ... ..., Sm) ранга r существует r таких множеств Si (скажем, ), что .

(3) Докажите, что матроид М трансверсален тогда и только тог­да, когда его можно представить в виде объединения матроидов ранга один.

(4) Пусть М1 = (Е, ρ1) и М2 = (Е, ρ2) — матроиды на мно­жестве Е. Докажите, что М1 и М2 имеют общее независимое множество мощности k тогда и только тогда, когда для любого подмножества A из E

(5) Сформулируйте утверждения, двойственные теоремам 7 и 8, получив тем самым еще два результата теории графов.

(6) Используя следствие 6, получите условие, при котором ко­нечное множество векторов векторного пространства можно разбить на k попарно непересекающихся линейно независи­мых подмножеств. Выведите соответствующий результат из следствия 5.

(7) Пусть &— семейство непустых подмножеств множества Е; найдите условие, при котором & содержит t попарно непере­секающихся частичных трансверсалей мощностей r1, ..,, rt.

1.9 Экстремальные множества и задачи покрытия и упаковки в матроидах

1.9.1. Введение

Данный раздел посвящен исследованию различных аспектов задач покрытия и упаковки в матроидах, а именно: взаимосвязи этих задач между собой и с задачами построения базы суммы матроидов, алгоритмов их решения, многообразия возможных ре­шений и т. д. Основные понятия и обозначения, а также некото­рые сведения из теории матроидов изложены в разд. 1.9.2.

В 1971 г. предложил конструктивное описа­ние цикла суммы матроидов и понятие увеличивающего пути для увеличения независимого множества суммы матроидов. Эти понятия и результаты изложены в разд. 1.9.3 и играют важную роль в дальнейших рассуждениях. В частности, видно, что из конст­рукции цикла суммы матроидов непосредственно следуют:

теоремы Нэш-Вильямса о ранге суммы матроидов, а также о том, что сумма матроидов есть матроид;

алгоритм отыскания базы суммы нескольких матроидоп, а значит, и решения задач упаковки и покрытия, требующий О(|Е|3) обращений к оракулам независимости.

Сочетание этих идей с идеями об алгоритмах упаковки и покрытия для графов позволило построить для одинаковых матроидов алгоритмы решения указанных задач, требующих рекордно маленького числа О(|Е|2) обращений к ора­кулу независимости (см. разд. 1.9.8). В разд. 1.9.4 полноты ради описа­ны применения теоремы Нэш-Вильямса к задачам покрытия, упаковки, а также пересечения в матроидах. В разд. 1.9.5 рассмат­риваются так называемые экстремальные множества набора мат­роидов, которые естественно интерпретировать как препятст­вия, ограничивающие возможности построения базы заданных размеров в сумме матроидов. Устанавливается, что совокупность экстремальных множеств образует решетку. Эта решетка была открыта независимо многими авторами. Дастся ее описание в различных терминах.

В разд. 1.9.6 вводится понятие базового ряда последовательности матроидов. Прообразом понятия базового ряда последовательности одинаковых матроидов служит введенное в 1971 г. понятие регулярной упаковки стя­гивающих лесов графа. Базовый ряд последовательности матро­идов на множестве Е представляет некоторое особое разбиение множества элементов базы суммарного матроида на независимые множества соответствующих матроидов, в частности, содержащие максимальную упаковку баз этих матроидов. Таким образом, по­строение базового ряда дает одновременно решение задач покры­тия и упаковки для заданных матроидов. В разд. 1.9.7 выясняется, что базовый ряд последовательности матроидов допускает есте­ственную декомпозицию относительно экстремального множества этой последовательности. В разд. 1.9.8 приводится алгоритм постро­ения базового ряда последовательности нескольких матроидов, требующий О(|Е|3) обращений к оракулам независимости, опи­сывающих совокупность матроидов. В случае одинаковых матро­идов удается найти алгоритм построения базового ряда, имею­щий О(|Е|3) обращений к оракулу независимости. Этот алгоритм позволяет, в частности, решать задачи построения базы суммы заданного числа одинаковых матроидов, а значит, и задачи по­крытия и упаковки для данного матроида. В разд. 1.9.9 проводится качественное сравнение некоторых матроидных алгоритмов.

1.9.2. ОСНОВНЫЕ ПОНЯТИЯ И ОБОЗНАЧЕНИЯ. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ МАТРОИДОВ

2.1. Пусть Е — конечное множество. Если ХЕ, то пусть = Е \ X, а |Х|—число элементов в X. Если А, В E и А ∩ В =Ø, то вместо A В запишем А + В. Системаподмножеств из Е называется системой независимости, а множества — независимыми, если

Максимальное по включению множество в называется ба­зой системы . Множество всех баз в обозначим через Подмножество А из Е называется зависимым, если А. Ми­нимальное по включению зависимое подмножество из Е называ­ется циклом системы . Множество всех циклов в обозначает­ся через

Система независимости = М называется матроидом, если

Можно доказать, что системабаз матроида М обладает