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

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


   Теорема 1. Факторграф связного графа по разбиению на листы
есть дерево.
    Д о к а з а т е л ь с т в о. Вследствие предложения 2 нужно
лишь убедиться, что факторграф не содержит циклов. Предположим
противное: существует цикл листов L1 , . . . , Lk , L1 и пусть e1 , . . . , ek
— мосты исходного графа, последовательно соединяющие эти листы.
Тогда, ввиду связности листов, в исходном графе должен быть цикл,
содержащий эти мосты. Но это противоречит предложению 2. ¤
    Пример 1. На рис. 9 изображены граф с семью листами и его
факторграф по разбиению на листы.




                                    Рис. 9


   Замечание 1. Говоря неформально, факторграф является
упрощённой моделью графа. В зависимости от выбора разбиения эта
модель может содержать бо̀льшую или меньшую информацию об ис-
ходном графе. Полезно сравнить в этом отношении факторграфы из
упражнения 1 и из теоремы 1.

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

   1. Теорема о свадьбах. Одна из наиболее известных задач
дискретной математики часто формулируется в шутливой форме:
имеется множество юношей и множество девушек, и для любых юно-
ши и девушки известно, знакомы ли они. Задача: можно ли женить
каждого юношу на знакомой ему девушке? Пусть количество юношей
равно m, девушек — n.
    Теорема 1 (Ф. Холл, 1935). Задача о свадьбах разрешима то-
гда и только тогда, когда любые k юношей (k = 1, . . . , m) знакомы
в совокупности не менее, чем с k девушками.