PL 
EnglishDomyślny
Українська💞 Skojarzenia w grafie dwudzielnym — ścieżki powiększające
Znajdź maksymalne skojarzenie w grafie dwudzielnym, wielokrotnie szukając ścieżek powiększających, które odwracają krawędzie skojarzone i nieskojarzone. To podstawa przydziału zadań i alokacji zasobów.
O skojarzeniach w grafach dwudzielnych
Graf dwudzielny dzieli swoje wierzchołki na dwa rozłączne zbiory — tutaj kandydaci po lewej i stanowiska po prawej — z krawędziami biegnącymi wyłącznie między tymi dwoma zbiorami, nigdy wewnątrz jednego. Skojarzenie to podzbiór krawędzi, w którym żaden wierzchołek nie pojawia się więcej niż raz; maksymalne skojarzenie to największy taki podzbiór osiągalny dla danego grafu. Klasycznym sposobem powiększania skojarzenia jest wielokrotne poszukiwanie ścieżki powiększającej: trasy, która zaczyna się i kończy w niesskojarzonych wierzchołkach i na przemian wykorzystuje krawędzie niesskojarzone i skojarzone. Odwrócenie każdej krawędzi na tej ścieżce zwiększa rozmiar skojarzenia dokładnie o jeden, a skojarzenie jest dowodliwie maksymalne właśnie wtedy, gdy nie pozostaje żadna ścieżka powiększająca. Wykonanie tego poszukiwania z każdego niesskojarzonego wierzchołka zajmuje O(V·E); algorytm Hopcrofta-Karpa poprawia to do O(E√V), znajdując kilka najkrótszych ścieżek powiększających w jednej fazie zamiast jednej. Poza teorią grafów skojarzenia dwudzielne modelują przydział pracy, alokację kursów oraz problemy stabilnego skojarzenia leżące u podstaw systemów przydziału do szkół i rezydentur medycznych.
Najczęściej zadawane pytania
Czym jest ścieżka powiększająca w skojarzeniach dwudzielnych?
Ścieżka powiększająca to sekwencja krawędzi, która zaczyna się i kończy w niesskojarzonych wierzchołkach, na przemian wykorzystując krawędzie spoza bieżącego skojarzenia i krawędzie w nim zawarte. Znalezienie takiej ścieżki i odwrócenie statusu każdej krawędzi na niej — skojarzona staje się niesskojarzoną i odwrotnie — zawsze zwiększa całkowity rozmiar skojarzenia dokładnie o jeden.
Dlaczego odwrócenie ścieżki powiększającej zwiększa rozmiar skojarzenia o jeden?
Ścieżka powiększająca zawsze ma o jedną krawędź niesskojarzoną więcej niż skojarzoną, ponieważ zaczyna się i kończy w niesskojarzonych wierzchołkach. Zamiana statusu każdej krawędzi na ścieżce przekształca więc k krawędzi niesskojarzonych w skojarzone i k−1 krawędzi skojarzonych w niesskojarzone — czysty zysk dokładnie jednej skojarzonej krawędzi, przy czym każdy wierzchołek na ścieżce pozostaje pokryty dokładnie jedną skojarzoną krawędzią.
Jak szybki jest algorytm Hopcrofta-Karpa w porównaniu z podejściem naiwnym?
Podejście naiwne — wielokrotne uruchamianie pojedynczego przeszukiwania w głąb w poszukiwaniu ścieżki powiększającej z każdego niesskojarzonego wierzchołka — zajmuje w najgorszym przypadku O(V·E), ponieważ może być potrzebnych do V ścieżek powiększających, a każde poszukiwanie kosztuje O(E). Hopcroft-Karp zamiast tego znajduje w jednej fazie maksymalny zbiór najkrótszych, rozłącznych wierzchołkowo ścieżek powiększających za pomocą jednego przejścia BFS+DFS, potrzebując tylko O(√V) faz, co daje łącznie O(E√V) — istotne przyspieszenie na dużych grafach.
Jakie rzeczywiste problemy rozwiązuje się za pomocą skojarzeń dwudzielnych?
Skojarzenia dwudzielne leżą u podstaw przydziału pracy i zadań (dopasowywanie pracowników do zgodnych ról), rekrutacji uniwersyteckiej i przydziału do rezydentur szpitalnych (prekursor algorytmu stabilnego skojarzenia Gale'a-Shapleya) oraz problemów przepływu w sieciach, takich jak planowanie i alokacja zasobów, gdzie maksymalizacja liczby skojarzonych par bezpośrednio maksymalizuje efektywne wykorzystanie ograniczonych zasobów.