Дискретная математика: графы и автоматы. Альпин Ю.А - 21 стр.

§ 5. Теорема о свадьбах, двудольные графы и (0,1)-матрицы               21


Вопрос: существует ли с.р.п.? Ответ: существует тогда и только тогда,
когда объединение любых k подмножеств (k = 1, . . . , m) содержит не
менее k элементов. Как это следует из теоремы Холла?
   4. Теорема Фробениуса–Кёнига и перманенты. В этом
пункте A = (aij ) — m×n-матрица с элементами 0 или 1. Любой набор
элементов a1j1 , a2j2 , . . . , amjm , где вторые индексы попарно различны,
называется диагональю матрицы. Если все элементы диагонали рав-
ны 1, то говорят, что диагональ положительна. Попросту говоря,
положительная диагональ — это набор m единичных элементов мат-
рицы, любые два из которых стоят в разных строках и столбцах.
    Лемма 1. Матрица A содержит положительную диагональ
тогда и только тогда, когда любые k строк (k = 1, 2, . . . , m) мат-
рицы A образуют матрицу, имеющую не менее k ненулевых столб-
цов.
      Д о к а з а т е л ь с т в о. Любая (0,1)-матрица A задает за-
дачу о свадьбах, если считать, что юноши перенумерованы числами
1, . . . , m, девушки — числами 1, . . . , n, и равенство aij = 1 озна-
чает, что i-й юноша знаком с j-й девушкой. Положительная диаго-
наль a1j1 , a2j2 , . . . , amjm определяет решение задачи: 1-го юношу же-
ним на j1 -й девушке и так далее. И наоборот, всякое решение зада-
чи о свадьбах определяет положительную диагональ. Заметим, что
j-я девушка имеет знакомого в множестве {i1 , . . . , ik } юношей тогда
и только тогда, когда j-й столбец матрицы, образованной строками
i1 , . . . , ik матрицы A, содержит единицу. Так что у этих k юношей
в совокупности ровно столько знакомых девушек, сколько ненулевых
столбцов в соответствующей матрице. Теперь уже ясно, что наша лем-
ма — переформулировка теоремы Холла. ¤
   Лемма 2. Следующие свойства матрицы A эквивалентны:
   1) любая подматрица, составленная из k строк (k = 1, . . . , m),
имеет не меньше, чем k ненулевых столбцов;
   2) сумма размеров любой нулевой подматрицы не превышает n.
    Д о к а з а т е л ь с т в о. Если верно 1), то любая нулевая подматри-
ца, расположенная в k строках, имеет не больше, чем n − k столбцов.
Следовательно, сумма её размеров не больше, чем k + (n − k) = n.
Если же 1) не выполнено и подматрица, составленная из некоторых
k строк, имеет l < k ненулевых столбцов, то в этих же строках рас-
положена нулевая подматрица с суммой размеров k + (n − l) > n. ¤
    Из лемм 1 и 2 сразу следует