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

п — т раз, что невозможно.

(ii) (0, 1)-матрицы. Другой подход к изучению трансверсалей семейства & = (Si, ..., Sm) непустых подмножеств множества

Е={е1 ..., еп} состоит в исследовании матри­цы инциденций этого семейства, т. е. (т×п)-матрицы А =(aij), в которой аij = 1, если еj Si, и aij = 0 в противном случае. (Любую такую матрицу, все элементы которой равны 0 или 1, мы называем (0,1)-матрицей.) Назо­вем словарным рангом матрицы А наибольшее число единиц в А, никакие две из которых не лежат в одной и той же строке или в одном и том же столбце. Тогда & имеет трансверсаль в том и только в том случае, если словарный ранг матрицы А равен т. Более того, словарный ранг матрицы А равен в точности числу элементов частичной трансверсали, обладающей наибольшей возможной мощностью. В качест­ве второго приложения теоремы Холла докажем сейчас из­вестный результат о

(0, 1)-матрицах, называемый теоремой Кёнига—Эгервари.

Теорема 2 (Кёниг—Эгервари). Словарный ранг (0, 1)-матрицы А равен минимальному числу μ строк и столбцов, которые в совокупности содержат все единицы из А.

Замечание. В качестве иллюстрации этой теоремы рассмот­рим матрицу, приведенную на рис. 3, которая является матрицей инциденций семейства ?, второго из описанных в разделе 1.4.

Рис. 3

Ясно, что и ее словарный ранг, и число μ равны четырем.

Доказательство. Очевидно, что словарный ранг не мо­жет превосходить числа μ. Чтобы доказать равенство, можно без потери общности предположить, что все единицы из А содержатся в r строках и s столбцах (где r +s = μ) и что строки и столбцы расположены в таком порядке, что в ниж­нем левом углу матрицы А находится

(т — r) × (п — s)-подматрица, полностью состоящая из нулей (рис. 4).

Pис. 4

Если i ≤r, то определим Si как множество целых чисел j ≤ п — s, таких, что аij = 1. Нетрудно проверить, что объединение любых k множеств Si содержит по меньшей мере k целых чисел; поэтому семейство

& = (S1, ..., Sr) имеет трансверсаль. Отсюда следует, что подматрица М из А содержит множество из r единиц, никакие две из которыхне принадлежат одной и той же строке или одному и тому же столбцу. Аналогично, матрица N содержит множество из s единиц, обладающих тем же свойством. Таким образом, мат­рица А содержит множество из

r + s единиц, никакие две из которых не принадлежат одной и той же строке или одно­му и тому же столбцу. Тем самым показано, что μ не пре­восходит словарного ранга.

Мы доказали теорему Кёнига — Эгервари с помощью теоремы Холла, а доказательство теоремы Холла g помощью теоремы Кёнига — Эгервари и того проще (см. упр. 3). Следовательно, эти две теоремы в некотором смыс­ле эквивалентны. Позднее в этой главе мы докажем теорему Менгера и теорему о максимальном потоке и минимальном разрезе, каждая из которых тоже эквивалентна теореме Холла.

(ііі) Реберная раскраска графов. Ранее мы установили, что если G — полный двудольный граф, наибольшая из степеней вершин которого равна ρ, то его хроматический класс равен ρ. Используя один результат из этой главы, покажем, что сформулированное утверждение справедли­во и для произвольного двудольного графа.

Теорема 3. Если G — двудольный граф, наибольшая из степеней вершин которого равна ρ, то χe(G) = ρ.

Доказательство Известно, что су­ществует двудольный граф

G' = G'(V1, V2), который регу­лярен степени ρ и содержит G в качестве подграфа, причем | V1 | = | V2 |. Известно, что G' имеет совершен­ное паросочетание; заметим, что это паросочетание включает каждую вершину графа G' и что в этом паросочетании любая вершина из G степени ρ соответствует другой вершине из G.

Чтобы доказать, что хроматический класс графа G равен ρ, достаточно взять это паросочетание в G' и окрасить пер­вым цветом те ребра из G', которые лежат в G и инцидентны вершине из G степени ρ. Тогда оставшаяся часть графа G будет двудольным графом с наибольшей из степеней вершин, равной ρ — 1, и мы можем по индукции установить осущест­вимость раскраски этой части графа G в остальные ρ — 1 цветов. Тем самым доказательство завершено.

(iv) Общие трансверсали. В заключение этого параграфа коротко обсудим вопрос об общих трансверсалях. Если Е— непустое конечное множество, а & = (Sl, ..., Sm) и F =(T1, ..., Тт) — два семейства его непустых подмножеств, то интересно знать, когда существует общая трансверсаль для & и F, т. е. множество, состоящее из т различных эле­ментов множества Е и являющееся трансверсалью и для &, и для F. Рассмотрим, например, задачу о составлении рас­писаний. Пусть Е — множество отрезков времени, в кото­рые могут читаться те или иные лекции; обозначим через Si множества отрезков времени, в которые данные т про­фессоров желают читать лекции, а через Тi — множества отрезков времени, в которые свободны т лекционных ауди­торий. Тогда, найдя общую трансверсаль для & и F, мы смо­жем предоставить каждому профессору свободную аудито­рию в удобное для него время.

Сформулируем необходимое и достаточное условие для того, чтобы два семейства & и F имели общую трансверсаль; заметим, что теорема 4 сводится к теореме Холла, если положить Тj = Е для 1≤ j≤ т.

Теорема 4. Пусть Е — непустое конечное множест­во, а &=(S1, ..., Sm) и F = (Т1, ..., Тт) — два семейства его непустых подмножеств. Тогда & и F имеют общую транс­версаль в том и только в том случае, если для всех подмно­жеств А и В множества {1, 2, ..., т}

Набросок доказательства. Рассмотрим семейство U={Ui} подмножеств множества Е {1, ..., т} (считаем, что Е и {1, ..., т} не пересекаются), где множеством индек­сов также является Е{1, ..., т} и где Ui = Si, если i {1, .... т}, и Ui= {i} {j : i Tj), если i E.

Нетрудно проверить, что & и F имеют общую трансверсаль тогда и только тогда, когда имеет трансверсаль семей­ство U. Применяя затем теорему Холла к семейству U, получаем нужный результат.

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

УПРАЖНЕНИЯ

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

(2) Докажите, что существует по крайней мере п!(п — 1)! ...1! латинских (n×n)-квадратов. Получите соответствующую нижнюю оценку для числа латинских (т×п)-прямоуголь­ников.

(3) Покажите, как с помощью теоремы Кёнига — Эгервари вывес­ти теорему Холла.

(4) С помощью теоремы 4 покажите, что если G — конечная группа, Н — ее подгруппа и G=x1H х2Н ... xmH=Ну1Ну2… Нут—левостороннее и правосторонее разложения группы G по подгруппе Н, то в G существуют эле­менты z1, ..., zт, обладающие тем свойством, что

(5) Докажите, что если А является (0, 1)-матрицей, в которой сумма элементов каждой из строк или каждого из столбцов равна k, то ее можно представить в виде суммы k матриц, каж­дая из которых содержит ровно одну единицу в каждой строке и в каждом столбце.