Двобічне зіставлення: Пошук доповнювальних шляхів

Дві сторони, без країв всередині сторін

Бінарне зіставлення розділяє вершини графа на дві групи - ліву та праві, і з'єднує їх ребрами, ніколи не з'єднуючи вершини одного боку. Зіставлення – це підмножина ребер, що не мають спільних кінців; кожна вершина торкається максимум однієї межі зіставлення. Мета моделювання - знайти максимальне зіставлення: вибрати якомога більше незалежних ребер. Це математична основа для призначення робіт – працівники з одного боку та завдання з іншого, де ребро представляє кваліфікацію працівника до виконання завдання – а також для стабільного парів у житлових будинках, ланцюгів обміну нирками та планування.

Довкірна трацепта

Почніть з будь-якого відповідності, навіть порожньої. Довкірна трацепта – це шлях, що починається від непарного лівого вершини, закінчується на непарному правому вершині та чергує: непарний край, парний край, непарний край і так далі. Переверніть кожен край вздовж цього шляху - парні краї стають непарними, непарні краї стають парними - і відповідність зростає на один край, оскільки шлях має на один непарний край більше, ніж парний. Теорема Берже говорить про те ж саме: відповідність є максимальною лише тоді, коли її немає жодного довкірного шляху відносно неї, що дає чітке критерій зупинки.

function tryAugment(u, visited) {           // Kuhn's algorithm, one DFS per left vertex
  for (const v of adj[u]) {
    if (visited.has(v)) continue;
    visited.add(v);
    if (matchR[v] === -1 || tryAugment(matchR[v], visited)) {
      matchR[v] = u; matchL[u] = v;
      return true;                            // found and flipped an augmenting path
    }
  }
  return false;
}
for (const u of leftVertices) tryAugment(u, new Set());

Алгоритм Куна та пришвидшення Хопкрофта-Карпа

Повторення пошуку верхнього лівого вершини, один за одним, є алгоритмом Куна (також відомим як метод угоди з фігурами). Кожен пошук — це O(E) глибинний пошук, і потрібно до V пошуків, що дає O(V разів E). Хопкрофт-Карп (1973) покращує це шляхом знаходження максимального набору найкоротших, вершинами неперервних розширюючих шляхів у одній фазі BFS-then-DFS замість одного шляху за раз. Оскільки довжина найкоротшого розширення шляху строго збільшується з кожної фази та обмежена, потрібно лише O(квадратний корінь з V) фаз, що дає загалом O(E разів квадратний корінь з V) — значна практична перевага, коли граф має тисячі вершин.

Теорема Königs: відповідність зустрічається з покриттям вершин

У будь-якому бінарному графі розмір максимального підмножчого відповідності дорівнює розміру мінімального покриття вершин - найменшому набору вершин, що торкається кожної ребра. Це теорема Königs, і вона перетворює відповідність у сертифікат: як тільки ви знайдете відповідність розміром k, яка демонструє покриття вершин того ж розміру, це доводить на місці, що не існує більшої відповідності. Та ж подвійність лежить в основі теореми про максимальний потік та мінімальне розрізання, оскільки бінарне підмножче відповідності є точно максимальним потоком у мережі з одиничною місткістю з джерелом, підключеним до лівого боку, і приймачем, підключеним до правого боку.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Bipartite Matching і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.