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

22                                       Глава 1. Неориентированные графы


   Теорема 2 (Фробениус–Кёниг). Пусть A — (0, 1)-матрица
размеров m × n (m 6 n). Она содержит положительную диагональ
тогда и только тогда, когда сумма размеров любой её нулевой под-
матрицы не больше n.
    Перманентом матрицы A = (aij ) размеров m × n, m 6 n, назы-
вается число              X
                  per A =   a1j1 a2j2 . . . amjm ,
где суммирование ведется по всевозможным последовательностям
{j1 , . . . , jm } различных элементов из множества {1, 2, . . . , n}. Дока-
жите, что перманент (0,1)-матрицы равен количеству положительных
диагоналей или, в “свадебных” терминах, — количеству решений за-
дачи о свадьбах.
    5. Граничный ранг (0,1)-матрицы размеров m × n опреде-
ляется как максимальное число ρ(A) единиц, любые две из которых
стоят в разных строках и столбцах. Если считать, что матрица A
определяет задачу о свадьбах, то её граничный ранг равен макси-
мально возможному числу бракосочетаний, заключенных между зна-
комыми. Ясно, что ρ(A) 6 min(m, n). Определим ещё одну характе-
ристику (0,1)-матриц.
    Ранг покрытия µ(A) равен минимальному числу линий (строк и
столбцов) матрицы, содержащих (покрывающих) все единицы матри-
цы A.
    Мы докажем, что граничный ранг и ранг покрытия совпадают,
но прежде приведем лемму, которую можно интерпретировать как
условие разрешимости задачи о свадьбах для девушек. Она не требует
отдельного доказательства.
    Лемма 3. Пусть A — (0, 1)-матрица размеров m×n, где m > n.
В ней можно найти n единиц в попарно разных строках и столбцах
тогда и только тогда, когда любые k столбцов A (k = 1, . . . , n)
образуют подматрицу, в которой ненулевых строк не меньше k.
   Теорема 3 (Кениг–Эгервари, 1931). Для любой (0, 1)-мат-
рицы A граничный ранг и ранг покрытия совпадают: ρ(A) = µ(A).
   Д о к а з а т е л ь с т в о. Если матрица содержит ρ единиц,
любые две из которых находятся на разных линиях (то есть, в разных
строках и разных столбцах), то ясно, что для покрытия матрицы
требуется не менее ρ линий. Поэтому ρ(A) 6 µ(A).
   Докажем, что ρ(A) > µ(A). Пусть в минимальный список по-
крывающих линий входят r строк и s столбцов, причем можно счи-
тать (подумайте, почему), что строки занимают верхние r позиций, а