3.09.2. Теорема Холла о свадьбах

Пусть А – подмножество множества вершин V(G) графа G. Множество всех вершин графа G, каждая из которых смежна с некоторой вершиной из А, называется Окружением множества А и обозначается NA.

Теорема. В двудольном графе G с долями V и U существует совершенное паросочетаиие V на U тогда и только тогда, когда для любого АV мощность |NA| ≥ .

Доказательство. Действительно, если для какого-то АV условие |NA| ≥ не выполняется, т. е. (пользуясь терминологией задачи о свадьбах) rкакое-то множество юношей (предположим K человек) знакомы в совокупности меньше, чем с K девушками, то уже этих K юношей нельзя всех женить, тем более -- всех юношей множества V. Таким образом необходимость данного условия очевидна.

Докажем достаточность. Пусть АV условие |NA| ≥ выполняется.

Возможны два случая.

а) Любые K юношей знакомы в совокупности не менее, чем с K+1 девушкой. Тогда, рассуждая по индукции по числу юношей (база индукции очевидно имеется) женим произвольного юношу на знакомой ему девушке. Для остальных юношей, количество знакомых девушек уменьшается не более, чем на 1. Значит, для любого числа K любые K юношей будут знакомы не менее, чем с K девушками. По индукционному предположению их можно женить.

б) Существует K юношей, у которых ровно K знакомых девушек (K < N = |A|). По предположению индукции их можно женить. Остается N-k юношей. Для них по-прежнему будет выполняться условие, что любые L из них знакомы не менее, чем с L девушками. Действительно, если бы это было не так, то соответствующие L Юношей вместе с предыдущими K имели бы в совокупности не менее L+K знакомых девушек, что противоречит условию теоремы. Значит, и оставшихся N-k юношей можно женить по индукционному предположению.

< Предыдущая		Следующая >