Wykres izomorfizm z relacją równoważności na zbiorze wierzchołków

Kolorowy wykres można opisać jako krotkę $(G,c)$gdzie jest wykresem, a jest kolorem. Mówi się, że dwa kolorowe wykresy i są izomorficzne, jeśli istnieje izomorfizm prawy tak, że przestrzegane jest zabarwienie, tj. dla wszystkich .$G$$c : V(G) \rightarrow \mathbb{N}$$(G,c)$$(H,d)$$\pi : V(G) \rightarrow V(H)$$c(v) = d(\pi(v))$$v \in V(G)$

Pojęcie to oddaje izomorfizm kolorowych wykresów w bardzo ścisłym tego słowa znaczeniu. Rozważ przypadek, w którym masz dwie mapy polityczne tego samego regionu, ale używają one różnych zestawów kolorów. Gdyby zapytać, czy są kolorowe w ten sam sposób, można by założyć, że oznacza to, czy istnieje mapowanie bijectywne między dwoma zestawami kolorów, tak że kolory obu map pokrywają się dzięki temu odwzorowaniu. Pojęcie to mogą być zawarte opisując barwne wykresy jak krotki w którym jest stosunek równoważności w planie wierzchołkowego . Możemy wtedy powiedzieć, że dwa takie wykresy i są izomorficzne, jeśli istnieje izomorfizm taki, że dla wszystkich par$(G,\sim)$$\sim$$G$$(G,\sim_1)$$(H,\sim_2)$$\pi : V(G) \rightarrow V(H)$$v_1,v_2 \in V(G)$ utrzymuje, że

Moje pytanie brzmi, czy ta koncepcja była wcześniej badana, czy nie znajdowała form kanonicznych itp., A jeśli tak, to pod jaką nazwą jest znana?

Problem, który opisujesz, został zdecydowanie wzięty pod uwagę (pamiętam, że dyskutowałem o nim w szkole, a już wtedy był on omawiany na długo przedtem), chociaż nie mogę wskazać żadnych konkretnych odniesień w literaturze. Być może dlatego, że jest liniowo równoważny z bezbarwnym izomorfizmem grafu, jak następuje (dotyczy to nawet form kanonicznych). Zadzwoń do opisanego problemu EQ-GI.

GI jest tylko specjalnym przypadkiem EQ-GI, w którym każdy wykres ma tylko jedną klasę równoważności składającą się ze wszystkich wierzchołków.

W przeciwnym kierunku, aby zredukować EQ-GI do GI, niech będzie wykresem z relacją równoważności z wierzchołkami, krawędziami i klasami równoważności . wykres którego zestaw wierzchołków składa się z wierzchołków , wraz z nowymi wierzchołkami , po jednym dla każdej klasy równoważności w , a także nowych wierzchołków . Połącz w ścieżkę , połącz każde z i dla każdego wierzchołka w$(G, \sim_G)$$n$$m$$c$$G'$$G$$v_1, \dotsc, v_c$$=_G$$n+c+1$$w_0, \dotsc, w_{n+c}$$w_i$$w_0 - w_1 - w_2 - \dotsb - w_{n+c}$$v_i$$w_0$$G$ , podłącz go do odpowiedniej klasy równoważności wierzchołek . Wtedy ma co najwyżej wierzchołków i może być skonstruowany zasadniczo w tym samym czasie. (Ma również co najwyżej krawędzi - co jest dla połączonych wykresów - ale to nieco mniej istotne, ponieważ większość algorytmów GI ma czasy działania, które zasadniczo zależą tylko od .)$v_i$$G'$$n + 2c + n +1 \leq O(n)$$m + n + c + (n+c+1) \leq m + 4n + 1 \leq O(m+n)$$O(m)$$n$

Aktualizacja : Ponieważ w komentarzach pojawiło się zamieszanie, dodaję tutaj szkic poprawności powyższego argumentu. Biorąc pod uwagę i , niech i będą wykresami skonstruowanymi jak powyżej; niech oznacza wierzchołek z góry w , a ten w , i podobnie dla i . Jeśli występuje izomorfizm , musi wysłać do dla wszystkich$(G_1, \sim_1)$$(G_2, \sim_2)$$G_1'$$G_2'$$v_{i,1}$$v_i$$G_1'$$v_{i,2}$$G_2'$$w_{i,1}$$w_{i,2}$$G_1' \cong G_2'$$w_{i,1}$$w_{i,2}$$i$, ponieważ na każdym wykresie jest unikalnym wierzchołkiem, który jest punktem końcowym dowolnej ścieżki o długości co najmniej . W szczególności odwzorowuje na . Ponieważ sąsiedzi , którzy nie są są dokładnie , izomorfizm musi odwzorować zestaw na zbiór (w szczególności zarówno i muszą mieć tę samą liczbę klas równoważności ). Zauważ, że izomorfizm nie musi wysyłać do dla wszystkich$w_{n+c}$$n+c+1$$w_{0,1}$$w_{0,2}$$w_0$$w_1$$v_i$$\{v_{1,1},\dotsc,v_{c,1}\}$$\{v_{1,2},\dotsc,v_{c,2}\}$$\sim_1$$\sim_2$$c$$v_{i,1}$$v_{i,2}$$i$ , ale dozwolone jest permutowanie indeksów wartości , o ile odpowiednie klasy równoważności mogą być odwzorowane względem siebie. Z drugiej strony, na podstawie tego opisu, w jaki sposób isomorphisms między i może wyglądać, to łatwo zauważyć, że jeśli następnie daje to izomorfizm .$v$$G_1'$$G_2'$$(G_1, \sim_1) \cong (G_2, \sim_2)$$G_1' \cong G_2'$

Przeczytałem twój ostatni komentarz w poprawnej odpowiedzi Jozuego; jeśli chcesz przekształcić EQ-GI w kolorowy GI (tzn. masz problem z kolorami przypisanymi do klas równoważności), możesz zastosować następującą redukcję:

Załóżmy, że wykresy wyjściowe są , i są Klasy równoważne; następnie możesz dodać do każdego wykresu „permutator”, tj. pełny wykres na węzłach ( , ) i użyj kolorów .$G_1 = (V_1, E_1)$$G_2 = (V_2, E_2)$$q$$|V_1|+1=|V_2|+1$$K'_{|V_1|+1}$$K''_{|V_2|+1}$$q+1$$c_1,...,c_q,c_{q+1}$

Zarówno i , węzłach odznaczają i zabarwiona pozostałe węzły zabarwiony . Węzły są pokolorowane kolorem a węzły tej samej klasy równoważności są powiązane z odpowiednim kolorem w ; węzły są kolorowe kolorem a węzły w tej samej klasie równoważności są powiązane z odpowiednim kolorem w .$K'$$K''$$q$$c_1,...,c_q$$c_{q+1}$$G_1$$c_{q+1}$$K'$$G_2$$q+1$$K''$

Pamiętaj też, że możesz upuścić kolory i uzyskać równoważną instancję GI :-)

Redukcja odpowiadająca przykładowi w twoim komentarzu