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

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


столбцы — последние s позиций, так что матрица имеет вид
                              µ         ¶
                            r     B ∗
                      A=
                          m−r     0 C
                                       n−s   s

Докажем, что матрица B содержит r единиц, любые две из которых
стоят на разных линиях. Допустим противное. Тогда по лемме 1 суще-
ствуют k строк матрицы B, все единицы которых стоят в l столбцах,
где l < k. Удалив номера этих k строк из списка линий и добавив
номера этих l столбцов, снова получим набор покрывающих линий
в количестве (r − k) + (s + l) = r + s − (k − l) < r + s = µ, что
противоречит минимальности µ.
    Теперь докажем, что подматрица C содержит s единиц в попар-
но разных линиях. Вследствие леммы 3 противное означало бы, что
имеются k столбцов матрицы C, все единицы которых находятся в p
строках, где p < k. Удалив номера этих k столбцов из списка покры-
вающих линий и добавив номера этих p строк, получим набор покры-
вающих линий числом, меньшим µ, — противоречие. Таким образом,
доказано существование r + s = µ(A) единиц, любые две из которых
стоят на разных линиях, значит, ρ(A) > µ(A). Учитывая полученное
ранее противоположное неравенство, заключаем, что ρ(A) = µ(A). ¤