§ 22. Трансверсали

Пусть Е — конечное непустое множество, a S = (S1, S2, .., Sm) — m-членное семейство его подмножеств, т. е. последовательность длины m, составленная из непу­стых (не обязательно различных) подмножеств множе­ства Е. Подмножество ТЕ называется трансверсалью (или системой различных представителей) семейства S, если существует биективное отображение φ: T → {1, 2,..., т}, при котором для каждого tT выполняется ус­ловие tSφ(t). Это означает, другими словами, что су­ществует такая нумерация элементов множества T, при которой ti Si (i = 1, …, m).

Подмножество ТЕ называется частичной трансвер­салъю семейства S, если существует инъективное отобра­жение φ: T → {1, 2,..., т}, при котором для каждого tT выполняется условие tSφ(t), Тем самым, частич­ные трансверсали семейства S — это трансверсали его подсемейств.

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

Например, если есть четверо юношей х1, x2, xз, x4 и пять девушек у1, у2, у3, y4, у5, а отношение знакомства между ними задается таблицей 22.1, то возможно следующее решение: x1 женится на у4, x2 – на у1, x3 — на y3, х4 — на y2. Если теперь Е = {у1, y2 , y3, y4, y5), то рас­смотренной таблице соответствует семейство подмножеств S = (S1, S2, S3, S4) множества Е, где Si — множество де­вушек, с которыми знаком юноша xi, т. е. S1 = {y1, y4₄, y5}, S2 = {y1}, S3 = {y2, y3, y4}, S4 = {y2, y4}. Задача о свадь­бах имеет решение, когда для соответствующего семейства подмножеств S существует трансверсаль. В нашей ситуации трансверсалью служит, например, множество {y1, y2, y3, y4}, при этом y4S1, y1S2, y3S3, y2S4.

Трансверсали семейства множеств может и не суще­ствовать. Пусть, например, S = (S1, S2, S3, S4), S1 = {l, 2}, S2 = {1, 2, 3}, S3 = {2, 3}, S4 = {1, 3}. Тогда

а в трансверсали должно быть четыре элемента. Следовательно, трансверсали нет.

Задача о существовании трансверсали решена Ф. Холлом.

Теорема Холла (1935 г.). Пусть Е — непустое конечное множество, S = (S1, S2, ..., S_m) — семейство его подмножеств. Для существования трансверсали семейства S необходимо и достаточно, чтобы для каждого k = 1,…,m объединение Si1 Si2 _… Sik любых k подмножеств Si содержало не менее k различных элементов.

Теорема Холла является отправным моментом теории трансверсалей. Известно несколько доказательств этой теоремы. Ниже приводится доказательство более общей теоремы, принадлежащей Р. Радо.

Часто возникает ситуация, когда вместе с семейством подмножеств S на множестве Е определена структура матроида М, и нужно решить вопрос о существовании трансверсали семейства S, независимой относительно матроида М, т. е. являющейся независимым подмножеством элементов этого матроида. На этот вопрос отвечает сле­дующая

Теорема Радо (1942 г.). Пусть М — матроид с множеством элементов Е, S = (S1, S2, …, Sm) — семейство непустых подмножеств множества Е. Для существования траисверсали семейства S, независимой относительно мат­роида М, необходимо и достаточно, чтобы для каждого k = 1,…,m объединение любых k подмножеств Si имело ранг, не меньший чем k.

Теоремы Холла — частный случай теоремы Радо. Дей­ствительно, если М — свободный матроид, то ранг любого подмножества ХЕ равен |Х|.

> Доказательство теоремы Радо. Необхо­димость условия теоремы очевидна; если существует не­зависимая трансверсаль семейства S, то ее пересечение с объединением любых k подмножеств Si содержит k-элементное независимое подмножество. Следовательно, ранг этого объединения не менее k.

Достаточность. Вначале докажем, что при вы­полнении условий теоремы ни одно из множеств Si не может содержать более одного такого элемента, удаление которого нарушает условие теоремы. Пусть, напротив, множество Si содержит два таких элемента х и у. Это значит, что существуют такие множества индексов А и В в {2, ..., т}, что

где ρ — ранговая функция матроида М. Положив

имеем

(см. аксиому ρ.З). Но

Поэтому

В то же время по условию теоремы

Итак,

Последнее противоречие доказывает нужное утверждение.

Пусть теперь какое-либо из подмножеств Si содержит более одного элемента. Тогда из Si можно удалить некоторый элемент, не нарушив справедливости условия теоремы. Итерируя этот процесс, придем к ситуации, в которой |Si| = 1 (i = 1,…,т) и выполняются условия теоремы. Но тогда все Si попарно различны и их объединение и есть нужная трапсверсаль. <

Понятие трансверсали можно обобщить следующим образом. Пусть Е — конечное непустое множество, S= (S1, S2,…, Sm)— семейство его непустых подмножеств, (k1, k2, ..., km) — последовательность целых положительных чисел. Семейство Р = (Р1, Р2, ..., Рm) подмножеств из Е назовем (k1, k2, ..., km)-трансверсалъю семейства S, если

Очевидно, что введенная выше трансверсаль является (1, ..., 1)-трансверсалью. Поэтому задача о свадьбах (о существовании трансверсали) естественным образом обобщается теперь в виде задачи о гаремах. Решение этой задачи, т. е. условия существования (k1, k2, ..., km)-трансверсали, легко получить непосредственно из теоре­мы Холла. Заменим семейство S другим семейством

где Sij = Si (i = l,…,m, j = 1,…,kt, t= 1,…,m). Очевидно, что семейство S имеет (k1, k2, ..., km)-трансверсаль тогда и только тогда, когда существует трансверсаль семейства S`. Таким образом, верно

Следствие 22.1. Для существования (k1, k2, ..., km)-трансверсали семейства S =(S1, S2, ..., Sm) необходимо и достаточно, чтобы для любого I{1, 2, ..., т} выпол­нялось неравенство

Аналогично из теоремы Радо можпо получить критерий существования независимой (k1, k2, ..., km)-транс­версали.

Из теоремы Радо вытекает также следующий крите­рий существования независимой частичной трансверсали фиксированной мощности.

Следствие 22.2. В обозначениях теоремы Радо се­мейство S имеет независимую частичную трансверсаль мощности t ≤ m тогда и только тогда, когда для каждого k = 1,…,m ранг объединения любых k подмножеств Si не меньше, чем k + t - m.

> Пусть D — такое множество, что |D|=m - t и D ∩ E = Ø. Построим новый матроид М` на множестве Е D, объявив его базами все подмножества BD, где В — база матроида М (очевидно, что аксиомы баз дей­ствительно выполняются), и рассмотрим семейство

Очевидно, что исходное семейство S имеет независимую частичную трансверсаль мощности t тогда и только тогда, когда семейство Т имеет трансверсаль, независимую относительно матроида М`. Согласно предыдущему след­ствию, для существования такой трансверсали необходи­мо и достаточно, чтобы объединение любых k подмно­жеств Тi содержало независимое относительно матроида М` подмножество мощности k. Но последнее условие рав­носильно условию следствия. <

Взяв в качестве М свободный матроид, получим

Следствие 22.3. Семейство подмножеств S имеет частичную трансверсаль мощности t≤m тогда и только тогда, когда для каждого k =1,…,m объединение любых k подмножеств Si имеет мощность не меньше, чем k + t - m.

Произвольное семейство S =(S1, S2, ..., Sm) непустых подмножеств множества Е определяет на Е структуру матроида, независимыми множествами которого являются частичные трансверсали этого семейства и пустое мно­жество. Об этом свидетельствует следующая

Теорема 22.4 (Дж. Эдмондс, Д. Фалкерсон, 1965г.).

Множество I, элементами которого служат все частич­ные трансверсали семейства подмножеств S и пустое мно­жество, удовлетворяет аксиомам независимости I.1 и I.2.

> В доказательстве нуждается только справедливость условия I.2. Произвольную частичную трансверсаль Х = {х1, х2, ..., xk} семейства S, представляющую подсемей­ство (Si1, Si2, ..., Sik), т. е. такую, что xp  Sp, запи­шем в виде

Пусть

— еще одна частичная трансверсаль и l > k. Нужно до­казать существование среди у1 у2, ..., yl такого у, что X_y _I

Если в (3) есть такая пара (y, j), что у не совпадает ни с одним из x в (2), а j — ни с одним из i, то, очевид­но, что X_y _I.

Пусть теперь в (3) нет такой пары. Но так как l>k, то существует индекс j, пусть это j1, отличный от всех индексов i в (2). При этом y1 совпадает с каким-либо из х, например, у1 = х1. Теперь можно написать

т. е. трансверсаль X представляет и подсемейство (Si1, Si2, ..., Sik), при этом х1= y1. Среди индексов j2, ..., jl существует индекс, отличный от каждого i2, ..., ik, пусть это будет j2. Тогда y2 совпадает с каким-либо из x2,..., xk, например, у2 = х2. Теперь имеем

Итерируя этот процесс, получим xi=yi (i = 1,…,k) (с точ­ностью до перенумерации элементов yi). Следовательно, X{y1, y2, …, yl}, X_yk+1 _I. <

Итак, (Е, I) — матроид с набором независимых мно­жеств I. Этот матроид называется матроидом трансверсалей семейства S. Матроид, изоморфный матроиду трансверсалей какого-либо семейства подмножеств, называется трансверсальным.

В важном частном случае, когда исходное семейство S является разбиением множества Е, т. е.

и подмножества Si попарно не пересекаются, матроид трансверсалей семейства S называется матроидом разбиения S. Очевидно, что подмножество ХЕ независимо относительно матроида разбиения S тогда и только тог­да, когда |X ∩ Si| ≤ 1 (i = 1,…,m).