Delikatne wprowadzenie do izomorfizmu grafów dla grafów o ograniczonej wartościowości

Czytam o klasach grafów, dla których izomorfizm grafów ( ) jest . Jednym z takich przypadków są wykresy ograniczonej wartościowości (maksimum nad stopniem każdego wierzchołka), jak wyjaśniono tutaj . Ale uznałem to za zbyt abstrakcyjne. Byłbym wdzięczny, gdyby ktokolwiek mógł zasugerować mi referencje o charakterze ekspozycyjnym. Nie mam silnego doświadczenia w teorii grup, więc wolałbym artykuły, które wykorzystują teorię grupy w delikatny sposób (moje tło jest w CS).$GI$$P$

Algorytm grafu izomorficznego z ograniczonym stopniem jest tak ściśle związany z teorią grup (permutacji), że wątpię, by istniał wstęp, który używa grup „tylko delikatnie”. Możesz jednak skonsultować się z doktorem Paolo Codenottiego. praca dyplomowa dla pełniejszego tła. Nie obejmuje dokładnie izomorfizmu grafu ograniczonego stopnia, ale obejmuje potrzebne do niego narzędzia (a reszta pracy dotyczy hipergraphów ograniczonej rangi, rozszerzając najbardziej znany algorytm ogólnego izomorfizmu grafowego na przypadek hipergraphu ograniczonej rangi) .

Przyda ci się również książka Algorytmy teoretyki grupowej i izomorfizm wykresów , ponieważ obejmuje ona większość niezbędnego tła (rozdział 2, „Podstawowe pojęcia”, ma 47 stron) i jest znacznie bardziej spokojną ekspozycją niż większość opublikowanych artykułów na temat temat.

Oznaczenie: Niech jest wykresem, e = ( V, 1 , V, 2 ), krawędź X . Zestaw wierzchołek V k oznacza zbiór wierzchołków odległości k od E i pozwolić H mieć wysokość X .$X = (V,E)$$e = (v_1, v_2)$$X$$V_k$$k$$e$$h$$X$

Zgodnie z definicją , V = V 0 ∪ V 1 … V h oraz V ( h + 1 ) = ∅ . Pozwolić, podzbiór e k o krawędziach X ( 0 ≤ k ≤ H ) jest zdefiniowany AS$V_k$$V= V_0 \cup V_1 \dots V_h$$V_{(h+1)}= \emptyset$$E_k$$X(0 \leq k \leq h)$

$E_k = \{ (u,w) | u \in V_k, w \in V_ k \cup V_{(k+1)} \}.$

Podgrupa jest zdefiniowana jako-$X_i$

$X_k= (V_0 \cup V_1 \dots \cup V_k, E_0 \cup E_1 \dots E_{(k-1)} \}$

Na przykład $X_2 =\{ (V_0 \cup V_1 \cup V_2, E_0 \cup E_1)\}$

to grupa automorfizmów na wykresie X, w której e jest ustalone. Jeśli B jest zbiorem wytwórczych A u t e ( X k ) , piszemy ⟨ B ⟩ = u t e ( X k ) , na przykład, jest oczywiste, że u t e ( X 0 ) = ⟨ ( v 1 , wer. $Aut_e(X)$$X$$e$$B$$Aut_e(X_k)$$\langle B \rangle = Aut_e(X_k)$ Gdzie ( v 1 , V, 2 ) jest permutacją wierzchołków v 1 , v 2 o X .$Aut_e(X_0)=\langle(v_1,v_2)\rangle$$(v_1,v_2)$$v_1, v_2$$X$

Zasada Konstruowanie zespołu generującego grupę automorfizmów jest kompletnym problemem GI (graf izomorfizm) [1]. Jeśli więc możemy obliczyć generujący zbiór grupy automorfizmów X (który ograniczył wartościowość w czasie wielomianowym), możemy rozwiązać GI w czasie wielomianowym. Tak więc chcemy ustalić A u t e ( X ) .$X$$X$$Aut_e(X)$

Technika:

Zbudujemy . Dla każdej X k mamy skonstruuje A u t e ( X ( k )$X_0, X_1..... X_h$$X_k$$Aut_e(X_{(k)})$

Należy zauważyć, że permutacją może być rozszerzony do automorfizmem A u t e ( X ( k + 1 ) ) .$Aut_e(X_{(k) })$$Aut_e(X_{(k+1)})$

Tak więc, generatory U t e ( x ( k + 1 ) ) można otrzymać z generatorów o A u t e ( X k ) .$Aut_e(X_{(k+1)})$$Aut_e(X_{k})$

Do generatora budowy, struktura, typ jest manipulowany. Konstrukcja-typ E k mogą być podzielone na klasy skończonych. Na przykład w przypadku trójwartościowym istnieje tylko sześć typów (w rzeczywistości może wystąpić tylko pięć takich przypadków).$E_k$$E_k$

Sklasyfikujemy krawędzie w do typów i zgrupujemy je w rodziny. Pomaga to stworzyć wiele unikalnych etykiet.$E_k$

W przypadku stałej wartościowości liczba etykiet jest niewielka. W tym momencie używamy koncepcji stabilizatorów ustawionych w celu znalezienia permutacji, które działają na konkretną etykietę. W tym procesie znajdujemy generator . Następnie używamy generator A u t e ( X ( k ) ) , aby znaleźć generator A u t e ( X ( k + 1 ) ) , jak wspomniano wcześniej. Postępując w ten sposób, otrzymujemy: A $Aut_e(X_{(k) })$$Aut_e(X_{(k) })$$Aut_e(X_{(k+1) })$$Aut_e(X)$