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

Рассмотрим другой пример. Предположим, что Е = {1, 2, 3, 4, 5, 6}, a

S1 = S2 = {1, 2}, S 3 = S 4 = {2, 3}, S 5 = {1, 4, 5, 6}. Здесь невозможно найти пять различных элементов из Е — по одному из каждого под­множества Sі, другими словами, это семейство & = (S1, ... ..., S 5) не имеет трансверсали. Заметим, однако, что его подсе­мейство

&'= {S1, S2, S3, S5) имеет трансверсаль, например {1, 2, 3, 4}. Трансверсаль произвольного подсемейства се­мейства & будем называть частичной трансверсалью для &; в нашем примере семейство & имеет несколько частичных трансверсалей (например, {1, 2, 3, 6}, {2, 3, 6}, {1, 5}, Ø и т. д.). Ясно, что любое подмножество частичной трансверса­ли само является частичной трансверсалью.

Естественно спросить: при каких условиях данное се­мейство подмножеств некоторого множества имеет трансвер­саль? Легко увидеть связь между этой задачей и задачей о свадьбах, если взять за Е множество девушек, а за Sі — множество девушек, знакомых юноше bi (1 ≤ i ≤ т); трансверсалью в этом случае является множество из т девушек, такое, что каждому юноше соответствует ровно одна (знакомая ему) девушка. Следовательно, теорема 1 раздела 1.3 дает необходимое и достаточное условие существования трансверсали для данного семейства множеств. Сформу­лируем теорему Холла для этого случая и дадим другое ее доказательство, принадлежащее Р. Радо.

Теорема 1. Пусть Е — непустое конечное множество и &= (Si, ..., Sm) — семейство непустых его подмножеств; тогда & имеет трансверсаль в том и только в том случае, если для любых k подмножеств Sі их объединение содержит по меньшей мере k элементов (1 ≤ k ≤ т).

Доказательство. Необходимость этого условия очевид­на. Для доказательства достаточности установим, что если одно из подмножеств (скажем, S1) содержит более одного элемента, то можно удалить один элемент из S1, не нарушив условия теоремы. Повторением этой процедуры мы добь­емся сведения задачи к тому случаю, когда каждое подмно­жество содержит только один элемент. Тогда утверждение станет очевидным.

Осталось обосновать законность этой «процедуры сведе­ния». Предположим, что S1 содержит элементы х и у, удале­ние каждого из которых нарушает условие теоремы. Тогда существуют подмножества А и В множества {2, 3, ..., т}, обладающие тем свойством, что

Но эти два неравенства приводят к противоречию, посколь­ку

Привлекательность этого доказательства в том, что оно проводится по существу лишь в один шаг в отличие от доказательства Халмоша — Вогена, которое предполагает исследование двух отдельных случаев. (Однако доказательство Радо труд­нее перевести на наглядный и привлекательный «мат­римониальный» язык!)

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

Следствие 1. В тех же обозначениях, что и выше, & имеет частичную трансверсаль мощности t тогда и только тогда, когда для любых k подмножеств Si их объединение содержит по меньшей мере

k + t — т элементов.

Доказательство. Требуемый результат можно получить, применив теорему 1 к семейству &' = (S1D, ... ...,SmD), где D — произвольное множество, не пересека­ющееся с Е и состоящее из т — t элементов. Заметим, что & имеет частичную трансверсаль мощности t тогда и только тогда, когда &' имеет трансверсаль.

Следствие 2. Если Е и & такие же, как и прежде, а X — любое подмножество из Е, то X содержит частичную трансверсаль мощности t для & тогда и только тогда, когда для каждого подмножества А множества {1, ..., т}

Доказательство. Достаточно применить предыдущее следствие к семейству &X= (S1∩X, …, Sm∩X).

УПРАЖНЕНИЯ

(1) Какие из следующих семейств подмножеств множества

Е = {1, ..., 5} имеют трансверсали:

(i) ({1}, {2, 3}, {1, 2}, {1, 3}, {1, 4, 5});

(ii) ({1, 2}, {2, 3}, {4 5}, {4, 5});

(iii) ({1, 3}, {2, 3} , {1, 2}, {3});

(iv) ({1,3,4}, {1,4, 5}, {2,3,5}, (2,4,5})?

(2) Пусть Е— множество букв в слове MATROIDS; сколько

трансверсалей имеет следующее семейство подмножеств из

Е: (STAR, ROAD, MOAT, RIOT, RIDS, DAMS, MIST)?

(3) Перепишите доказательство теоремы Холла, данное Халмошем и Вогеном, на языке теории трансверсалей; перепишите также доказательство Радо на языке (i) паросочетаний в дву­дольном графе; (ii) свадеб.

(3) Пусть А — данное подмножество множества Е и & — семей­ство непустых подмножеств из Е. Докажите, что трансверсаль для &, содержащая А, существует тогда и только тогда, когда (i) & имеет трансверсаль и (ii) А является частичной трансверсалью для &. (Решение этого упражнения, использующее теорию матроидов, будет дано далее)

(4) Пусть Е и & имеют обычный смысл; докажите, что если Т1 и Т2 — трансверсали для & и x — элемент из Т1, то существует элемент у из T2, обладающий тем свойством, что (Т1 — {x}){у} (множество, полученное из T1 заменой элемента х на у) тоже является трансверсалью для &.

(5) Рангом ρ(A) подмножества А из Е называется число элементов в наибольшей частичной трансверсали для семейства &, со­держащей А; покажите, что (i) 0≤ ρ(A) <|A|; (ii) если А В Е, то ρ(A) ≤ ρ (В);

(iii) для любых A,B E имеем ρ(A В) + ρ(A ∩В)≤ ρ(A) + ρ(В).

(6) Пусть Е — счетное множество, и пусть & = (S1, S2, ...) — счетное семейство непустых конечных подмножеств из Е. Определяя трансверсаль для & естественным образом, дока­жите (используя лемму Кёнига), что & имеет трансверсаль тогда и только тогда, когда для любых k подмножеств Si их объединение содержит по меньшей мере k элементов (для всех конечных k). На примере Е = {1, 2, 3, ...}, S1 = {E}, S2 = {1}, S3 = {2}, S4 = {3}, ... покажите, что этот ре­зультат перестает быть верным, если не все Si конечны.

1.5. Приложения теоремы Холла

В этом параграфе мы рассмотрим приложения теоремы Холла в четырех различных областях, а именно: (i) при пост­роении латинских квадратов; (ii) при исследовании одной проблемы, касающейся матриц из нулей и единиц; (iіі) при раскрашивании ребер двудольного графа; (iv) при изу­чении вопроса о существовании общей трансверсали для се­мейств подмножеств некоторого множества (будет вскрыта также связь этой задачи с задачами о составлении расписа­ний).

(i) Латинские квадраты. Латинским (т×п)-пря­моугольником называется (т×п)-матрица М = (тij), эле­ментами которой являются целые числа, удовлетворяющие условиям: (1) 1 ≤ mij ≤п, (2) все элементы в каждой строке и в каждом столбце различны. Заметим, что из усло­вий (1) и (2) следует, что т ≤ п; если т = п, то латинский прямоугольник называется латинским квадратом. К при­меру, на рис. 1 и 2 изображены латинский (3 × 5)-прямоугольник и латинский (5 × 5)-квадрат.

Рис. 1. Рис. 2.

Можно задать следующий вопрос: если дан латинский (т ×n)-прямо­угольник, где т < п, когда можно присоединить к нему п — т новых строк так, чтобы получился латинский квад­рат? Oтвет на этот вопрос: «всегда»!

Теорема 1. Пусть М — латинский (т×п)-прямоугольник, причем

т < п; тогда М можно расширить до латин­ского квадрата добавлением п — т новых строк.

Доказательство. Докажем, что М можно расширить до латинского

(т +1) × n-прямоугольника; повторяя эту процедуру, мы придем к латинскому квадрату.

Пусть Е — {1, 2, .... п) и & = (S1, ..., Sn), где через Si обозначено множество, состоящее из тех элементов мно­жества Е, которые не встречаются в i-м столбце матрицы М. Если мы сможем доказать, что & имеет трансверсаль, то тем самым мы докажем теорему, поскольку элементы этой трансверсали и образуют дополнительную строку. По тео­реме Холла достаточно доказать, что объединение любых k множеств Si содержит по меньшей мере k различных эле­ментов. А это очевидно, ибо любое такое объединение со­держит (п — m)k элементов (включая повторения), и если бы в нем было менее k различных элементов, то по крайней мере один из них повторялся бы более чем