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

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


    Д о к а з а т е л ь с т в о. Необходимость почти очевидна: если неко-
торые k юношей знакомы в совокупности меньше, чем с k девушками,
то им не хватит невест и задача в целом неразрешима. Достаточность
доказывается индукцией по числу юношей. При m = 1 утверждение
очевидно. Предположим, что оно верно для числа юношей, меньшего
m, и докажем его для m юношей. Возможны два случая.
    1. Условие теоремы выполнено “с избытком”: любые k юношей
(k 6 m − 1) знакомы не меньше, чем с k + 1 девушками. Тогда женим
какого-нибудь юношу на знакомой ему девушке. Для остальных m−1
юношей и n − 1 девушек условие теоремы выполнено и по предполо-
жению индукции их можно женить на знакомых девушках.
    2. Имеется k юношей (k 6 m−1), знакомых в совокупности ровно
с k девушками. По предположению индукции этих юношей можно
женить. Если мы теперь докажем, что любые p из остальных m − k
юношей знакомы не меньше, чем с p из остальных n − k девушек,
то и для них по предположению индукции задача будет разрешимой.
Допустим противное: среди оставшихся есть p юношей, знакомых в
совокупности лишь с q < p девушками из оставшихся. Но тогда во
всём множестве юношей имеется k + p юношей, знакомых лишь с
k + q девушками, причем k + q < k + p. Это противоречие завершает
доказательство теоремы. ¤
    В следующих параграфах показано, что задача о свадьбах и тео-
рема Холла допускают формулировку и в других, на первый взгляд
весьма отличных, терминах. При этом математическое их содержание
сохраняется. Заметим, что каждая из этих формулировок имеет хож-
дение в своей области дискретной математики не может быть сочтена
“лишней”.
    2. Паросочетания в двудольных графах. Граф называет-
ся двудольным, если его множество вершин V можно так разбить на
два подмножества V1 и V2 , что любое ребро графа соединяет вершины
из разных подмножеств. Совершенным паросочетанием из V1 в V2 в
двудольном графе называется такая инъекция ϕ : V1 → V2 что вер-
шины v и ϕ(v) смежны для всех v ∈ V1 . Вопрос: при каких условиях
существует совершенное паросочетание? Выведите из теоремы Хол-
ла, что оно существует тогда и только тогда, когда любые k вершин
из V1 имеют в совокупности не меньше, чем k смежных вершин.
    3. Системы различных представителей. Рассмотрим се-
мейство S1 , . . . , Sm подмножеств конечного множества E. Говорят,
что множество {s1 , . . . , sm } ⊆ E является системой различных пред-
ставителей (с.р.п.) для данного семейства, если si ∈ Si , i = 1, . . . , m.