Анализ алгоритмов поиска максимального паросочетания в графах: от теоретических основ до практических приложений

В мире дискретной математики и компьютерных наук графы служат мощным инструментом для моделирования самых разнообразных систем — от социальных сетей до сложных инфраструктурных проектов. Одной из фундаментальных и, вместе с тем, нетривиальных задач в теории графов является поиск максимального паросочетания. Эта проблема, кажущаяся на первый взгляд абстрактной, находит свое отражение в колоссальном количестве прикладных задач: от оптимального распределения ресурсов и планирования расписаний до решения вопросов в биоинформатике и компьютерном зрении.

Целью данной курсовой работы является всесторонний анализ алгоритмов для нахождения максимального (по количеству ребер) подмножества попарно несмежных ребер в заданном графе. Мы не только погрузимся в теоретические основы этой задачи, но и детально рассмотрим классические и современные подходы к ее решению, оценивая их вычислительную сложность и эффективность. В рамках исследования будут решены следующие задачи:

1. Формализовать ключевые понятия теории графов и паросочетаний, выделив их взаимосвязи.
2. Подробно изучить принципы работы ведущих полиномиальных алгоритмов, применяемых как для двудольных, так и для общих графов.
3. Провести сравнительный анализ этих алгоритмов, оценив их вычислительную сложность и выявив оптимальные решения для различных типов графов.
4. Сформулировать и проанализировать неэффективные «алгоритмы перебора», подчеркнув их ограничения и значимость полиномиальных подходов.
5. Исследовать широкий спектр прикладных областей, где задача о максимальном паросочетании играет ключевую роль, а также обозначить современные направления исследований.
6. Дать рекомендации по выбору структур данных и методов программирования для эффективной реализации рассмотренных алгоритмов.

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

Основные понятия и определения теории графов и паросочетаний

Прежде чем углубляться в хитросплетения алгоритмов, важно заложить прочный фундамент из базовых определений. Именно строгость в терминологии позволяет избежать двусмысленностей и четко формулировать математические утверждения. Задача о поиске максимального паросочетания является краеугольным камнем в комбинаторной оптимизации, и ее понимание начинается с осмысления фундаментальных объектов — графов и их компонентов. Ведь без четкого понимания терминов невозможно адекватно оценить эффективность и применимость алгоритмов.

Базовые определения теории графов

В самом общем виде, граф G представляет собой упорядоченную пару (V, E), где V — это конечное непустое множество, элементы которого называются вершинами (узлами), а E — множество ребер, каждое из которых является неупорядоченной парой различных вершин из V. Эта простая структура позволяет моделировать отношения или связи между объектами.

Например, если V = {v₁, v₂, v₃, v₄} и E = {(v₁, v₂), (v₂, v₃), (v₃, v₄)}, то это означает, что вершина v₁ связана с v₂, v₂ с v₃, и v₃ с v₄.

Две вершины называются смежными, если они соединены ребром. Соответственно, два ребра называются смежными, если они имеют общую вершину. Если ребра не имеют общих вершин, они называются попарно несмежными. Эти простые понятия формируют каркас, на котором строятся более сложные структуры и задачи.

Формальное определение паросочетания и его виды

В контексте нашей задачи, центральным понятием является паросочетание. Паросочетанием (Matching) M в графе G называется любое подмножество ребер из E, такое что никакие два ребра из этого подмножества не имеют общих вершин. Иными словами, все ребра в паросочетании M являются попарно несмежными. Именно поэтому паросочетание также часто называют независимым множеством ребер.

Например, если у нас есть граф G с вершинами {1, 2, 3, 4, 5, 6} и ребрами {(1,2), (2,3), (3,4), (4,5), (5,6), (6,1)}, то множество ребер {(1,2), (3,4), (5,6)} будет являться паросочетанием, поскольку ни одно из этих ребер не имеет общих вершин с другим.

Существуют различные типы паросочетаний, которые важно различать:

• Максимальное по мощности паросочетание (или наибольшее паросочетание) — это паросочетание, содержащее максимально возможное количество ребер в графе. Именно эту задачу мы будем решать.
• Максимальное по включению паросочетание — это паросочетание M в графе G, к которому невозможно добавить ни одно ребро из E, которое было бы несмежным ко всем ребрам из M. Важно отметить, что максимальное по включению паросочетание не всегда является максимальным по мощности. Представьте себе ситуацию, когда вы жадным образом выбираете ребра, пока это возможно. Результат будет максимальным по включению, но, возможно, вы могли бы выбрать другой набор ребер и получить большее количество.

Рассмотрим граф с вершинами V = {1, 2, 3, 4} и ребрами E = {(1,2), (1,3), (2,4), (3,4)}.

• Паросочетание M₁ = {(1,2)} является максимальным по включению, так как к нему нельзя добавить ни (1,3) (смежно с 1), ни (2,4) (смежно с 2), ни (3,4).
• Паросочетание M₂ = {(1,3)} также является максимальным по включению.
• Паросочетание M₃ = {(1,2), (3,4)} является максимальным по мощности, так как содержит два ребра, и к нему нельзя добавить ни одно другое ребро. При этом M₁ и M₂, будучи максимальными по включению, не являются максимальными по мощности.

Помимо этих, существуют и другие важные виды паросочетаний:

• Совершенное паросочетание (Perfect Matching, или полное паросочетание) — это паросочетание, которое покрывает все вершины графа. То есть каждая вершина графа инцидентна некоторому ребру этого паросочетания. Совершенное паросочетание может существовать только в графах с четным числом вершин.
• Почти совершенное паросочетание — это паросочетание, в котором не участвует ровно одна вершина. Оно встречается в графах с нечетным числом вершин.

Эти определения закладывают основу для понимания того, что именно мы ищем и как оцениваем найденные решения.

Ключевые концепции для алгоритмов поиска паросочетаний

Для разработки и анализа эффективных алгоритмов поиска максимального паросочетания необходимо ввести еще несколько важных концепций, которые станут краеугольными камнями в дальнейших рассуждениях.

Одной из таких концепций является двудольный граф. Это граф G = (V, E), множество вершин V которого можно разбить на два непересекающихся подмножества A и B (называемых долями графа) таким образом, что любое ребро из E соединяет вершину из A с вершиной из B. Иными словами, внутри каждой доли графа (A или B) нет ребер. Задачи о паросочетаниях в двудольных графах часто имеют более эффективные алгоритмические решения по сравнению с общими графами.

Центральными понятиями для полиномиальных алгоритмов, которые мы будем рассматривать, являются чередующаяся цепь и дополняющая (увеличивающая) цепь.

• Чередующаяся цепь (Alternating Path) — это путь в графе, для любых двух соседних ребер которого верно, что одно из них принадлежит текущему паросочетанию M, а другое — нет. Иными словами, ребра чередуются: ребро из M, ребро не из M, ребро из M и так далее.
• Дополняющая (или увеличивающая) цепь (Augmenting Path) — это особый тип чередующейся цепи. Ее ключевое отличие в том, что обе ее концевые вершины являются свободными, то есть не инцидентны ни одному ребру из текущего паросочетания M.

Именно концепция увеличивающей цепи лежит в основе одного из самых элегантных и фундаментальных результатов в теории паросочетаний — Теоремы Бержа. Сформулированная Клодом Бержем в 1957 году, эта теорема гласит:

Паросочетание M является максимальным по мощности тогда и только тогда, когда в графе G не существует увеличивающей цепи относительно M.

Эта теорема имеет огромное значение, поскольку она предоставляет необходимый и достаточный критерий для определения того, является ли текущее паросочетание максимальным. Доказательство теоремы интуитивно понятно:

• Если M является максимальным по мощности, то по определению к нему нельзя добавить ни одного ребра, не нарушив свойства паросочетания, и, следовательно, в графе не может существовать увеличивающей цепи. Если бы такая цепь существовала, мы могли бы «инвертировать» ее ребра (удалить из M те, что были в цепи, и добавить те, что не были), получив паросочетание с большим числом ребер, что противоречило бы максимальности M.
• Если в G нет увеличивающей цепи относительно M, то M должно быть максимальным по мощности. Предположим обратное: пусть M не является максимальным по мощности, и существует другое паросочетание M’ с |M’| > |M|. Рассмотрим симметрическую разность M Δ M’ = (M \ M’) ∪ (M’ \ M). В этом подграфе каждая вершина имеет степень не более 2. Таким образом, компонентами связности этого подграфа являются пути и циклы. Поскольку |M’| > |M|, в M Δ M’ должно быть больше ребер из M’, чем из M. Это означает, что в M Δ M’ должна существовать как минимум одна компонента, которая является увеличивающей цепью для M (путь, начинающийся и заканчивающийся свободной вершиной, и имеющий больше ребер из M’, чем из M), что противоречит нашему предположению об отсутствии увеличивающих цепей.

Теорема Бержа стала фундаментальной для перехода от переборных методов (которые имеют экспоненциальную сложность) к эффективным полиномиальным алгоритмам. Она дает четкий критерий оптимальности и метод итеративного улучшения: начать с произвольного паросочетания (возможно, пустого) и итеративно искать увеличивающие цепи. Если найдена увеличивающая цепь, «увеличить» текущее паросочетание, инвертируя ребра на этой цепи. Этот процесс продолжается до тех пор, пока увеличивающих цепей не останется, что гарантирует достижение максимального паросочетания.

Наконец, важно упомянуть о связанном, но отличном понятии — независимое множество вершин. Это подмножество вершин графа, в котором никакие две вершины не смежны. Число независимости α(G) графа G — это мощность наибольшего независимого множества вершин. Хотя это понятие и не является напрямую паросочетанием, оно тесно связано с ним в ряде теоретических результатов (например, теорема Галлаи).

Классические алгоритмы нахождения максимального паросочетания

Эффективный поиск максимального паросочетания в графах — задача, над которой десятилетиями работали ведущие умы дискретной математики и компьютерных наук. В результате этих усилий были разработаны полиномиальные алгоритмы, способные решать эту проблему для графов значительного размера. Примечательно, что подходы к решению задачи существенно различаются в зависимости от того, является ли граф двудольным или общим.

Алгоритмы для двудольных графов

Двудольные графы обладают особой структурой, которая позволяет применять более простые и быстрые алгоритмы для поиска максимального паросочетания. Среди них выделяются два классических алгоритма: Алгоритм Куна и Алгоритм Хопкрофта-Карпа.

Алгоритм Куна

Алгоритм Куна, названный в честь Гарольда Куна, является одним из старейших и наиболее интуитивно понятных алгоритмов для поиска максимального паросочетания в двудольных графах. Его принцип основан на поиске увеличивающих цепей. Алгоритм последовательно просматривает вершины одной из долей графа (например, доли A), пытаясь найти увеличивающую цепь, начинающуюся в каждой свободной вершине. Если такая цепь найдена, текущее паросочетание «увеличивается» за счет инвертирования ребер вдоль этой цепи, что приводит к увеличению мощности паросочетания на единицу. Этот процесс повторяется до тех пор, пока не останется свободных вершин, из которых можно построить увеличивающую цепь.

Для поиска увеличивающих цепей Алгоритм Куна чаще всего использует обход в глубину (DFS). Процедура DFS модифицируется таким образом, чтобы искать путь от свободной вершины u из доли A до свободной вершины v из доли B, который чередуется между ребрами, не входящими в текущее паросочетание, и ребрами, входящими в него.

Псевдокод алгоритма Куна:

функция dfs(u, visited, matchR):
    visited[u] = ИСТИНА
    для каждого соседа v вершины u:
        если matchR[v] == -1 ИЛИ (НЕ visited[matchR[v]] И dfs(matchR[v], visited, matchR)):
            matchR[v] = u
            matchL[u] = v
            вернуть ИСТИНА
    вернуть ЛОЖЬ

функция kuhn_matching(граф G = (A ∪ B, E)):
    matchL = массив длины |A| с инициализацией -1 (для вершин из A)
    matchR = массив длины |B| с инициализацией -1 (для вершин из B)
    размер_паросочетания = 0
    для каждой вершины u из A:
        visited = массив длины |A| с инициализацией ЛОЖЬ
        если dfs(u, visited, matchR):
            размер_паросочетания = размер_паросочетания + 1
    вернуть размер_паросочетания и matchL, matchR

Здесь matchL[u] хранит вершину из B, с которой u_A спарена, а matchR[v] хранит вершину из A, с которой v_B спарена. Значение -1 означает, что вершина свободна.

Пример работы:
Пусть у нас есть двудольный граф с долями A = {A1, A2, A3} и B = {B1, B2, B3} и ребрами:
(A1, B1), (A1, B2), (A2, B2), (A3, B3).

1. Начинаем с пустого паросочетания M = {}.
2. Рассматриваем A1. Запускаем DFS из A1.
   • Путь A1-B1. B1 свободна. Добавляем (A1, B1) в M. M = {(A1, B1)}.
3. Рассматриваем A2. Запускаем DFS из A2.
   • Путь A2-B2. B2 свободна. Добавляем (A2, B2) в M. M = {(A1, B1), (A2, B2)}.
4. Рассматриваем A3. Запускаем DFS из A3.
   • Путь A3-B3. B3 свободна. Добавляем (A3, B3) в M. M = {(A1, B1), (A2, B2), (A3, B3)}.

Поскольку все вершины из A теперь насыщены, и не осталось увеличивающих цепей, алгоритм завершается, возвращая максимальное паросочетание {(A1, B1), (A2, B2), (A3, B3)} размером 3.

Алгоритм Хопкрофта-Карпа

Алгоритм Хопкрофта-Карпа, разработанный Джоном Хопкрофтом и Ричардом Карпом, является более продвинутым методом для поиска наибольшего паросочетания в двудольных графах. Его ключевое преимущество заключается в значительно лучшей асимптотической временной сложности по сравнению с Алгоритмом Куна. Вместо того чтобы находить одну увеличивающую цепь за итерацию, Алгоритм Хопкрофта-Карпа строит максимальный набор кратчайших увеличивающих путей одновременно.

Алгоритм работает в несколько фаз, каждая из которых состоит из двух этапов:

1. Фаза BFS: Выполняется поиск в ширину (BFS) для построения слоистой структуры графа. Цель этого этапа — найти все кратчайшие увеличивающие цепи. Все вершины, которые могут быть достигнуты из свободных вершин доли A, размечаются уровнями. Если в процессе BFS находится свободная вершина в доле B, то это означает, что найдена хотя бы одна увеличивающая цепь. BFS останавливается на первом уровне, на котором обнаружена свободная вершина из B.
2. Фаза DFS: Используя слоистую структуру, построенную на этапе BFS, запускается модифицированный поиск в глубину (DFS) из каждой свободной вершины доли A. DFS пытается найти увеличивающие цепи, которые состоят только из ребер, соединяющих вершины соседних уровней, и, что важно, только из кратчайших увеличивающих цепей. При этом, как только увеличивающая цепь найдена и использована для увеличения паросочетания, ребра в этой цепи помечаются как использованные, и DFS продолжает поиск других увеличивающих цепей, не переиспользуя уже пройденные вершины в текущей фазе.

Эта стратегия позволяет алгоритму Хопкрофта-Карпа достигать временной сложности O(E√V), где V — число вершин, а E — число ребер. Эта оценка асимптотически быстрее, чем O(V³) для плотных графов и близка к O(E) для разреженных графов. Увеличение скорости происходит за счет того, что на каждой итерации алгоритм находит сразу несколько несвязанных увеличивающих путей, что сокращает общее количество фаз до O(√V).

Сведение к задаче о максимальном потоке

Интересно, что задача о максимальном паросочетании в двудольном графе может быть сведена к хорошо изученной задаче о максимальном потоке. Для этого строится новая транспортная сеть:

1. Создается исток S и сток T.
2. Для каждой вершины u из доли A проводится ребро из S в u с пропускной способностью 1.
3. Для каждой вершины v из доли B проводится ребро из v в T с пропускной способностью 1.
4. Для каждого ребра (u, v) в исходном двудольном графе (где u ∈ A, v ∈ B) проводится ребро из u в v с пропускной способностью 1.

Максимальный поток в этой транспортной сети будет численно равен размеру максимального паросочетания в исходном двудольном графе. Для решения задачи о максимальном потоке может быть применен Алгоритм Эдмондса-Карпа, который является одним из вариантов метода Форда-Фалкерсона и базируется на поиске увеличивающих путей в остаточном графе с помощью BFS.

Алгоритмы для общих графов

Для нахождения наибольшего паросочетания в произвольных (общих) графах, где могут присутствовать циклы нечетной длины, требуется более сложный подход. Классическим решением в этом случае является Алгоритм Эдмондса.

Алгоритм Эдмондса (сжатия цветков)

Алгоритм Эдмондса, разработанный Джеком Э��мондсом в 1961 году и опубликованный в 1965 году, стал первым полиномиальным алгоритмом для поиска наибольшего паросочетания в общих графах. До его появления задача считалась значительно более трудной, чем для двудольных графов, из-за наличия нечетных циклов.

Ключевая идея алгоритма Эдмондса заключается в концепции «сжатия нечетных циклов», которые Эдмондс назвал «цветками». Нечетный цикл — это цикл, состоящий из нечетного числа вершин и, соответственно, нечетного числа ребер. Если в нечетном цикле есть свободная вершина, то можно найти увеличивающую цепь, проходящую через этот цикл.

Принцип работы алгоритма:

1. Алгоритм начинает с пустого или произвольного паросочетания M.
2. Он ищет увеличивающие цепи, используя модифицированный поиск в ширину (BFS) из всех свободных вершин.
3. В ходе BFS алгоритм строит так называемое «дерево поиска» (похожее на то, что используется в Алгоритме Куна или при поиске максимального потока).
4. Если в процессе поиска BFS обнаруживается ребро, соединяющее две вершины одного уровня (то есть обе вершины находятся на четном или обе на нечетном расстоянии от корня), и это ребро не входит в текущее паросочетание, то это ребро вместе с частью дерева поиска образует нечетный цикл — «цветок».
5. Когда «цветок» обнаружен, алгоритм «сжимает» его в одну новую вершину, рассматривая ее как единый узел. Все ребра, инцидентные вершинам внутри цветка, становятся инцидентными этой новой «сжатой» вершине.
6. Поиск увеличивающих цепей продолжается в сжатом графе.
7. Если увеличивающая цепь найдена в сжатом графе, то алгоритм «разжимает» цветок и соответствующим образом модифицирует паросочетание, «проталкивая» увеличение через цикл.

Псевдокод (упрощенный, для понимания идеи):

функция edmonds_matching(граф G = (V, E)):
    M = пустое_паросочетание
    пока существует_увеличивающая_цепь(G, M):
        P = найти_увеличивающую_цепь(G, M)  // Включает сжатие/разжатие цветков
        M = M XOR P                       // XOR - симметрическая разность множеств ребер
    вернуть M

функция найти_увеличивающую_цепь(G, M):
    // Модифицированный BFS для поиска увеличивающих цепей
    // Если найден нечетный цикл (цветок):
    //     Сжать цветок в одну вершину
    //     Рекурсивно вызвать find_augmenting_path на сжатом графе
    //     Разжать цветок и восстановить путь
    // ...

Значение Алгоритма Эдмондса:
Историческая значимость Алгоритма Эдмондса трудно переоценить. Он не только предоставил первое полиномиальное решение для общей задачи о максимальном паросочетании, но и открыл дорогу для дальнейших исследований в комбинаторной оптимизации, показав, как сложные структуры (нечетные циклы) можно эффективно обрабатывать. Его идеи оказали влияние на развитие других областей, таких как комбинаторная полиэдральная теория.

Сравнительный анализ алгоритмов: вычислительная сложность и эффективность

Понимание вычислительной сложности алгоритмов является краеугольным камнем в анализе их эффективности и применимости. В этом разделе мы рассмотрим, насколько «дороги» рассмотренные алгоритмы с точки зрения времени и памяти, а также проведем сравнительный анализ, включая оценку неэффективных переборных методов.

Анализ вычислительной сложности полиномиальных алгоритмов

Каждый из рассмотренных алгоритмов имеет свою характерную вычислительную сложность, которая выражается в O-нотации и зависит от числа вершин (V) и ребер (E) графа.

• Сложность Алгоритма Куна (для двудольных графов):
  В худшем случае, Алгоритм Куна имеет временную сложность O(V · E). Это происходит потому, что на каждой из V итераций (для каждой вершины из одной доли) может быть запущен DFS, который в худшем случае просматривает все E ребер.
  Применимость: Алгоритм Куна хорошо подходит для разреженных двудольных графов и является относительно простым в реализации. Однако для плотных графов его производительность может быть неудовлетворительной.
• Сложность Алгоритма Хопкрофта-Карпа (для двудольных графов):
  Алгоритм Хопкрофта-Карпа демонстрирует значительно лучшую временную сложность O(E√V). Это достигается благодаря его двухфазной итерационной структуре:
  1. Фаза BFS: Поиск в ширину строит слоистый граф, находя максимальный набор кратчайших увеличивающих цепей. Эта фаза занимает O(E) времени.
  2. Фаза DFS: Последующий поиск в глубину находит все эти кратчайшие увеличивающие цепи. Эта фаза также занимает O(E) времени.

  Ключевое достижение состоит в том, что общее число таких фаз ограничено O(√V). Таким образом, общая временная сложность составляет O(√V · E). Эта оценка асимптотически быстрее, чем O(V³) для плотных графов (где E ≈ V², тогда O(V²√V) = O(V^2.5)) и близка к O(E) для очень разреженных графов. Именно эта асимптотическая скорость делает Алгоритм Хопкрофта-Карпа наиболее эффективным для большинства задач на двудольных графах.

• Сложность Алгоритма Эдмондса (для общих графов):
  Алгоритм Эдмондса для произвольных графов работает за O(V³). Его сложность обусловлена необходимостью обработки «цветков» и рекурсивного сжатия графа. Каждая итерация поиска увеличивающей цепи, которая может включать сжатие и разжатие цветков, может потребовать O(V · E) времени, а таких итераций может быть O(V).
  Возможности оптимизации: Оптимизация Алгоритма Эдмондса может включать предварительное построение произвольного паросочетания (например, жадным алгоритмом), что на некоторых классах графов (например, случайных) может значительно ускорить его работу, сократив количество необходимых итераций. Также существуют более сложные реализации, которые позволяют снизить сложность до O(V · E) или даже O(V²) с использованием более продвинутых структур данных и техник.
• Сложность Алгоритма Эдмондса-Карпа (для задачи о максимальном потоке, к которой сводится задача о паросочетании в двудольных графах):
  Применение Алгоритма Эдмондса-Карпа для нахождения максимального потока имеет сложность O(V · E²), где V — число вершин, а E — число ребер в транспортной сети. Однако, в случае единичных пропускных способностей (как это происходит при сведении задачи о паросочетании), его сложность может быть уменьшена до O(V · E). Тем не менее, для двудольных графов Алгоритм Хопкрофта-Карпа все равно остается асимптотически быстрее, поскольку O(E√V) < O(V · E) для большинства практически интересных случаев.

Сводная таблица сложности алгоритмов:

Алгоритм	Тип графа	Временная сложность	Пространственная сложность	Примечания
Алгоритм Куна	Двудольный	O(V · E)	O(V + E)	Прост в реализации, хорош для разреженных графов.
Алгоритм Хопкрофта-Карпа	Двудольный	O(E√V)	O(V + E)	Асимптотически наиболее быстрый для двудольных графов, использует параллельный поиск кратчайших увеличивающих путей.
Алгоритм Эдмондса	Общий	O(V3)	O(V + E)	Первый полиномиальный алгоритм для общих графов, использует «сжатие цветков».
Алгоритм Эдмондса-Карпа	Общий (через макс. поток)	O(V · E2)	O(V + E)	Для единичных пропускных способностей O(V · E).

Сравнение «алгоритма перебора» с полиномиальными методами

Чтобы по-настоящему оценить элегантность и мощь полиномиальных алгоритмов, необходимо хотя бы кратко рассмотреть альтернативу — «алгоритм перебора». Под «алгоритмом перебора» в данном контексте понимается прямолинейный подход, который заключался бы в следующем:

1. Сгенерировать все возможные подмножества ребер графа.
2. Для каждого подмножества проверить, является ли оно паросочетанием (т.е., нет ли в нем смежных ребер).
3. Среди всех найденных паросочетаний выбрать то, которое содержит максимальное количество ребер.

Этот подход, хотя и гарантирует нахождение максимального паросочетания, является катастрофически неэффективным. Если граф G имеет E ребер, то существует 2^E различных подмножеств ребер. Таким образом, временная сложность такого алгоритма будет экспоненциальной, выражаемой как O(2^E). В худшем случае, для плотного графа с V вершинами, число ребер E может быть порядка O(V²), что приводит к сложности O(2^V2). Для графов с большим числом вершин, даже небольшим, такой алгоритм становится невыполнимым в разумные сроки.

Например, для графа с 20 вершинами (что является очень скромным размером для современных задач) количество возможных ребер может достигать 20 * 19 / 2 = 190. Тогда 2¹⁹⁰ операций — это число, превышающее число атомов во Вселенной, и такой расчет не будет завершен никогда.

Именно здесь на сцену выходит фундаментальная Теорема Бержа, которая, как мы уже видели, утверждает, что паросочетание M является максимальным по мощности тогда и только тогда, когда в графе G не существует увеличивающей цепи относительно M. Эта теорема стала тем ключевым «инсайтом», который позволил избежать перебора. Вместо того чтобы проверять все возможные комбинации, полиномиальные алгоритмы используют итеративный подход, основанный на поиске увеличивающих цепей. Каждая найденная увеличивающая цепь позволяет увеличить текущее паросочетание на одно ребро. Поскольку максимальное число ребер в паросочетании не может превышать V/2, то и число итераций по поиску увеличивающих цепей (в каждом из которых паросочетание увеличивается) ограничено, что и приводит к полиномиальной временной сложности. Теорема Бержа дает четкий критерий оптимальности, позволяя алгоритмам остановиться, когда дальнейшие улучшения невозможны, и гарантируя, что найденное решение действительно является максимальным.

Обзор оптимизаций и современные подходы

Несмотря на наличие классических полиномиальных алгоритмов, исследования в области паросочетаний не стоят на месте. Существуют различные оптимизации и современные подходы, направленные на дальнейшее ускорение работы алгоритмов, особенно для очень больших графов или в специфических условиях:

• Параллельные и распределенные алгоритмы: Для обработки сверхбольших графов, которые не помещаются в память одного компьютера, разрабатываются параллельные и распределенные версии алгоритмов паросочетаний.
• Эвристики и приближенные алгоритмы: В некоторых прикладных задачах, где точное решение слишком дорого или не требуется, используются эвристические и приближенные алгоритмы, которые находят «достаточно хорошее» паросочетание за меньшее время.
• Использование специализированных структур данных: Оптимизация на низком уровне, например, использование специализированных структур данных для представления графов и поиска путей, может значительно улучшить константу в асимптотической оценке.
• Алгоритмы для взвешенных паросочетаний: Для графов, где ребра имеют веса, задача усложняется до поиска паросочетания с максимальной суммой весов. Для этого используются алгоритмы, такие как алгоритм венгерских графов (для двудольных графов) или алгоритм Минковского (для общих графов), которые также имеют полиномиальную сложность.

Эти направления исследований показывают, что, несмотря на зрелость области, возможности для улучшения и адаптации алгоритмов остаются.

Прикладные области и направления исследований

Задача о максимальном паросочетании, хоть и является фундаментальной в теории графов, имеет удивительно широкий спектр практических применений. Это свидетельствует о глубокой связи между абстрактной математикой и реальными инженерными, экономическими и научными проблемами. Более того, эта область продолжает развиваться, открывая новые горизонты исследований.

Прикладные задачи, решаемые с помощью паросочетаний

Паросочетания выступают мощным инструментом для моделирования и оптимизации в самых разнообразных сферах:

• Классическая задача о назначениях (Assignment Problem): Это, пожалуй, наиболее известное и интуитивно понятное применение. Представьте себе ситуацию, где есть набор рабочих и набор задач, и каждый рабочий может выполнить определенные задачи. Цель — назначить как можно больше рабочих на задачи так, чтобы каждый рабочий выполнял не более одной задачи, и каждая задача выполнялась не более одним рабочим. Эта задача легко моделируется как поиск максимального паросочетания в двудольном графе, где доли представляют рабочих и задачи, а ребра — возможные назначения. Аналогичные сценарии включают составление пар для танцев, распределение ресурсов по проектам, или сопоставление студентов и курсов.
• Оптимизация компьютерных сетей и распределение ресурсов: В телекоммуникациях и компьютерных сетях паросочетания могут использоваться для оптимизации маршрутизации данных, распределения пропускной способности или назначения частот. Например, для определения оптимальных путей передачи данных между серверами, минимизируя конфликты и максимизируя утилизацию ресурсов.
• Примеры из компьютерного зрения: В области обработки изображений и компьютерного зрения паросочетания применяются для задач сегментации изображений, сопоставления объектов или отслеживания движения. Например, для сопоставления точек интереса между двумя изображениями или для объединения сегментов изображений в единые объекты.
• Задачи в синтетической биологии: Удивительно, но даже в синтетической биологии, например, при разработке новых ДНК-последовательностей, можно столкнуться с задачами о паросочетаниях. Пример — перемешивание символов в строке для максимизации количества перемещенных символов, что может быть смоделировано как поиск паросочетания в графе, где вершины представляют позиции символов, а ребра — возможные обмены.
• Планирование, моделирование сложных систем, анализ социальных и биологических сетей: Паросочетания играют роль в широком круге задач, связанных с планированием (например, расписание транспорта), моделированием взаимодействия элементов в сложных системах (например, химических реакций), анализе социальных связей (например, поиск устойчивых пар или групп), и изучении биологических сетей (например, взаимодействие белков).
• Размещение доминошек на прямоугольном поле с выколотыми клетками: Классическая головоломка, которая может быть формализована как задача о паросочетании. Поле превращается в граф, где каждая клетка — вершина, а ребра соединяют соседние клетки. Задача сводится к поиску максимального паросочетания в этом графе.
• Покрытие ориентированного ациклического графа (DAG) наименьшим числом путей: Теорема Дилуорта (Dilworth’s Theorem) связывает эту задачу с поиском максимальной антицепи в DAG. Однако с помощью паросочетаний можно эффективно решить задачу о минимальном покрытии вершин путями в ориентированном графе, сведя ее к поиску максимального паросочетания в специально построенном двудольном графе.

Современные направления исследований

Область паросочетаний не является статичной; она продолжает развиваться, порождая новые теоретические и практические вызовы.

• Обобщение концепции паросочетаний на матроиды: Матроиды — это комбинаторные структуры, которые обобщают понятия линейной независимости в векторных пространствах и независимости в графах (например, остовы или паросочетания). Исследования в этой области направлены на поиск максимальных паросочетаний в более общих матроидных структурах, что открывает двери для решения широкого класса задач комбинаторной оптимизации.
• Задачи о взвешенных паросочетаниях: В реальных приложениях ребра графа часто имеют ассоциированные веса (например, стоимость, время, полезность). Задача о взвешенном максимальном паросочетании заключается в поиске паросочетания, сумма весов ребер которого является максимальной (или минимальной, в зависимости от постановки задачи). Для решения этой задачи используются более сложные алгоритмы, такие как венгерский алгоритм (для двудольных графов) или алгоритм Минковского (для общих графов), которые также имеют полиномиальную сложность.
• Вклад Алгоритма Эдмондса в комбинаторную полиэдральную теорию: Помимо своей непосредственной алгоритмической ценности, Алгоритм Эдмондса имеет глубокое теоретическое значение. Он предоставил первое доказательство целочисленности многогранника паросочетаний, которое не следовало из тотальной унимодулярности. Многогранник паросочетаний — это выпуклая оболочка индикаторных векторов всех паросочетаний в графе. Целочисленность означает, что вершины этого многогранника имеют целочисленные координаты, что крайне важно для задач линейного программирования и комбинаторной оптимизации, поскольку это гарантирует, что оптимальное решение задачи линейного программирования для этого многогранника будет соответствовать реальному паросочетанию.

Эти направления подчеркивают не только продолжающуюся актуальность исследований в области паросочетаний, но и их глубокое влияние на более широкие аспекты комбинаторной математики и оптимизации.

Структуры данных и методы программирования для реализации алгоритмов

Успешная реализация алгоритмов поиска максимального паросочетания невозможна без грамотного выбора структур данных для представления графов и эффективных методов программирования. Правильный выбор может существенно повлиять на производительность алгоритма, особенно при работе с большими графами.

Представление графов в памяти

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

• Матрица смежности: Это двумерный массив (матрица) размером V × V, где V — число вершин в графе. Элемент A_ij равен 1, если между вершинами i и j существует ребро, и 0 в противном случае. Для невзвешенных графов этого достаточно, для взвешенных графов в ячейках хранят веса ребер.
  • Преимущества: Быстрая проверка наличия ребра между двумя вершинами O(1). Удобно для плотных графов.
  • Недостатки: Требует O(V²) памяти, что может быть избыточно для разреженных графов. Для графа с 1000 вершин потребуется 1 000 000 ячеек, даже если ребер всего несколько тысяч.
• Списки смежности: Для каждой вершины хранится список ее смежных вершин. Обычно это реализуется как массив списков (или вектор векторов), где adj[i] — это список вершин, смежных с i.
  • Преимущества: Требует O(V + E) памяти, что значительно эффективнее для разреженных графов, поскольку память расходуется только на существующие ребра.
  • Недостатки: Проверка наличия ребра между двумя вершинами требует обхода списка смежности одной из вершин, что в худшем случае занимает O(степень(V)) или до O(V) времени.

Обоснование выбора в зависимости от плотности графа:

Граф считается плотным, если число его ребер E близко к максимально возможному для полного графа, которое составляет V(V-1)/2. Граф называется разреженным, если число его ребер значительно меньше максимально возможного, то есть |E| << V². Формально, плотность графа D определяется как D = 2E / (V(V-1)). Если D близко к 1, граф плотный; если D близко к 0, граф разреженный.

• Для плотных графов: Матрица смежности может быть предпочтительнее. Хотя она и занимает O(V²) памяти, это близко к оптимальному, так как E ≈ V². Более того, постоянный доступ к наличию ребра O(1) может ускорить операции в некоторых алгоритмах.
• Для разреженных графов: Списки смежности являются оптимальным выбором. Они экономят память O(V + E) и обычно обеспечивают лучшую производительность для алгоритмов, которые обходят граф, так как они не тратят время на перебор несуществующих ребер. Большинство практических графов являются разреженными.

Базовые алгоритмы обхода графов

Алгоритмы поиска паросочетаний часто используют фундаментальные алгоритмы обхода графов как свои строительные блоки:

• Поиск в ширину (BFS — Breadth-First Search): Начинается с заданной вершины и исследует все ее соседи на одном уровне, прежде чем перейти к соседям следующего уровня. BFS особенно важен для алгоритмов, которые ищут кратчайшие увеличивающие пути, таких как Алгоритм Эдмондса-Карпа и Алгоритм Хопкрофта-Карпа. В этих алгоритмах BFS используется для построения слоистых графов или для определения расстояний до свободных вершин, что позволяет находить увеличивающие цепи оптимальной длины.
• Поиск в глубину (DFS — Depth-First Search): Начинается с заданной вершины и исследует как можно дальше по каждой ветви перед тем, как вернуться. DFS является основой Алгоритма Куна для поиска увеличивающих цепей. Он рекурсивно пытается «продлить» текущий путь, пока не найдет свободную вершину или не исчерпает все возможности.

Инструменты и библиотеки для работы с графами

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

В языке Python, например, существует популярная библиотека NetworkX. Она предоставляет широкий спектр функций для:

• Создания графов: Возможность легко создавать как простые, так и сложные графы различных типов (ориентированные, неориентированные, взвешенные, мультиграфы).
• Анализа графов: Встроенные функции для вычисления различных метрик (степень вершин, кратчайшие пути, центральность, компоненты связности) и, что особенно важно для нашей темы, реализации алгоритмов поиска паросочетаний. NetworkX включает реализации алгоритмов для поиска максимального паросочетания в двудольных и общих графах.
• Визуализации графов: Инструменты для графического представления графов, что очень полезно для отладки и демонстрации работы алгоритмов.

Использование таких библиотек позволяет сосредоточиться на логике алгоритма и анализе результатов, а не на низкоуровневой реализации базовых операций с графами. Кроме NetworkX, существуют аналогичные библиотеки для других языков программирования (например, Boost.Graph для C++, JGraphT для Java), а также специализированные программы для визуализации и анализа графов (например, Gephi).

Заключение

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

Мы начали с тщательного рассмотрения базовых понятий теории графов, определив такие ключевые термины, как вершины, ребра, смежность и несмежность. Были формализованы различные виды паросочетаний, включая максимальное по мощности, максимальное по включению, совершенное и почти совершенное, с акцентом на их различия и практическое значение. Особое внимание было уделено концепции увеличивающих цепей и фундаментальной Теореме Бержа, которая послужила краеугольным камнем для разработки эффективных полиномиальных алгоритмов, давая четкий критерий оптимальности и метод итеративного улучшения.

Далее был представлен детальный обзор классических алгоритмов: Алгоритм Куна и Алгоритм Хопкрофта-Карпа для двудольных графов, а также Алгоритм Эдмондса (сжатия цветков) для общих графов. Для каждого алгоритма были описаны принципы работы, включая псевдокод и примеры, подчеркивающие их специфику и историческое значение. В частности, было обосновано, как Алгоритм Хопкрофта-Карпа достигает своей асимптотической скорости O(E√V) за счет параллельного поиска кратчайших увеличивающих путей, и как Алгоритм Эдмондса преодолевает сложности, связанные с нечетными циклами в общих графах.

Сравнительный анализ вычислительной сложности показал кардинальное различие между экспоненциальной сложностью примитивных «алгоритмов перебора» и полиномиальной эффективностью современных методов. Это сравнение еще раз подчеркнуло значимость теоретических открытий, таких как Теорема Бержа, которые позволили превратить неразрешимые для больших графов задачи в вычислительно управляемые. Были рассмотрены и возможности оптимизации, а также современные подходы к решению задачи о паросочетаниях.

Широта прикладных областей, от классической задачи о назначениях до оптимизации компьютерных сетей, сегментации изображений, анализа биологических систем и планирования, продемонстрировала не только академическую, но и огромную практическую ценность исследования паросочетаний. Были также обозначены современные направления исследований, такие как обобщение на матроиды и задачи о взвешенных паросочетаниях, а также вклад Алгоритма Эдмондса в комбинаторную полиэдральную теорию.

Наконец, были рассмотрены эффективные подходы к реализации алгоритмов, включая выбор оптимальных структур данных (матриц и списков смежности) в зависимости от плотности графа, а также роль базовых алгоритмов обхода графов (BFS и DFS) и современных программных инструментов, таких как библиотека NetworkX.

Таким образом, поставленные цели и задачи исследования были полностью достигнуты. Проведенный анализ подтверждает, что задача о максимальном паросочетании является одной из центральных и наиболее плодотворных в дискретной математике, а разработанные для ее решения алгоритмы — ярким примером того, как глубокие теоретические изыскания приводят к мощным и универсальным инструментам для решения реальных мировых проблем. Дальнейшие перспективы исследования могут включать углубленное изучение параллельных и распределенных алгоритмов для сверхбольших графов, а также разработку новых эвристик для задач взвешенного паросочетания в динамически изменяющихся графах.

Список использованной литературы

1. Максимальное паросочетание. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGnq67XXC60bYnRFNnyo30BouChBNtk3EMzN5OmLv0BEVpNeVvtzX8fY9YVpZlzoEjq9M5WZLKxqaQ_RNp_utdoK17FeZU1hiDXmF400SH0RAM4RLmpeC-kr17Xnx_2F4BCakp5wpek_lbSqyQ6-RMSzLfJXnqhIgWCROlkmQaM (дата обращения: 22.10.2025).
2. Совершенное паросочетание — WikiGrapp. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHLTRR-o1hSBTXpnn4hs-BLgv6wxsxWnCOmrCC0Yl8P9NatQiI2ohSl16JLbUlitEck6CSCkP5fvWjA8MOns0pJ29xEdaf50ivjt2F-BBwUcfw-VB66kT87GcWyDEgakPCw9an_Q8ImRLkHSOb588Gi37gD-b0UxjZKFPCaTxav3QuPckAaSDsikXoTX17vRp7TURt28BERm8ACadBVk1FkNXrtR5TkfI82CvHuy2Qt0P8_MK10YddnwWDs8xvPxb90fPUTL30Nj9KVNl6IkkXwObEkNZFuimGWItGy4ehW2T80PvUOapfPTdr74AkRA3vU3KI= (дата обращения: 22.10.2025).
3. Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях — Викиконспекты. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHSMSSSw6lo7yQ80O5gNwWtPOhGoa5q-jYBJ64ZJOXPzEaxbKYtzcWuwhx16SsLORGdst0N3Oh9q9PYiZUWGgo72dprZSugy4oPmuqm9_YzI3MUsKgygnlY2IOVIJZ0s4aKcIds0xKOGn6ljt6NnkHQb2DqjF05eHTz3paltetlUEOaXffjFlK9FpD0oErSHvZfmVgpbtKhxmzeHrLvWGVdQv-mJtpBg3yShBNokcWICJgnMQRRXBivoNoTRdbxCWr3nk1IX7mDQOa6maIFLLhtltVHhWujX9ZBXdJ2BOsf-6njI3b3BfiBa8JI1wdqMJHLodT41YGWatBpmmCdpOJMNeak_rzX_j7BL9YBwFSVbYRfhgofDKerDdl_31h0vSrb-r3_N4Q_GuT7jNdv64xzUBI4SplUyMtApMZ0gXujf_QTiXTNuQsVQRW_h592CD70rQBF-QDTUcxFgR8IH6EBDCxxL5NNv7acnncvACFjVtiJabANBO_d-8ibaFFpOfqw0nz6AVSj78Sn3YsjYWJGN4YxdWAhspw1-uwsvgAgtZeS_XXcR0X6dnGiV6E3jDWUIJ6Wkqxm_QLAVU7eWCIgT9RUaqSHkHbBkRRKjxf23IT5qC626esB0YFgV8cVZnTX6c89pf9C0Y3852eU1lr4jejNX4I5ERK5XVewET3DRdrnChhqCX21yq1ucVkKcfrJh-VuS65kaTl9ilran1VGW1UsFkWIJ0uiM4vxIeXUW1iHn1jKB5i5q9H9s0RsAYIIWARkkyAq1jDycpuPEW5HDatzSas9fG1kA6Vi0Q== (дата обращения: 22.10.2025).
4. Теоретический материал: Поиск максимального паросочетания в двудольном графе. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFU0Jps9bpo4lN7T4VtwcuRuebk3cKFbhlkK_2wXNLYqkXGVXTF3XGXbuOMS2d7mI_jNWhQoZPgFjVKWtSn1r9iDp2KbYOmSidyLT_RnDC8—JUOnbd-X3FWZSwJ55PpccEageQ5a88Tp_YqAwx (дата обращения: 22.10.2025).
5. Основные понятия Теории Графов — Skysmart. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFk-gmBKnVSPmjPMBgZlDTpSuD1zCYbKaeUWdWsiADbgxXhsGdD3uyZkCuj-qx7bJklhKWPo7oAkWNQGV5gKAJmaTa6Uka7riQcb35ShZtwx8-4SkB15FkbfB1xghDyOegJA-2jwiPj7QzxScXsinkiKAMBIuk75GAV4zpGwuUjlKh0 (дата обращения: 22.10.2025).
6. Глава 6. ПАРОСОЧЕТАНИЯ И ЗАДАЧА О НАЗНАЧЕНИЯХ. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEXqMFVvweXTfZNrSizm6l53kPhyCLCu1kjFq0Q_g8bdmU40KSKTm6HffhoiJDNAGpvyIRtaQctZ7of8BLB-CQW2E4Elrk82v1a8r8SehIFrK7PKR3TssovvzXWwgtgSbAcLXcgktx9U2LK1g== (дата обращения: 22.10.2025).
7. Алгоритм Хопкрофта – Карпа для отыскания наибольшего паросочетания в двудольном графе. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFS7KSmtm1mWuy-J3DFIcLMsstZ6FrInfV07LfG8DcV8NmmCLvZkoD6VriVcMDCGrgTxKr-Md8zrFzuJGDmVHEyW_KvJQh5icUX9h4dy0RvOs_0K2j9FXYMIs_QLT0AFli4Hkuu8Q== (дата обращения: 22.10.2025).
8. Паросочетания — Алгоритмика — Algorithmica. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGn02KPAHLMmXr54Fvq7pBdFTc4PMcQeQWL81gbdRG4OpClGQij2Hu9djUdRBc57OUCwH6LJoNb2taXwugYI2vyqw62UAPfZtAlM63VOzujoZgabY32rbhepX1e5m2- (дата обращения: 22.10.2025).
9. Паросочетание — Википедия. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHSq2Xb_4IEnrbBJ9IdO6ggQluGdLLupGk3R_cHWxaS2nESAg0YFzQTEFii6B-_H41etSuPzY2ka0ny4llVs6RkYrUz8coF4OZrX09OYCd47BZdFFRcr6tNBpuxA0_TRqjckKWarTPqTzRachFxbaTYuzrDmrmBvWze8ss5i_neurAcMHkmUrHC826Jy_LEcLsxRvXhA6iV81FKSVvlbh2vUEREauXD (дата обращения: 22.10.2025).
10. algo :: Алгоритм Эдмондса нахождения наибольшего паросочетания — e-maxx.ru. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEomtdx22B7_ytGaHHvHREhjiMGZDddpQUomIZ9OKC8K7gKsUDgumpITt4Qb3UN0Ew9aKdC8fkVapzpgy_Tv6LfCEdzpKJyqoZpbppGno8CLsHy3pJ6OCR1XA6U5ikQJOM= (дата обращения: 22.10.2025).
11. Теория графов: деревья, планарность, разновидности графов — Skillbox. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHN9bCCSzdBn1LRz6O9bIujzTqMRikHSJkX9lvKG8TU-ffq-As8EC1Hh9nPrpNWQGY1389g9YKq_pQZ4ivi2WkDu9o7RWG0uy1xhFJXHk4wiXmsfnVkJW_apXdfaEBI82Q4A4mPvD5iUu4-cSqZ0QSkwfpYWUTdoc9aRsFJUmzQ1QdCkuPtyxVrUW8pDVEkCWQ= (дата обращения: 22.10.2025).
12. Алгоритм Хопкрофта — Карпа — Википедия. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEmfwmCj9Yb8nZ4kCQya2FP7WC98HsdUlxcTRFfA4xQXH7E8NBbN-GgsuVczrz0jQt5y3AVYGLwmuQCJR_SrjQ_0Lbm3EGZnbFFZvHnJnJl2lvShRQHUGT2TTnNWJlvHRb9qkOWzovaKDqWZ5Au64kJcC14Ka9n-iHmVdIFj2lPST5zj5NznHkiWMC5SZRDkOhiptjzWfbIMjJx4Ghxx__JGERxtNDCl4A_I-MSDpEfnNecYwXeiL6J44HMwHLOPx-NByLKXTmo6FI1g2C2_iI1YRSdVi2VK1C_22Icioy0uUgFlsZKWuJroA== (дата обращения: 22.10.2025).
13. Алгоритм Гопкрофта-Карпа — AlgoWiki. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFixKbAhM2Br9FeQdUr8PkpC5ckGoo3dP7J_Bz7gyWVLeMEnD4pu839zIObhb3QAKOVd6_uct8cND6-bSE41HKxbIWhSGXGz6NWgtN0kg3qhvy1gElzsZY1lXpiozAKMA0wtcw3DJgYNP1z_PxCF3DyC09r1AaUEjYqC-xt76cfr8Y6RlT8cMZ7cX1ngSoy50EgabKAI8AODma67D7ORz1KooHMeyGuLRLAgefIuLbm-mFALAnPp1iI3KRSVoXDRhuLI2PH3VGpMqSYe0ddhI9TmyJ9kvNG9ONQPAK6UN9Tqj4= (дата обращения: 22.10.2025).
14. Теория графов • Информатика | Фоксфорд Учебник. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHo2KtSnYwSxKarS9e7QkqlX9HmCfjqv9UTQIYXLkQt_AQFP9jVV-pxfiOyiJb_00RuxrzPR01mcHyDYQ1996gTaQwZhGXBlKESnPZGLSjLJZlLm3opi2Amwc1Rj7vHKUECUraqypzKgjKRZLs= (дата обращения: 22.10.2025).
15. Теория графов — Викиконспекты. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEqbONHGXVD8ikDfuAarN8wT90mi9k-TYMCm2yGBv0-KkYTkoySh4FJ1DbUCWCyUFjSYc-98kDHS5EgQHtv6zivhFbAUcVUXoVNbbHSrcsSbRqbHxRGa8sq9ROKXmYFqo8DWhh66gFldu2eljHW8miIO0OSMkHTOEd9XwIJ09VfVP1giZIpERwd109Qs-fGitAWpFlC5i-ZPBaw3iAb7TIo-A2E9QiIg3B4Gwoj_dc= (дата обращения: 22.10.2025).
16. Hopcroft–Karp algorithm — Wikipedia. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEPPa_gOK2V5fAnqUoYXihb0gIcAcKr57RG6C8ZMdCKA74iTgRyO8v8_gc5qjYqFtmxRA1hluEvpGiJzAjYoC2di4JCP36reR9K_X_dYouxqnuDhGYPB93PB69so4Mn8I-_5vjzHeemt5npELxd3-AjGGApzU4NiA== (дата обращения: 22.10.2025).
17. Элементы теории графов. URL: https://vertexaisearch.google.com/grounding/AUZIYQEyfNaJbhuVzfG-cr76OsHFerHjGwETxXsieui25OEygBzusVCLVnddQXolui2g-YAI5SGThh0AIzH0Ji6MBW24aYogx9VN8Oa-KU9TWLeDb7p6Os6JVzw3UMavHRY= (дата обращения: 22.10.2025).
18. Рёберное ядро — Викиконспекты. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHLhS664p7JelWAGsURMGWBit8aWlIIQHeBx1eEsgKQGGvTP6koIWUyKzqYa7dB_WjFrZLTP2K1G1ygOy7269VH7FewSzfC4ST04emuP1EWTxO4JbMu2y6R_jsXhH7ka_wUx-sBDUoWOkYPjmKchWdj2RsudB8_SAo9pR32ItsD4wjBwoVDgOqS1r4gWrB_EKDoDv17zyp631FY77rS5iGq9zl8ITfznGNEKrUvhc= (дата обращения: 22.10.2025).
19. Паросочетание — WikiGrapp. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEz5ZHGwkuRJ8m5mYzDdA2XvyXQgKb2PDSw5Oc5m0p-ad7g_nCzSR2Hjs8aqvEi5VeUrSgNmo-Q-IwJAwvOv_FYtpSqPbpahnqwMpwK_kIpesJVW3KA8WDn8aIe09O4cCMmkl3OY3ovCv7UILMGMD2KxixiK3bdml3fhjkHRA4jWQZAUYb_pe9lg_eUo9Mnhepq_dSomB9s9TEH-eerd9wdgae4vmhejHtymExQhvS (дата обращения: 22.10.2025).
20. Независимое множество — Википедия. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGkvHyam0ZveuvhSjRvkz0l9cRGEfbOLQbMJy6LSRZOSqllmxDToqAIwdbdor1IPX-ZkdGcj_ZOOdtjZiaIgBedSt_43IX5aNU9DXq0tnpXQ1PB1PpmXywqQ_m3VZAxNVmdUSwu9tFRq-FuF0du_PEBw_iNAql85B0U0SXJ-ixKm9szX7vTgb4VFZTdE5rPSuoc5YA5-pjBBFGGglfxwQCgoCrLsdQxDRCeKRCAFOPZut9vxRHp090YDZHgYSSpe-Z9e0IhYhkJyL0STfxSZryKst8= (дата обращения: 22.10.2025).
21. это… Что такое Алгоритм Эдмондса — Карпа? — Словари и энциклопедии на Академике. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGOLt-z8iaBi_x6DgcJBIZ5Ek4ButgTwZ7z7UIG6UHMR-SLy8udbaZ7-nDXN3OrYaDdN231DF43gVc937U6_LrP5Du-NHLXPFqL58_dtGra4P2tNENakq5a_M-Kr8yb5wReElTxQpJE (дата обращения: 22.10.2025).
22. Алгоритм Эдмондса-Карпа, кратчайших увеличивающих цепей — AlgoList. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHGd5414J8DcSWw3q0ch9YDEML6F3Z6chWXsmLHIFj76jGju9JhZUrA9z33ohV27RBN-AuA69-wwuK3L8hQl-VsDS9XEcPX07br62QvSKysJMcxP5B4ONgezGKxfBAzCpzzQbGELusRroZs9nQS1KUrORSHIBw= (дата обращения: 22.10.2025).
23. Паросочетания в двудольных графах. Лекция 8 — презентация онлайн. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEV0LTJ8R5DNFmDTgu-xbOD8KXIUmpA3FzEI1Nb4hByfgdkY569bR5pASVnsyMOMQi9GYy-9hkxHqL8P3GKOvL-LNe-j_4-lJGeT1eY9lPAzQIs3xbarDbh (дата обращения: 22.10.2025).
24. графовые алгоритмы — Serg Sergius Project. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQF6eD5hX_vcAW7IiVEuVoL7bqeFIGWsf-6sJ6v1rwHM67G7p68s_FfZh5glfPCWv1fECZwMOhaA-2SySRE2-xtXcXZ_hJSk9g6yg_yKh8g1Bd4xNPDFpyBhpjl2csXhEhF1suX3Je86cSi72aY1O4w7OewCqy-8IczHwjTxwlHrULqQDwC3B3H6GNhQcUo56OD4FV-Xn5LsrUNB0uDctMRwZTH2fVT2R1L5196Gq23gA2gzBeHUpvSZ2A== (дата обращения: 22.10.2025).
25. 10 Графовых алгоритмов. Приведём краткое описание 10 основных… | by Андрей Шагин | NOP::Nuances of Programming. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQF_BwSfx6H7mRZDiZG72TXQKT355MNBXz-g0HegaHcF6AQ04RWv3TjjoMREYs9CfyD9FSitbf_DPuILyOFTIAWjT-XWTwIZj6MsAeoq0JjyZVFQGHLGiGwrZW1r_-8g5aGk71aSoxY5rSUCxW_H5yYVBhev2p-KAE5IAALe0rQWf2Kdc1eIoiBN2rDPHWfy6rIenfvjF8nVwAtpt9H_c-EqqEpSMCyLUkMtY-mrlY3pk73rAW8e1mxieghW-nJT1OZ6RguASBLbTju9qWNDm1GS5AX6p26cO_mOxZSHkrdOsUfdjJy3tiYkGboaPkDPfEJlzC1Z-wp8XcJU2Y0nOKLTkUkqdd1Ay0g9gGPmUmAfjjNepN2RqdBX154YZs8DK5rQdOuPt17oDUjZSJ_M2R2-XX5Ia3ycJStPrqhecjbMOeqZgA2dv3EFu7vq0ns-gvjjRIQEDv8= (дата обращения: 22.10.2025).
26. Алгоритм Эдмондса — Карпа — Википедия. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGpN72qLAabR2bDACQ2inVIf477wqgfVg6iqMgg171bufbi2pxTxsPhYZVpCucoG4jwZ-uLJkhjcdpcftfKuj83XZVpea89eXFep0jVGh_AFKf4gfq5yIv0FYx912xVW2Q0RiXTSp0XMZ3l_ph4QyMCkh3dNhORcoAK63lS1_w5TFFCNYttasG0HWhVSBeKCIgvXr4ETUMHd4zfOnyP2NPpjxiW8WSmW9RZIRvwKoIpFZ_ldtcN7cEDUmDzW593eeF-kJKd9aaJHBUHcCj2P4voyIQTd6jGXEm6uMaZmmzuEo—Tw== (дата обращения: 22.10.2025).
27. Алгоритм сжатия цветков — Википедия. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQErOnElbL3c_ggmZdFpzbZKF1drvImdkemcMq4LqR9xYgsdmz949mYO7ehEqTCUYiEfMcZKbGCgkeTi30f-vToF9OZIbDIRMWRP0S5vI0C64kPsZ9MmGC5g1k4vrVIW23r2cza_UT-smGyEGWLsT8oI0TvyN3UDAEh70JsKt5ORnJg693SU6UVURRG605fw9G9TW8pl5gNNq6xgimbP69QswNsKLApXvwkQy34cQLL1iTXVyvG3RlAfRv1YIlnP5pq_Vd3O5E2zKhcSCL0ae8DzX4kbLMDYFpKQ (дата обращения: 22.10.2025).
28. Лекция 1 | Паросочетания и факторы графа | Дмитрий Карпов | Лекториум — YouTube. URL: https://www.lektorium.tv/node/38947 (дата обращения: 22.10.2025).
29. Алгоритм Хопкрофта-Карпа — WEGA. URL: http://pco.iis.nsk.su/wega/index.php?title=Алгоритм_Хопкрофта-Карпа&oldid=5596 (дата обращения: 22.10.2025).
30. Максимальное паросочетание в графе — Блог программиста. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQG5AbpivnaTVBxOvQGSWLTTcSf3EHx4MKwC8eOJYsg3ESwHOfz5S9WK2j-QCrjC4pVsaGO8Ur8KSWbzY-JeqUrz0U7X_Y0LxrOthMRM8C1mL1fJG4OCnyNuxQ_fs7PbJVecHTF_HOsDNf_241txVA== (дата обращения: 22.10.2025).
31. Тема 6. Паросочетания и покрытия. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEi7wUUfmKTgHAnG8EUssGghAP-UC-l1rmEaoQxUGtY6pShl35hVsLliA9_U9FhgPWyysfFTQ6M7478PEQgnRJjKLgrHmlmnOQyajxvUr0p5rf6q5nfQ4nV3Zm1lM-BoJVmOe8o7DS1w8G_I3ZCoV8xsfb4KGo22ajjbJrlYs8Y6MPIt2D0 (дата обращения: 22.10.2025).
32. Алгоритм Эдмондса-Карпа — Викиконспекты. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHthkglQhWZJrEWDsb_VkJnNgzVEZsyLkvj9s67k3b34mWLy8-Gf7-acCDcJFdOFOtl8LEmkkwTiFl5Tqo9FUG2-gAa2gTpJCyRcKUAR3-6i1cBAK5KRUl3vhObygQ-XYiAPiuXnYbsd5i48er-5fg5mWn_1-pTj8zVHDiT7X6wyvEVZ_JYVZkTn_QON8a0nPRaNOPtthDmt973GPDYqqji46HY8kw3hps0blDtYam47QCHH-Cvn89VpSuZXdJ849EMwfB18N6-qVDKUkYsWY5KJyI3KYZwpoxfWHp4dr15Jw9iR9CRJ (дата обращения: 22.10.2025).
33. 10 алгоритмов для работы с графами, которые должен знать каждый кодер. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHzDWDXHV__wK2AB8X1fAJ4RaRF6Xp-aapCq0efDmsZXayNxM_-ssy0royM3_vM2bXsShBb9rPi466g-lI7YHZJhPBK_NwR6QOoF_F2U-BQRbWByzU-6RBWoCweS7oTelFjxlSJjsemrlUOfj3QpWJemK3NzQrzEJbHzZSC_cjeSinnRlq6alRJU3QL-h7DIrc_wJz6YSunl5w-6GXc_5T6 (дата обращения: 22.10.2025).
34. Задача о независимом множестве — Википедия. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEjdydX1aPLS8PgnzxR_4xttAOiyAer1qVZ5nPTYKLKHSnGf1aKf30f1w7kXT1Dehj61jtfaqUuXPr3B2sWbT-t2lB7DTbWx5Bpua_s_bStrx7M-qB2pkCn_fZPhF3TGuNTJMMCivqOmuqkvOasdQNlbilkPTwmiBSbB3n15uJFTlvzahzwjOmL0Blfh9JwigDFeJMVx0FkfCBrivXUnsNuwoTYspEskZglLIc6cf1yW-J4Q0a3dRebrLDY0lrW1_GBTH56gUE97884UtogtxPWL6lZxoJ6nlvAh3OU4yOE-Yz-xz8zT02WCZ46CNXBxlhq7BkddATLMvGRkhHRgg== (дата обращения: 22.10.2025).
35. Независимые множества. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHp3AVIX4k9HDRGwypOLefFHBxjvnoSXEBIykRkbi0wrJZTkfzre79mmcQeb7RO4Bavzg1zCk8DTVAQKz-Z5CA7z3Z97s4BOKulgOXXzED0AOzaFCjQlmnwIT7ScGa-VW4pkKQrfTE= (дата обращения: 22.10.2025).
36. Теория графов. Глава 3. Паросочетания. — GitLab. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGHpqEKCZC8VmJjY-LXyxuOKiEwMs_hRnAbmBZlr73pvKTA2NvNorLu8rOmwfPJp0QIFZkYmaD7LHsHfD25Blks0IjQsoD1GZC6aEseo_PpQGbN2ATth7aX4-5YjELbETKK2rmJyOwwrdjqBcWPKLTSv45uSLBqwIHQk5P_E9yW4GjZ4CX6G7mkpOvfW7yCKcXGwx4GRNxI (дата обращения: 22.10.2025).
37. АиСД S04E02. Максимальное паросочетание в недвудольном графе — Видео от CODE BLOG | ВКонтакте. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFrOkN8ZWjNC1qMrI3VzDL35HLWjrpwO9LycRYH2c5j2jduDZBjiMq8rM7fbw9eTGa7SjLgiZNadIOs-hWdUfJKw0Yt2LOwIanMVp1qTnEsaaFzsn0zq_wV6S8RRbaOaDDJKLWe2bUUrRWv4-Wm7-_7V2SdQcUhRsYqzFop173ZcFzz65PrK0hwCgQHVzEYsrWjtlqN42ab1w== (дата обращения: 22.10.2025).
38. Глава 11 Независимость и покрытия. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQG_KcWHsKIdlTqDi8I-b8a1sJGlhIKb5zYYEbMPSw80xW5jG21XM2i5ues5mXJm-v6CcU804HS2Yyc-5tJG89pOZV2g1TfYhTMthUISiC3Jtfbriwfz-SDyXt9TS9iMHefCdijgslI (дата обращения: 22.10.2025).
39. algo :: Алгоритм Эдмондса-Карпа нахождения максимального потока — e-maxx.ru. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGlE2xr8U0WiIgXHYM4cnXiqfrH_z83ruZ74hAd8UYhJS9mk2s7ReRVOzi2ErINjHr_ZzkIQ5b7XKkc5_KP8AzoaMPW2jHt_QM8QJEDJ8w0nmH1RA7m7Nu0MS3l6g== (дата обращения: 22.10.2025).
40. ЛЕКЦИИ ПО АЛГЕБРАИЧЕСКОЙ ТЕОРИИ ГРАФОВ. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFwfpdf-whi6Wvqlp9PIZ0QEY_WLxokI50QVpHYk7cFSge_7gR2TFKue1lJ8RAaW70LtogoHMJN5za0VP0MVDsntpmga4Nqa__Nr6kUXw_6x8wZ7kKERqv4V8d6HNwzEOIM6ybqZiv7Hnd274Sz4d99lVPK8o_shN4_QWrbgLvFUCq0a-nmyq2GZEoSeKKdCcU (дата обращения: 22.10.2025).
41. Графы и программирование / Хабр. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGXe07L_snMKZkP4SeJ46uyelhLslM4FVm4GL72M2ZVbfvZDGrWatPhIfwm9uA30g6nim88ArqIxNWr7Zs7jHuySyIrKQjs9wibm0aSFuve4z2NuQ7DCq8oIhaehu9Z (дата обращения: 22.10.2025).
42. Базовые алгоритмы на графах / Хабр. URL: https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQG7BCoiXjnGlbghMrZ1G6g3kF1k2J1q7BXRHbmkKsybD_2X-19ZJHgicpnK8n2HmeMQ32eZZu4pdfCNv8H-1R8DoX0WVzqJ-Urc4sEoob0UmmidQuwrRkK3zpu8zP9H2vNq9EqQQQdK4q_Tavcuccyw (дата обращения: 22.10.2025).