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

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

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

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

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

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

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

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