Introducción suave al isomorfismo gráfico para gráficos de cenefa acotada

Estoy leyendo sobre las clases de gráficos para los que isomorfismo de grafos ( ) se encuentra en . Uno de esos casos son los gráficos de valencia acotada (máximo sobre el grado de cada vértice) como se explica aquí . Pero lo encontré demasiado abstracto. Estaría agradecido si alguien me puede sugerir algunas referencias de naturaleza expositiva. No tengo una sólida formación en teoría de grupos, por lo que preferiría trabajos que utilicen la teoría de grupos de manera amable (mi experiencia es en CS).$GI$$P$

El algoritmo para el isomorfismo gráfico de grado acotado está tan estrechamente relacionado con la teoría de grupos (permutación) que dudo que haya una introducción que use grupos "solo suavemente". Sin embargo, puede consultar el doctorado de Paolo Codenotti. tesis para un fondo más completo. No cubre exactamente el isomorfismo gráfico de grado acotado, pero cubre las herramientas necesarias para ello (y el resto de la tesis trata sobre hipergrafías de rango acotado, extendiendo el algoritmo más conocido para el isomorfismo gráfico general al caso de hipergrafía de rango acotado) .

También puede encontrar útil el libro Algoritmos teóricos grupales e isomorfismo gráfico , ya que cubre la mayor parte de los antecedentes necesarios (Capítulo 2, "Conceptos básicos", tiene 47 páginas) y es una exposición mucho más pausada que la mayoría de los artículos publicados sobre El tema.

Notación: Let ser gráfica, e = ( v 1 , v 2 ) un borde de X . El conjunto de vértices V k el conjunto de vértices de distancia k de e , y dejar que h sea la altura de X .$X = (V,E)$$e = (v_1, v_2)$$X$$V_k$$k$$e$$h$$X$

Según la definición de , V = V 0 ∪ V 1 ... V h y V ( h + 1 ) = ∅ . Supongamos que el subconjunto E k de las aristas de X ( 0 ≤ k ≤ h ) se define como-$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)} \}.$

El subgrafo se define como:$X_i$

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

Por ejemplo, $X_2 =\{ (V_0 \cup V_1 \cup V_2, E_0 \cup E_1)\}$

es el grupo de automorfismo del gráfico X donde e es fijo. Si B es un conjunto de generación de A u t e ( X k ) , escribimos ⟨ B ⟩ = A u t e ( X k ) , por ejemplo, está claro que A u t e ( X 0 ) = ⟨ ( v 1 , v $Aut_e(X)$$X$$e$$B$$Aut_e(X_k)$$\langle B \rangle = Aut_e(X_k)$ Donde ( v 1 , v 2 ) es una permutación de vértices v 1 , v 2 de X .$Aut_e(X_0)=\langle(v_1,v_2)\rangle$$(v_1,v_2)$$v_1, v_2$$X$

Principio La construcción de un grupo generador de automorfismo de es un problema completo de GI (isomorfismo gráfico) [1]. Entonces, si podemos calcular el conjunto generador de grupo de automorfismo de X (que tiene una cenefa acotada en tiempo polinomial), podemos resolver GI en tiempo polinomial. Entonces, deseamos determinar A u t e ( X ) .$X$$X$$Aut_e(X)$

Técnica:

Construiremos . Para cada uno, X k construiremos A u t e ( X ( k )$X_0, X_1..... X_h$$X_k$$Aut_e(X_{(k)})$

Tenga en cuenta que una permutación de puede extenderse a un automorfismo de A u t e ( X ( k + 1 ) ) .$Aut_e(X_{(k) })$$Aut_e(X_{(k+1)})$

Entonces, los generadores de se pueden obtener de los generadores para A u t e ( X k ) .$Aut_e(X_{(k+1)})$$Aut_e(X_{k})$

Para construir el generador, se manipula el tipo de estructura de . El tipo de estructura de E k se puede dividir en clases finitas. Por ejemplo, en el caso trivalente, solo hay seis tipos (solo cinco de esos casos pueden ocurrir).$E_k$$E_k$

Clasificaremos los bordes en en tipos y los agruparemos en familias. Esto ayuda a crear una serie de etiquetas únicas.$E_k$

Para una valencia fija, el número de etiquetas es pequeño. En este punto, usamos el concepto de estabilizadores setwise para encontrar permutaciones que actúan en una etiqueta en particular. En el proceso, encontramos el generador de . Luego, usamos el generador de A u t e ( X ( k ) ) para encontrar el generador de A u t e ( X ( k + 1 ) ) , como se indicó anteriormente. Procediendo de esta manera, obtenemos, A $Aut_e(X_{(k) })$$Aut_e(X_{(k) })$$Aut_e(X_{(k+1) })$ .$Aut_e(X)$