Ниже приведены ключевые результаты, доказательства и алгоритмы по двудольности и по нахождению максимального паросочетания $восновном—длядвудольныхграфов,супоминаниемобщихслучаев$.

1) Критерий двудольности $формулировкаидоказательство$

Определение. Неориентированный граф G = $V,E$ называется двудольным, если множество вершин V можно разбить на два непересекающихся подможества L и R так, что каждое ребро имеет концы в разных частях $нетрёбервнутриLивнутриR$.Критерий: граф G двудолен ⇔ G не содержит циклов нечётной длины $т.е.несодержитпростогоцикласнечётнымчисломрёбер$.

Доказательство.
$a$ Если G двудолен, то в нем нет нечётных циклов. Действительно, любое ребро меняет часть $L\leftrightarrow R$, поэтому при обходе цикла длина цикла равна числу переходов между частями и потому должна быть чётной.

$b$ Обратно, если G не содержит нечётных циклов, то G двудолен. Построим двудольность следующим образом: для каждой компоненты связности запустим BFS $илиDFS$ из произвольной вершины s и пометим вершины по уровню $расстояниювребрахотs$. Отнесём вершины чётных уровней в L, нечётных — в R. Если бы существовало ребро $u,v$ между вершинами одинаковой парности уровней, то это давало бы цикл нечётной длины: путь s→u длины d, ребро $u,v$, и путь v→s длины d' $всвязномслучаеd^{\prime }=d\pm 1$, в сумме — нечётный цикл. Но по предположению таких циклов нет, поэтому раскраска возможна и даёт разбиение L,R. Таким образом G двудолен.

2) Алгоритм проверки двудольности $эффективный$

Идея: попытка "2-раскраски" графа. Для каждого не посещённого компонента запустить BFS/DFS, присваивая стартовой вершине цвет 0, соседям — цвет 1, их соседям — цвет 0 и т.д. Если в процессе найдём ребро между вершинами одного цвета — граф не двудолен; иначе — двудолен.Псевдокод $BFS$:
Инициализировать color$$v$$ = UNCOLORED для всех v.Для каждой вершины v, если color$$v$$ == UNCOLORED:
a) color$$v$$ = 0; положить v в очередь Q.
b) Пока Q не пусто: извлечь u; для каждого соседa w:
если color$$w$$ == UNCOLORED: color$$w$$ = 1 - color$$u$$; положить w в Q;иначе если color$$w$$ == color$$u$$: вернуть "не двудолен".Если проверки прошли — вернуть "двудолен" и разбиение по color.Сложность: O$|V|+|E|$ по времени и O$|V|$ по памяти $стандартнаясложностьобходаграфа$.

3) Понятия паросочетания и теорема Берже $augmentingpath$

Паросочетание M ⊆ E — множество попарно несмежных рёбер $вершинапринадлежитнеболееодномуребруизM$.Паросочетание максимального размера $максимальноепомощности$ — такое M, что нет другого паросочетания бoльшего размера.Augmenting path $расширяющийпуть$ относительно паросочетания M — простой путь, концы которого не покрыты M $свободныевершины$, и рёбра на пути чередуются: не в M, в M, не в M, ... $начинаетсяизаканчиваетсяребромвнеM$.Теорема Берже: паросочетание M является максимальным ⇔ в графе нет расширяющего пути относительно M.

Краткое доказательство.

Если существует расширяющий путь P, то можно увеличить мощность паросочетания, взяв симметрическую разность M' = M Δ P $т.е.заменитьвPвсерёбраMнарёбравнеMинаоборот$. Так как концы P свободны, |M'| = |M| + 1, значит M не был максимальным.Обратно, если расширяющего пути нет, то нельзя увеличить |M| на 1. Предположим, что существует более сильное паросочетание M' (|M'| > |M|). Рассмотрим симметрическую разность M Δ M' — это набор путей и циклов, в которых рёбра чередуются; в этих компонентах количество рёбер из M' превышает количество из M в сумме, значит там есть путь с концами свободными относительно M — расширяющий путь. Противоречие. Следовательно M максимальное.

4) Нахождение максимального паросочетания в двудольном графе

Общие подходы:
a) Наивный "поиск увеличивающего пути" $Kuhn$: из каждой свободной вершины левой части запускают DFS для поиска свободной правой вершины по альтернирующим путям, при удаче увеличивают matching на 1. Если при каждой попытке пробегать весь граф, сложность в худшем случае O$|V|<em>|E|$ $точнееO(|L|</em>E)$, часто работоспособно на практике для средних по размеру разреженных графов.
b) Hopcroft–Karp $оптимальныйпотеоретическойоценкедляб.г.$. Работает уровнями и находит одновременно множество вершин-вершиной параллельных кратчайших увеличивающих путей.

Идея Hopcroft–Karp:

Пока существует путь увеличения:
a) BFS из всех свободных левых вершин строит слоёвую ориентированную сеть $levels$, останавливаясь на свободных правых вершинах, таким образом находит расстояние до ближайших свободных правых вершин $этоминимальнаядлинаувеличивающегопути$.
b) Затем с помощью DFS $вслоённогообхода$ ищут и блокируют максимальное число вершинно-реберно непересекающихся увеличивающих путей минимальной длины $т.е.множествавершинно-непересекающихсяпутей$. После нахождения каждого пути matching увеличивается.Повторяют, пока BFS не найдёт ни одного свободного правого узла $неткороткихувеличивающихпутей$.

Сложность: O$sqrt(V)\ast E$ $обычнозаписываютO(sqrt(n)\cdot m)приn=|V|,m=|E|$. Краткая интуиция оценки: каждая фаза $одинBFS+несколькоDFS$ увеличивает размер matching на ≥1 и за каждую ~O$E$ работы либо происходит значительное увеличение размера matching $всумменеболееsqrt(V)фаздаютмногоприроста$, либо длина кратчайшего увеличивающего пути увеличивается, и длина может увеличиваться не больше O$sqrt(V)$ раз; формальный анализ даёт O$\surd V\cdot E$.

Практическая применимость Hopcroft–Karp:

Очень эффективен для больших разреженных двудольных графов при поиске максимального паросочетания по мощности.Часто используется в задачах вида распределение заданий/ресурсов, назначение $assignmentбезвесов$, сопоставление в биоинформатике, алгоритмы потоков и т.д.Реализуется довольно просто и присутствует во многих библиотеках $CP,networkx,boost$.

Альтернативы:

Редукция к потоку: построить сеть с источником, стоком, ребрами из source→L $cap=1$, из L→R $cap=1порёбрамисходногографа$ и R→sink $cap=1$. Тогда любой алгоритм максимального потока $Dinic,Edmonds-Karp,Push–Relabel$ даст максимальное паросочетание. Для графов с единичными пропускными способностями Dinic обычно работает за O$sqrt(V)\cdot E$ на практике и имеет хорошие реализации.Для взвешенного максимального паросочетания $максимумпосуммевесов$ применяется алгоритм Хунгарана $Kuhn–Munkres$ за O$n^3$ для полного двудольного графа $n—размерчасти$, либо min-cost max-flow для общего случая $медленнеедлябольшихграфов$.

5) Максимальное паросочетание в не двудольных графах

Для общих $недвудольных$ графов применяется алгоритм Эдмондса $blossomalgorithm$, который умеет "сворачивать" чётные циклы $blossoms$. Классическая сложность O$V^3$, более современные реализации $Micali–Vazirani$ дают O$\surd V\cdot E$. Реализация более сложна, но доступны готовые библиотеки $BoostGraphLibrary,Lemon,LEDAидр.$.Практически, если граф двудолен — используйте Hopcroft–Karp; если нет — либо Blossom $длябезвесового$, либо редукция к min-cost flow/Hungarian для взвешенной версии.

6) Приложения в реальных задачах

Задачи распределения и назначения: работа — вакансии, студент — проект, задачи с ресурсами.Сетевая маршрутизация и паросочетание используются при построении пар в сетях обмена $peer-to-peer$, парные сопоставления в биоинформатике $сопоставлениегенов/структур$, сопоставление признаков в компьютерном зрении.В задачах оптимизации и теории расписаний часто нужна максимальная кардинальная пара $илимаксимальнаяповесу$.Комбинирование с потоками, min-cost-max-flow, или с алгоритмами для динамического обновления паросочетания для онлайн/потоковых приложений.

7) Резюме по сложностям $итоговаясводка$

Проверка двудольности $BFS/DFS$: O$|V|+|E|$.Наивный поиск увеличивающего пути $Kuhn$ для двудольных графов: O$|L|\cdot |E|$ в худшем случае, обычно прост и эффективен для средних размеров.Hopcroft–Karp $максимальноенеперекрывающеесямнож.кратчайшихувеличивающихпутей$: O$\surd |V|\cdot |E|$.Сеть + Dinic для единичных пропускных способностей: в практических ситуациях сопоставим с Hopcroft–Karp, часто O$\surd |V|\cdot |E|$ на практике.Edmonds $blossom$ для общих графов: классически O$|V{|}^3$, улучшенные варианты O$\surd |V|\cdot |E|$.Взвешенное двудольное назначение $Hungarian/Kuhn–Munkres$: O$n^3$ для полного графа n×n.

Если хотите, могу:

Привести подробный псевдокод Hopcroft–Karp и доказательство оценки сложности пошагово;Показать пример работы алгоритма на конкретном графе;Порекомендовать реализации/библиотеки на C++, Python $networkx,scipy$, Java.