Przeskocz do treści

Delta mi!

Loading

Ukryte skojarzenia

Karol Pokorski

o artykule ...

  • Publikacja w Delcie: listopad 2013
  • Publikacja elektroniczna: 01-11-2013
  • Autor: Karol Pokorski
    Afiliacja: student, Wydział Matematyki i Informatyki, Uniwersytet Wrocławski

Przedstawimy tu dwa zagadnienia, w których pojawia się problem znajdowania najliczniejszego skojarzenia w grafie dwudzielnym, jednak trochę ukryty.

W pierwszym problemie mamy znaleźć tzw. pokrycie cyklowe grafu skierowanego. Pokrycie cyklowe grafu math  jest to zbiór cykli skierowanych math  takich że każdy wierzchołek należy do dokładnie jednego cyklu z  math  Chcielibyśmy szybko (tj. w czasie wielomianowym) odpowiadać na pytanie, czy dany graf ma pokrycie cyklowe, a jeśli tak, chcielibyśmy umieć wyznaczyć przykład takiego pokrycia.

Rozwiązanie jest zaskakująco proste. Stwórzmy nowy graf math  w następujący sposób: każdy wierzchołek math oryginalnego grafu math  rozbijamy w  math  na dwa wierzchołki, math i  math i jeśli w  math  istniała krawędź z  math do math to w  math  tworzymy krawędź z  math do math

obrazek

Okazuje się teraz, że jeśli najliczniejsze skojarzenie w  math  jest doskonałe (każdy wierzchołek jest skojarzony), to graf math  ma pokrycie cyklowe. Formalne udowodnienie tego faktu jest dość proste: wystarczy pokazać bijekcję ze zbioru pokryć cyklowych w  math  w zbiór skojarzeń doskonałych w  math  Szczegóły tego dowodu pozostawiam Czytelnikowi. Rysunek na marginesie podpowiada, jak tej bijekcji szukać.

Kolejnym przykładem zastosowania skojarzeń w rozwiązywaniu problemów jest wypełnianie kwadratów łacińskich. Kwadratem łacińskim nazywamy macierz (tabelkę) math w której każdy wiersz i każda kolumna jest permutacją ciągu math Przykłady kwadratów łacińskich poniżej:

obrazek

Rozważmy następujący problem: mamy kwadrat łaciński rozmiaru math w którym pokazano nam tylko math górnych wierszy (taki nie do końca wypełniony kwadrat nazywamy prostokątem łacińskim rozmiaru math). Chcemy zrekonstruować cały kwadrat łaciński, oczywiście możliwie najszybciej.

Zamiast próbować rozwiązać ten problem w pełnej ogólności, spróbujmy najpierw rozwiązać jego mniejszą część (informatycy tak lubią!). Taką częścią problemu mogłoby być poprawne uzupełnienie wiersza math Jak to zrobić?

Konstruujemy graf dwudzielny math  w którym wierzchołki z jednej grupy będą reprezentować kolumny, natomiast wierzchołki z drugiej grupy reprezentować będą liczby ze zbioru math które będziemy wpisywać do kolejnego wiersza. Jest już chyba jasne, że krawędź między math-tą kolumną a liczbą math należy stworzyć wtedy i tylko wtedy, gdy liczba math nie wystąpiła w  math-tej kolumnie. W takim grafie szukamy najliczniejszego skojarzenia. Jeśli jest ono doskonałe, wyznacza ono pewien poprawny sposób wypełnienia wiersza math:

obrazek

A co, jeśli w  math  nie znajdziemy skojarzenia doskonałego? Okazuje się, że taka sytuacja nigdy nie wystąpi! Zanim jednak udowodnimy ten fakt, zauważmy, że właśnie uzyskaliśmy algorytm uzupełniający prostokąt do kwadratu łacińskiego: wystarczy wypełniać kolejne wiersze poprzez znajdowanie kolejnych skojarzeń doskonałych, a użyte krawędzie wyrzucać z grafu. Po wyrzuceniu z grafu wszystkich krawędzi kwadrat łaciński będzie uzupełniony.

Nadszedł czas na dowód faktu, że w skonstruowanym zgodnie z powyższą metodą grafie math  zawsze istnieje skojarzenie doskonałe. Zauważmy, że graf math  jest grafem regularnym, czyli stopnie wszystkich wierzchołków są w nim takie same (są one równe math). Okazuje się, że w dwudzielnym grafie regularnym zawsze istnieje skojarzenie doskonałe.

Aby to wykazać, skorzystamy z twierdzenia Halla o małżeństwach. O twierdzeniu Halla pisaliśmy już w artykułach Kaskady i swaty oraz Skojarzenia w grafach kubicznych. Twierdzenie to głosi, że warunkiem koniecznym i dostatecznym na istnienie doskonałego skojarzenia w grafie dwudzielnym jest, aby każdy podzbiór wierzchołków z jednej grupy (załóżmy, że jest on mocy math) miał połączenie łącznie z co najmniej math wierzchołkami z drugiej grupy (jest to tzw. warunek Halla). Dowód naszego faktu wykorzystujący twierdzenie Halla jest bardzo prosty: rozważmy dowolny podzbiór math kolumn. Z każdego wierzchołka odpowiadającego tym kolumnom wychodzi math krawędzi, a więc łącznie mamy math krawędzi. Gdyby warunek Halla dla rozważanego podzbioru nie był prawdziwy, tzn. gdyby rozważany podzbiór był połączony krawędziami z mniej niż math wierzchołkami z drugiej grupy, to na mocy zasady szufladkowej Dirichleta do pewnego z tych wierzchołków musiałoby prowadzić więcej niż math krawędzi. To jednak jest niemożliwe, gdyż graf jest regularny. Stąd dla grafu math  warunek Halla jest rzeczywiście spełniony, więc math  ma skojarzenie doskonałe.

obrazek

Warto jeszcze dodać, że gdybyśmy dostali do uzupełnienia prostokąt łaciński wymiaru nie math tylko math jego uzupełnienie do kwadratu math mogłoby okazać się niemożliwe. Obrazuje to podany obok przykład.