Двудольные графы и теорема Холла: Математика идеальных совпадений
Существует особый класс графов, который естественным образом описывает системы, где объекты разделены на две непересекающиеся группы, и связи возможны только между представителями разных групп. Студенты и университеты, таксисты и пассажиры, рабочие и станки, покупатели и товары. В дискретной математике такие структуры называются двудольными графами. Анализ таких графов позволяет решать сложнейшие логистические и экономические задачи распределения ресурсов.
Математически двудольный граф (Bipartite graph) — это граф, множество вершин которого можно разбить на две изолированные части (доли) так, что каждое ребро графа соединяет вершину из первой части с вершиной из второй. Внутри одной доли нет ни одного ребра. Интересное свойство: граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. Это значит, что его хроматическое число равно ровно 2 (его всегда можно раскрасить лишь двумя цветами).
Центральной задачей на двудольных графах является поиск паросочетания (Matching). Паросочетание — это набор ребер, не имеющих общих вершин. Иными словами, каждый объект из первой доли связывается не более чем с одним объектом из второй доли. Например, один рабочий может быть назначен только на один станок, и за одним станком может работать только один рабочий.
Идеальной ситуацией является совершенное (полное) паросочетание — когда абсолютно все вершины из обеих долей обеспечены парами. Но как, не перебирая все варианты, узнать, существует ли в данном графе полное паросочетание? Английский математик Филип Холл в 1935 году доказал знаменитую теорему, известную как Условие Холла (или "Теорема о свадьбах").
В популярной формулировке теорема звучит так: представим множество юношей и множество девушек, где ребра означают взаимную симпатию. Чтобы можно было переженить всех юношей так, чтобы каждый женился на симпатичной ему девушке, необходимо и достаточно, чтобы любая выбранная подгруппа юношей (состоящая из k человек) симпатизировала в совокупности как минимум k девушкам. Если найдутся 3 друга, которым нравятся в сумме только 2 девушки — переженить всех без конфликтов математически невозможно.
Для практического поиска наибольшего паросочетания в невзвешенных двудольных графах применяется быстрый алгоритм Куна (Kuhn's algorithm), основанный на поиске чередующихся цепей. Если ребра имеют вес (например, станки приносят разную прибыль в зависимости от того, какой рабочий за ними стоит), задача превращается в классическую "Задачу о назначениях", которая изящно решается Венгерским алгоритмом за время O(V^3).
