3.3.2 — оптимальное сопоставление двух групп3.3.2 — optimally pairing up two groups
Двудольный граф — вершины делятся на две группы, рёбра идут только между группами, никогда внутри одной. Огромный класс реальных задач ("кто с кем совместим") сводится именно к такому графу, а вопрос "как сопоставить максимум пар" — это частный случай максимального потока из 3.3.1 со своими специализированными, более быстрыми алгоритмами.A bipartite graph splits its vertices into two groups, with edges running only between the groups, never within one. A huge class of real problems ("who's compatible with whom") reduces to exactly this kind of graph, and the question "how do you pair up the maximum number" is a special case of max-flow from 3.3.1, with its own specialized, faster algorithms.
Двудольный граф (bipartite graph) — граф, вершины которого можно разбить на два непересекающихся множества L и R так, что каждое ребро соединяет вершину из L с вершиной из R (никогда L-L или R-R). Паросочетание (matching) — подмножество рёбер, никакие два из которых не имеют общей вершины (каждая вершина занята не более чем в одном ребре паросочетания). Максимальное паросочетание — паросочетание с наибольшим возможным числом рёбер.A bipartite graph is a graph whose vertices can be split into two disjoint sets L and R such that every edge connects a vertex in L to a vertex in R (never L-L or R-R). A matching is a subset of edges no two of which share a vertex (every vertex is used by at most one matching edge). A maximum matching is a matching with the largest possible number of edges.
каждая вершина участвует не более чем в одном сплошном ребре — определение паросочетанияevery vertex appears in at most one solid edge — the definition of a matching
Ключевое понятие — увеличивающая цепь (augmenting path): путь, начинающийся и заканчивающийся в непокрытых (не участвующих в текущем паросочетании) вершинах, где рёбра чередуются — не входит в паросочетание, входит, не входит, входит... Если такая цепь найдена, "переключение" всех её рёбер (то, что было в паросочетании, убрать; то, что не было, добавить) увеличивает размер паросочетания ровно на 1. Теорема Бержа гарантирует обратное: паросочетание максимально тогда и только тогда, когда увеличивающих цепей относительно него больше не существует.The key concept is an augmenting path: a path starting and ending at uncovered (not part of the current matching) vertices, where edges alternate — not in the matching, in the matching, not in, in... If such a path is found, "flipping" all its edges (remove what was in the matching, add what wasn't) increases the matching's size by exactly 1. Berge's theorem guarantees the converse: a matching is maximum if and only if no augmenting path exists relative to it.
Алгоритм Куна — прямое применение этого факта: для каждой непокрытой вершины из L запускаем DFS-поиск увеличивающей цепи (пытаемся найти для неё пару напрямую, а если её текущий "кандидат" в R уже занят — рекурсивно пытаемся "передвинуть" того, кто его занимает, на другую вершину). Повторяем для всех вершин L. Сложность O(V·E) — каждый запуск DFS — O(E), запусков — O(V).Kuhn's algorithm is a direct application of this fact: for every uncovered vertex in L, run a DFS search for an augmenting path (try to pair it directly, and if its candidate in R is already taken, recursively try to "bump" whoever holds it onto a different vertex). Repeat for every vertex in L. Complexity is O(V·E) — each DFS run is O(E), and there are O(V) runs.
// matchR[v] = вершина из L, сопоставленная с v из R, или -1// matchR[v] = the L-vertex matched to R-vertex v, or -1
bool tryKuhn(int u, const std::vector<std::vector<int>>& adj,
std::vector<bool>& used, std::vector<int>& matchR) {
for (int v : adj[u]) {
if (used[v]) continue;
used[v] = true;
// v свободна, или её текущую пару можно передвинуть в другое место// v is free, or its current partner can be moved elsewhere
if (matchR[v] == -1 || tryKuhn(matchR[v], adj, used, matchR)) {
matchR[v] = u;
return true;
}
}
return false;
}Алгоритм Хопкрофта-Карпа ускоряет ту же идею до O(E√V): вместо поиска увеличивающих цепей по одной (как Кун), он находит через BFS кратчайшую длину увеличивающей цепи, затем через DFS ищет сразу максимальный набор непересекающихся увеличивающих цепей этой длины за один проход (аналогично идее "слоистой сети" в алгоритме Диница из 3.3.1) — доказано, что нужно всего O(√V) таких раундов до достижения максимума.The Hopcroft-Karp algorithm speeds up the same idea to O(E√V): instead of finding augmenting paths one at a time (like Kuhn), it uses BFS to find the shortest augmenting-path length, then DFS to find a maximal set of vertex-disjoint augmenting paths of that length in one pass (similar to the "layered network" idea in Dinic's algorithm from 3.3.1) — it's proven that only O(√V) such rounds are needed to reach the maximum.
Оба алгоритма выше решают задачу без весов — "максимальное число пар", все рёбра равнозначны. Венгерский алгоритм решает более общую задачу — взвешенное паросочетание: у каждого ребра есть стоимость (или выгода), и нужно найти совершенное паросочетание с минимальной суммарной стоимостью (или максимальной выгодой) — например, "какого сотрудника на какую задачу назначить, чтобы суммарная эффективность была максимальна". Работает через итеративную корректировку "потенциалов" вершин, приводящую к системе рёбер нулевой приведённой стоимости, среди которых ищется обычное (невзвешенное) максимальное паросочетание. Классическая сложность — O(V³).Both algorithms above solve the unweighted problem — "maximum number of pairs," all edges equal. The Hungarian algorithm solves the more general problem — weighted matching: every edge has a cost (or benefit), and the goal is a perfect matching with minimum total cost (or maximum benefit) — e.g., "which employee should be assigned to which task to maximize total efficiency." It works by iteratively adjusting vertex "potentials," arriving at a system of zero-reduced-cost edges, among which an ordinary (unweighted) maximum matching is found. Its classic complexity is O(V³).
Студенты — L, проектные слоты — R, ребро есть, если студент имеет нужный набор навыков для проекта. Задача "занять максимум слотов подходящими студентами" — невзвешенное максимальное паросочетание, ровно как в базовом примере учебников.Students are L, project slots are R, an edge exists if the student has the right skill set for the project. "Fill the maximum number of slots with suitable students" is an unweighted maximum matching, exactly the textbook base case.
Курьеры — L, заказы — R, вес ребра — расстояние или время доставки. Минимизация суммарного времени доставки при назначении "один курьер — один заказ" — классическая взвешенная задача о назначениях, решаемая венгерским алгоритмом в реальных диспетчерских системах доставки.Couriers are L, orders are R, the edge weight is distance or delivery time. Minimizing total delivery time under a "one courier — one order" assignment is the classic weighted assignment problem, solved by the Hungarian algorithm in real delivery-dispatch systems.
Национальная программа распределения врачей-резидентов по больницам (NRMP в США) — двудольный граф врачи/больницы с предпочтениями с обеих сторон; хотя решается специализированным алгоритмом Гейла-Шепли (устойчивое паросочетание, не просто максимальное), сама постановка — прямое расширение темы этой страницы.The US National Resident Matching Program pairing medical residents with hospitals is a bipartite graph of doctors/hospitals with preferences on both sides; while it's solved by the specialized Gale-Shapley algorithm (stable matching, not just maximum), the framing itself is a direct extension of this page's topic.
Экзамены — L, тайм-слоты — R, ребро есть, если экзамен может быть проведён в этом слоте (нет конфликта преподавателя/аудитории). Максимальное паросочетание даёт наибольшее число экзаменов, которые можно провести без конфликтов за один проход планирования.Exams are L, time slots are R, an edge exists if the exam can run in that slot (no instructor/room conflict). A maximum matching gives the largest number of exams that can be scheduled conflict-free in one planning pass.
Теорема Кёнига связывает максимальное паросочетание в двудольном графе с минимальным вершинным покрытием (наименьшим набором вершин, покрывающим все рёбра) — применяется, например, при выборе минимального набора тестовых сценариев, покрывающих все пары "функция-зависимость», которые нужно проверить.König's theorem relates a bipartite graph's maximum matching to its minimum vertex cover (the smallest set of vertices touching every edge) — applied, for instance, when choosing the minimum set of test scenarios covering every "function-dependency" pair that needs checking.
На плотном двудольном графе (E ≈ V²) сложность Куна вырождается в O(V³) — при V в районе нескольких тысяч это уже слишком медленно. Хопкрофт-Карп с его O(E√V) — не "опциональная оптимизация ради красоты", а необходимость на реальных масштабах, где Кун просто не успеет отработать за разумное время.On a dense bipartite graph (E ≈ V²), Kuhn's algorithm's complexity degenerates to O(V³) — with V in the low thousands, that's already too slow. Hopcroft-Karp's O(E√V) isn't "an optional optimization for elegance" — it's a necessity at real-world scale, where Kuhn's algorithm simply won't finish in reasonable time.
Максимальное паросочетание — наибольшее возможное по размеру, но может оставлять непокрытые вершины, если |L| ≠ |R| или граф неполный. Совершенное паросочетание покрывает абсолютно все вершины — существует не всегда (например, если |L| ≠ |R|, оно невозможно в принципе). Алгоритм Куна/Хопкрофта-Карпа находит максимальное, а не гарантированно совершенное — предполагать иначе означает неверно интерпретировать результат.A maximum matching is the largest possible by size, but may leave vertices uncovered if |L| ≠ |R| or the graph is incomplete. A perfect matching covers absolutely every vertex — it doesn't always exist (e.g., if |L| ≠ |R|, it's impossible by definition). Kuhn's/Hopcroft-Karp's algorithm finds the maximum, not a guaranteed-perfect one — assuming otherwise misreads the result.
Максимизация ЧИСЛА пар (Кун) и минимизация СУММАРНОЙ стоимости назначений (венгерский алгоритм) — разные задачи с разными алгоритмами. Использование Куна там, где на самом деле важна стоимость назначения (курьер А ближе к заказу, чем курьер Б), даст технически валидное, но неоптимальное с точки зрения бизнеса паросочетание.Maximizing the NUMBER of pairs (Kuhn) and minimizing the TOTAL cost of assignments (the Hungarian algorithm) are different problems with different algorithms. Using Kuhn's algorithm where assignment cost actually matters (courier A is closer to the order than courier B) produces a technically valid but business-suboptimal matching.