Dopasowywanie Dwustronne: Znajdowanie Ścieżek Wzmacniających

Two sides, no edges within a side

A bipartite graph splits its vertices into two disjoint groups, left and right, with every edge running from one side to the other and never within a side. A matching is a subset of edges that share no endpoints - every vertex touches at most one matching edge. The problem this simulation shows is maximum matching: pick as many disjoint edges as possible. It is the mathematical skeleton of job assignment – workers on one side, tasks on the other, an edge wherever a worker is qualified for a task – as well as of stable roommate style pairing, kidney-exchange chains, and scheduling.

Augmentujący ścieżka

Zacznij od dowolnego dopasowania, nawet pustego. Augmentująca ścieżka to taki szlak, który rozpoczyna się w niezarejestrowanym wierzchołku po lewej stronie, kończy się w niezarejestrowanym wierzchołku po prawej stronie i przechodzi naprzemiennie: niezarejestrowany krawędź, zarejestrowana krawędź, niezarejestrowana krawędź i tak dalej. Odwróć każdą krawędź na tym szlaku - zarejestrowane krawędzie stają się niezarejestrowane, a niezarejestrowane krawędzie stają się zarejestrowane, a dopasowanie rośnie o dokładnie jeden element, ponieważ ścieżka ma o jeden niezarejestrowany element więcej niż zarejestrowany element. Teorem Berge'a stwierdza również odwrotność: dopasowanie jest maksymalne wtedy i tylko wtedy, gdy nie istnieje żaden ścieżka augmentująca w odniesieniu do niego, co daje czystą kryterium zatrzymania.

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());

Algorytm Kuhna i przyspieszenie Hopcrofta-Karpa

Powtarzanie wyszukiwania powyższego dla każdego niezwiązanej lewej wierzchołki, jedna po drugiej, to Algorytm Kuhna (również przypisany do specjalnego przypadku metody węgierskiej). Każde takie wyszukiwanie jest O(E) głębokim przeszukiwaniem i potrzebnych jest co najwyżej V takich wyszukiwań, dając O(V razy E). Hopcroft-Karp (1973) poprawia to, znajdując maksymalny zbiór najkrótszych, wierzchołkowo-rozłącznych ścieżek wzmacniających w jednej fazie BFS-then-DFS, zamiast jednej ścieżki na raz. Ponieważ długość najkrótszej ścieżki wzmacniającej rośnie ściśle z każdą fazą i jest ograniczona, potrzebne są tylko O(pierwiastek z V) faz, dając O(E razy pierwiastek z V) w całym procesie - duży praktyczny zysk, gdy graf ma tysiące wierzchołków.

Teoria Konigiego: dopasowywanie spotyka się z wierzchołkowym pokryciem

W dowolnym grafie bipartytowym rozmiar maksymalnego dopasowania jest równy rozmiarowi minimalnego pokrycia wierzchołków - najmniejszemu zbiorowi wierzchołków, który dotyka każdego krawędzia. Jest to teoria Konigiego i stanowi ona certyfikat: po znalezieniu dopasowania o wielkości k, udowodnić, że nie istnieje większe dopasowanie. Ta sama dwójność leży u podstaw twierdzenia max-flow min-cut, ponieważ dopasowanie bipartytowe jest dokładnie przepływem maksymalnym na sieci o pojemności jednostkowej z źródłem podłączonym do lewej strony i studnią podłączoną do prawej strony.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Bipartite Matching i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.