Monthly Archives: Grudzień 2010

Największa klika w grafie

Projekt z Optymalizacji Kombinatorycznej. NP-trudny; z optymalnym rozwiązaniem ciężko. Pomysłów sporo, złożoności różne, nie zawsze adekwatne do jakości rozwiązań. Wybór padł na najszybszy. Trafnie – łatwa implementacja, czasy poszukiwań króciutki, wyniki powyżej 60% optymalnych rozwiązań, w wielu przypadkach optymalne. Może kiedyś się przyda, więc piszę jak to działa. Żeby nie pisać od nowa, cytuję fragment pracy (całej zamieścić nie mogę).

Etap I – sortowanie
Pierwszy etap działania algorytmu to sortowanie wektora zawierającego opisy wierzchołków.
Wektor sortowany jest malejąco, kluczem sortowania jest natomiast stopień wierzchołka.
Celem sortowania jest ustalenie, który wierzchołek ma największy stopień, ponieważ będzie to
najlepszy kandydat na „podstawę”, od której zaczniemy budowanie kliki. Wynika to z naszego
założenia, że im więcej krawędzi prowadzi do tego wierzchołka (czyli im większy jego stopień),
tym większe prawdopodobieństwo, że to na nim opiera się największa klika istniejąca w grafie
(ponieważ ma najwięcej sąsiadów).

Etap II – rozbudowa kliki
Mając wybrany wierzchołek o najwyższym stopniu przystępujemy do budowy kliki. Umieszczamy
go w nowej strukturze danych (w naszym przypadku wektorze, choć lista jednokierunkowa też
byłaby dobrym pomysłem).
Kolejno sprawdzamy elementy znajdujące się w posortowanym wektorze dalej, niż wybrany
wcześniej wierzchołek. Jeśli wierzchołek jest sąsiadem wierzchołka, na którym budujemy klikę, to
powiększamy ją o nowy wierzchołek i przechodzimy do kolejnego. Jeśli nie jest sąsiadem
„podstawy” to po prostu przechodzimy dalej.
Dodając kolejne wierzchołki postępujemy podobnie, z tym, że dodajemy je do kliki wtedy i tylko
wtedy, gdy są one sąsiadami wszystkich wierzchołków znajdujących się już w klice. Czynność
powtarzamy do czasu „zużycia” wszystkich wierzchołków.
Przy dodawaniu nie są brane pod uwagę wierzchołki, których stopień jest mniejszy od rozmiaru
aktualnie znalezionej kliki (ponieważ nie ma szans, by miały wspólną krawędź z wszystkimi
znajdującymi się już w klice).

Łatwo zauważyć kwadratową złożoność algorytmu. Jeśli ktoś byłby chętny, gotów jestem udostępnić fragmenty kodów w C++ oraz wyniki przeprowadzonych testów efektywnościowych.