Grupa krotek tak, że każdy element w grupie nie ma wspólnych elementów z innymi członkami.

Question

Więc natknąłem się na problem w świecie rzeczywistym, który wygląda tak: mamy listę par, które musimy podzielić na grupy. Chcemy zminimalizować liczbę grup, które mamy w sumie, z ograniczeniem, że dowolny członek grupy nie może współużytkować elementu z żadnym innym członkiem grupy.

Oto przykład. Nasza lista krotek to (A, B), (B, C), (C, A), (D, E), (F, G). Możemy utworzyć trzy grupy wykonując [(A, B), (D, E), (F, G)], [(B, C)], [(C, A)].

Czy możliwe jest optymalne rozwiązanie tego problemu w czasie wielomianowym? Jak złe jest to chciwe rozwiązanie? Możliwe, że został przedstawiony jako inny problem, ale nie jestem w stanie wymyślić, jak zredukować go do czegoś innego (przypuszcza się kolorowanie graficzne).

Answer 1

Problem opisany jako edge-coloring problem: masz wykres, w którym każda pozycja krotki jest węzłem, a krawędzie są podawane przez krotki. Grupowanie krotek w grupy odpowiada zatem znajdowaniu grup krawędzi, które nie współdzielą punktów końcowych (dopasowań), którym można przypisać ten sam kolor przy kolorowaniu krawędzi. Innymi słowy, każde zabarwienie krawędzi daje skupienie, a każde grupowanie daje kolorystykę krawędzi. Niestety, jest to NP - trudno znaleźć najlepszą kolorystykę krawędzi, więc Twoim problemem jest ogólnie NP -hard. Istnieją algorytmy aproksymacyjne dla tego problemu, które dają przybliżenia w postaci stałego współczynnika, ale chyba że nie ma dokładnego algorytmu.

Jeśli uogólnisz ten problem, aby pozwolić na dowolną liczbę elementów na krotkę, wtedy problem ten staje się o wiele trudniejszy. Ogólną wersją tego problemu jest rzeczywiście NP - trudne i bardzo trudne do przybliżenia, poprzez zmniejszenie kolorystyki wykresu. Pokażę przykład redukcji w konkretnej sprawie, ale generalizuje ona całkiem ładnie.

Biorąc pod uwagę wykres podobny do tego:

A -- B -- C 
| | | 
D -- E -- F 

Będziemy tworzyć zbiór krotek, po jednej dla każdego węzła, gdzie każdy wpis w krotka jest zbiorem krawędzi przyległych do tego węzła. Na przykład, w powyższym wykresie, chcemy tworzyć te krotki:

(AB, AD) 
(AB, BC, BE) 
(CB, CF) 
(AD, DE) 
(BE, DE, EF) 
(CF, EF) 

Teraz wyobraź sobie, że dwa z tych krotek nie pokrywają się. Oznacza to, że dwa węzły odpowiadające tym krotkom nie mogą przylegać, ponieważ gdyby były, krawędź między nimi byłaby wspólnym elementem w krotkach, a zatem nie mogłyby być skupione. Z drugiej strony, jeśli dwa węzły nie sąsiadują ze sobą, wówczas ich krotki mogą być zgrupowane w tym samym skupisku, ponieważ w drugiej nie będzie widoczna krawędź w jednej krotce.

Biorąc pod uwagę tę konfigurację, dowolna kolorystyka oryginalnego wykresu daje sposób grupowania krotek (wszystkie krotki dla węzłów o tym samym kolorze w tym samym zestawie, żadne z nich nie sąsiadują ze sobą, więc nie powodują konfliktu), i dowolny sposób grupowania krotek daje kolorowanie (kolor wszystkie węzły odpowiadające każdej krotce w klastrze tego samego koloru). Dlatego znalezienie minimalnej liczby klastrów odpowiada znalezieniu liczby chromatycznej oryginalnego wykresu, która jest NP - trudna i nieznana, aby przyjąć jakiekolwiek algorytmy aproksymacyjne, które uzyskałyby wartość zbliżoną do rzeczywistej.