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

Abstract

Один з ключових питань у теорії графів - це знаходження оптимальних паросполучень у двудольних графах. Двудольні графи є особливими, оскільки їх вершини можна розділити на дві неперетинаючіся множини або "долі". Знаходження оптимального паросполучення полягає у знаходженні найбільшої множини ребер, які не мають спільних вершин та з'єднують вершини з однієї долі з вершинами з іншої долі.
Для вирішення цієї задачі розроблено кілька алгоритмів, серед яких одним з найвідоміших є алгоритм Унгарія, також відомий як алгоритм Куна. Цей алгоритм заснований на теорії матричних ігор та використовує метод пошуку шляхів з покращеннями.