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

Следствие Если и такие же, как и прежде, а — любое подмножество из , то содержит частичную трансверсаль мощности для тогда и только тогда, если для каждого подмножества множества

Доказательство Достаточно применить предыдущее следствие к семейству .

Приложение теории трансверсалей

Используются понятия трансверсалей, на основании чего доказывается теорема о модификации латинского прямоугольника. Вводятся определения -матрицы, формулируются и доказываются теоремы Кенига-Эгервари и об общей трансверсали.

Теорема Пусть латинский -прямоугольник, причем, ; тогда можно расширить до латинского квадрата добавлением новых строк.

Доказательство Докажем, что можно расширить до латинского -прямоугольника; повторяя эту процедуру, мы придем к латинскому квадрату.

Пусть и , где через обозначено множество, состоящее из тех элементов множества , которые не встречаются в -м столбце матрицы . Если мы сможем доказать, что имеет трансверсаль, то тем самым мы докажем теорему, поскольку элементы этой трансверсали и образуют дополнительную строку. По теореме Холла достаточно доказать, что объединение любых множеств содержит по меньшей мере различных элементов. А это очевидно, ибо любое такое объединение содержит элементов (включая повторения), значит, по крайней мере, один из них повторялся бы более чем раз, что невозможно.

Определение (0,1) матрицы или матрицы инциденций. Другой подход к изучению трансверсалей семейства непустых подмножеств множества состоит в исследовании -матрицы , в которой , если , и в противном случае. (Любую такую матрицу, все элементы которой равны или , мы называем -матрицей) этого семейства.

Определение словарного ранга. Назовем словарным рангом матрицы наибольшее число единиц в , никакие две из которых не лежат в одной и той же строке или в одном и том же столбце. Тогда имеет трансверсаль в том и только в том случае, если словарный ранг матрицы равен . Более того, словарный ранг матрицы равен в точности числу элементов частичной трансверсали, обладающей наибольшей возможной мощностью. В качестве второго приложения теоремы Холла рассмотрим известный результат о -матрицах, называемой теоремой Кенига-Эгервари.

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

Замечание В качестве иллюстрации этой теоремы рассмотрим матрицу

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

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

Если , то определим как множество целых чисел , таких, что . Нетрудно проверить, что объединение любых множеств содержит по меньшей мере целых чисел; поэтому семейство имеет трансверсаль. Отсюда следует, что подматрица из содержит множество из единиц, никакие две из которых не принадлежат одной и той же строке или одному и тому же столбцу. Аналогично, матрица содержит множество из единиц, обладающих тем же свойством. Таким образом, матрица содержит множество из единиц, никакие две из которых не принадлежат одной и той же строке или одному и тому же столбцу. Тем самым показано, что не превосходит словарного ранга.