I. Skojarzenia- wstęp
Skojarzeniem nazywamy taki podzbiór krawędzi grafu, że każdy wierzchołek jest styczny z co najwyżej jedną krawędzią. Będziemy zajmować się skojarzeniami w grafach dwudzielnych. Graf dwudzielny to taki, w którym wierzchołki są podzielone na 2 zbiory, a każda krawędź łączy wierzchołki z 2 różnych zbiorów.
Wyobraźmy to sobie na następującym przykładzie:
Mamy dane 2 zbiory wierzchołków: X i Y. Niech X oznacza kobiety, a Y mężczyzn. Dla każdej kobiety/ każdego mężczyzny określone jest kto może jej/jego potencjalnym partnerem/potencjalna partnerką (potencjalni partnerzy muszą być różnej płci xD). Zatem mamy dany graf dwudzielny, gdzie krawędzie (E) łączą 2 różne zbiory(X,Y). Skojarzenia dokonamy tworząc pary kobieta-mężczyzna (parę mogą tworzyć tylko osoby uznające wcześniej za potencjalnych partnerów) przy czym każdej kobiecie przyporządkowany jest co najwyżej 1 mężczyzna i vice versa -tworzymy więc podzbiór rozłącznych wierzchołkowo krawędzi E). Liczność skojarzenia to liczba utworzonych par.
Skojarzenie maksymalne- skojarzenie mające największą możliwą liczność.
Skojarzenie doskonałe- skojarzenie, którego liczność jest równa liczności zbioru X i jednocześnie liczności zbioru Y(tzn. takie, w którym żadna kobieta ani żaden mężczyzna nie zostaje na lodzie).
Ścieżka powiększająca (naprzemienna)- taki ciąg różnych krawędzi w którym co druga należy do skojarzenia oraz pierwszy i ostatni wierzchołek są wolne.
Twierdzenie Halla: W grafie istnieje skojarzenie doskonałe <=> dla każdego podzbioru ilość jego sąsiadów jest co najmniej tak samo liczna jak wierzchołki w tym podzbiorze. Czyli innymi słowy: wtedy i tylko wtedy, gdy dla każdego podzbioru kobiet ich potencjalni partnerzy są co najmniej tak samo liczni i dla każdego podzbioru mężczyzn ich potencjalne partnerki są co najmniej tak samo liczne.
II. Jak znaleźć skojarzenie maksymalne?
1. Metoda z wykorzystaniem przepływów
Do danego grafu dodajemy 2 wierzchołki A i B. Z wierzchołka A tworzymy krawędzie skierowane do każdego wierzchołka ze zbioru X. Z każdego wierzchołka ze zbioru Y tworzymy krawędzie skierowane do wierzchołka B. Szukamy maksymalnego przepływu z A do B- jest to właśnie maksymalne skojarzenie.
Idea metod 2. i 3. jest następująca:
Załóżmy, że w grafie dwudzielnym mamy znalezione jakieś skojarzenie, które nie jest maksymalne. Aby powiększyć liczbę skojarzonych par, szukamy ścieżki powiększającej: zaczynając od dowolnego nieskojarzonego wierzchołka ze zbioru X idziemy na przemian po krawędziach należących i nienależących do skojarzenia, aż dojdziemy do takiego wierzchołka ze zbioru Y, który nie jest skojarzony. Tak znalezioną ścieżkę powiększającą odwracamy, tzn. leżące na niej krawędzie, które należały dotychczas do skojarzenia oznaczamy jako nieskojarzone i vice versa- nienależące dotychczas do skojarzenia oznaczamy jako skojarzone. Ponieważ ścieżkę powiększającą tworzy nieparzysta liczba krawędzi, a ostatnia z nich nie należała pierwotnie do skojarzenia, to odwrócenie ścieżki gwarantuje zwiększenie liczby skojarzeń. Jeśli znalezienie jakiejkolwiek ścieżki powiększającej nie jest już możliwe, oznacza to, że skojarzenie jest maksymalne.
Jeśli nie mamy na początku danego skojarzenia, to po prostu szukamy ścieżki powiększającej od kolejnych nieskojarzonych wierzchołków. Ścieżka powiększająca może składać się z jednej krawędzi (łączącej dany wierzchołek z jego nieskojarzonym jeszcze sąsiadem).
2. Metoda z wykorzystaniem BFSa ()
Metoda ta opiera się na znajdowaniu ścieżki powiększającej i odwracaniu jej.
Wszystkie nieskojarzone wierzchołki ze zbioru X wrzucamy na kolejkę i oznaczamy jako odwiedzone. Odpalamy BFSa. Dla każdego ściągniętego z kolejki wierzchołka u przeglądamy jego sąsiadów.
- Jeśli dany sąsiad v jest skojarzony, wrzucamy na kolejkę jego partnera w (jeśli nie był odwiedzony), oznaczamy, że wierzchołek w został odwiedzony i że wierzchołek u jest jego przodkiem.
- Jeśli dany sąsiad v jest nieskojarzony, kojarzymy parę u-v (znaleźliśmy ścieżkę powiększającą). Jeśli wierzchołek u był już wcześniej skojarzony, to (przed skojarzeniem pary u-v) likwidujemy to skojarzenie i przechodzimy od wierzchołka u po jego przodkach, zmieniając odpowiednio skojarzenia (np. jeśli partnerem wierzchołka u był wierzchołek w, kojarzymy wierzchołek w z przodkiem wierzchołka u likwidując jednocześnie ewentualne poprzednie skojarzenie przodka wierzchołka u. Postępujemy analogicznie dla ewentualnego przodka przodka wierzchołka u itd., tzn. aż do momentu, gdy dotrzemy do wierzchołka, który przodka nie ma)-jest to właśnie odwracanie ścieżki.
3. Metoda z wykorzystaniem DFSa (to będziemy klepać)
Podobnie jak wersja z BFSem metoda ta opiera się na znajdowaniu ścieżki powiększającej i odwracaniu jej.
Dla każdego nieskojarzonego wierzchołka u należącego do zbioru X odpalamy DFSa. W DFSie przeglądamy wszystkich potencjalnych partnerów danego wierzchołka. Jeśli dany potencjalny partner v nie jest jeszcze skojarzony, możemy go skojarzyć z wierzchołkiem u i zakończyć DFSa (znaleźliśmy ścieżkę powiększającą). W przeciwnym razie odpalamy DFSa od wierzchołka w, z którym skojarzony jest wierzchołek v (jeśli wierzchołek w nie był jeszcze odwiedzony) i tym samym sprawdzamy czy istnieje możliwość skojarzenia wierzchołka w z wierzchołkiem innym niż v (i dokonać takiego skojarzenia, likwidując skojarzenie v-w). Jeśli tak jest możemy spokojnie skojarzyć wierzchołek u z wierzchołkiem v.
Pseudokod wygląda następująco:
mate_X[i]-należący do zbioru X partner należącego do zbioru Y wierzchołka i (kobieta skojarzona z mężczyzną i)
mate_Y[i]-należący do zbioru Y partner należącego do zbioru X wierzchołka i (mężczyzna skojarzony z kobietą i)
visited_X[]-tablica odwiedzin dla wierzchołków ze zbioru X
visited_Y[]-tablica odwiedzin dla wierzchołków ze zbioru Y
bool p=true;
while(p)
p=false;
for i=1 to |x|//|x|- liczność zbioru X
if(mate_Y[i]==NULL)//wierzchołek i jest nieskojarzony
if(DFS(i)) p=true;
wyczyść visited;
bool DFS(u)
{
visited_X[u]=true;
foreach v-nieodwiedzony sąsiad u (!visited_Y[v])
if(mate_X[v]==NULL)//jeśli v nie jest skojarzony
{
visited_Y[v]=true;
mate_X[v]=u;//kojarzymy parę (u,v)
mate_Y[u]=v;
return true;
}
else
{
w=mate_X[v];//w-wierzchołek skojarzony z v
if(DFS(w))//jeśli jesteśmy w stanie skojarzyć go z innym wierzchołkiem
{
visited_Y[v]=true;
mate_X[v]=u;//kojarzymy parę (u,v)
mate_Y[u]=v;
return true;
}
}
return false;
}
Jak łatwo zauważyć, kod ten można skrócić, gdyż w przypadku gdy wierzchołek v nie jest jeszcze skojarzony postępujemy tak samo jak gdy można go skojarzyć z jakimś innym wierzchołkiem. Po skróceniu kod wygląda następująco:
bool DFS(u)
{
oznacz u jako odwiedzony;
foreach v-nieodwiedzony sąsiad u (!visited_Y[v])
if(mate_X[v]==NULL||DFS(mate_X[v]))
{
visited_Y[v]=true;
mate_X[v]=u;
mate_Y[u]=v;
return true;
}
return false;
}
Możemy też zrezygnować z używania tablicy visited_Y. Zauważmy, że przeglądając wierzchołki ze zbioru Y mamy 2 możliwości:
- jeśli dany wierzchołek nie jest skojarzony, to znaczy, że nie był odwiedzony
- jeśli jest skojarzony, to wystarczy sprawdzić, czy jego partner był odwiedzony
Złożoność:
Złożoność DFSa to 0(E). Za każdym wywołaniem DFSa liczność skojarzeń wzrasta maksymalnie o 1. Skojarzeń może być maksymalnie V. Złożoność wynosi zatem 0(V*E)
Dlaczego to działa?
Bóg jeden wie xD1
III. Zadanie α
Jaką maksymalną liczbę wież możemy ustawić na szachownicy, aby się nie atakowały? Tyle, ile jest maksymalnie skojarzeń w grafie dwudzielnym, w którym jeden zbiór wierzchołków stanowią wiersze, a drugi – kolumny. Jeśli pole (x,y) nie zostało zjedzone przez korniki, znaczy to, że kolumna y jest potencjalnym partnerem wiersza x.
