Reordenar las matrices de adyacencia de regular los gráficos de modo que es la misma

Question

Dada una matriz a de Un fuertemente $k$ regular grafo G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). La matriz puede ser dividido en 4 sub matrices basadas en la adyacencia del vértice $x \in G$. $A_x$ es la matriz simétrica de la gráfica de $(G-x)$ donde $C$ es la matriz simétrica de la gráfica creada por los vértices de $(G-x)$ que no son adyacentes a $x$ $D$ es la matriz simétrica de la gráfica creada por los vértices de $(G-x)$ cuales son adyacentes a $x$.

$$ A_x = \left(\begin{array}{cccccc|ccc|c} 0&1&0&0&1&0&1&0&0&0\\ 1&0&1&0&0&0&0&1&0&0\\ 0&1&0&1&0&0&0&0&1&0\\ 0&0&1&0&0&1&1&0&0&0\\ 1&0&0&0&0&1&0&0&1&0\\ 0&0&0&1&1&0&0&1&0&0\\ \hline 1&0&0&1&0&0&0&0&0&1\\ 0&1&0&0&0&1&0&0&0&1\\ 0&0&1&0&1&0&0&0&0&1\\ \hline 0&0&0&0&0&0&1&1&1&0\\ \end{array}\right) = \left( \begin{array}{ccc} C & E & 0 \\ E^{T} & D & 1\\ 0 & 1 & 0\\ \end{array} \right) $$

Cabe señalar que

1. Intercambiando/intercambio de cualquiera de las dos filas (o columnas) de a $C$ no afecta a la matriz de $D$ (y viceversa).

2. Cualquier cambio en $C$ o $D$ o ambos $C$ $D$ cambios de la matriz $E$.

Problema: Si algunos vértices de $G$ es reordenado (es decir, permutada), $A$ será diferente, digamos, esta nueva matriz se $B$. De nuevo, la matriz de $B$ puede ser dividido en 4 sub matrices basadas en la adyacencia del vértice $x \in G$ $ B_x$ puede ser obtenida.

Asumir:

1. $C$ siempre es la matriz de adyacencia de un grafo y más grande que $D$.
2. Existe un algoritmo que siempre el fin de $D$ (para un vértice $x \in G$) se $O(K)$ tiempo (que se supone ser el polinomio/exponencial, no importa).

3. Cada fila de la E tiene diferentes permutación, es decir, las filas pueden tener el mismo número de 1's pero diferentes permutación/acuerdo de 1.

   Para $n$ vértices habrá total $n$ número de $C,D$, cada uno de ellos se llevará a $O(K)$ (que se supone ser el polinomio) tiempo para ordenar. Si cada una de las $C$ toma tiempo $O(f(n))$ a tipo, el total de la complejidad se $O(n \cdot K \cdot f(n))$.

Pregunta: de Acuerdo a los tres supuestos anteriores, no existe un polinomio tiempo algoritmo para ordenar $C$, de modo que $B=A$? I. e., existe un polinomio $f$ ?

El problema está conectado a esta pregunta.

Si algo no está claro, por favor pregunte a una pregunta específica, voy a intentar mi mejor esfuerzo para responder.

Answer 1

esta no será una directa respuesta a lo que no parece realmente un directo de la pregunta, que en su aparente gran alcance y la ambición empuja fuera de los límites de la SE, preguntas pero es, sin embargo, pretende ser un científico y orientar la respuesta. usted parece ser el estudio gráfico de isomorfismo en general, y como están aparentemente en cuenta precisa de la complejidad de este es un gran problema abierto. y es conocido, utilizado generalmente que los gráficos son los "duros" de GI de lo contrario, uno puede aprovechar uniforme vértice grados (normalmente) a disminuir significativamente el espacio de búsqueda de vértice permutaciones.

así que la mejor ruta para el estudio de duros que se conocen problemas científicos es relacionar su propio acercamiento a la literatura también conocido como "terra cognita", que es bastante grande en este tema. para los problemas de esta significativa, la mayoría de los enfoques directos son intentado/ analizado "en algún lugar". Aquí hay algunos bastante cerca de referencias a su técnica, comparten muchas similitudes. y, a continuación, la tarea es tratar de determinar cómo su técnica es diferente. Su idea básica de la asignación de columnas/ filas de la matriz de adyacencia a diferentes matrices es básicamente un algoritmo de partición de los vértices en los diferentes conjuntos. así:

• la complejidad de abrir las particiones / abierta la cuestión de por McKay en mathoverflow. él le pregunta acerca de la complejidad de la partición regular de los gráficos en el vértice de las particiones con la "equidad" de la propiedad, que puede ser similar a la suya. él es el escritor de nauty la parte superior de software gráfico de isomorfismo cálculos.

• Gráfico eficaz automorphism por el vértice de partición / Fowler et al. de lo abstracto, un algoritmo que se ejecuta en tiempo P para todos los gráficos de prueba, incluyendo regular gráficos.

Mi sugerencia es también para intentar convertir el problema de isomorfismo de las instancias y probar empíricamente nauty (sólo como el 1º de papel usos de pruebas empíricas, que es aceptado con condiciones en esta zona), y que puede ser uno de los más eficientes conocidos enfoques, porque nauty codifica grandes extensiones de estado-of-the-art conocimiento/ algoritmo(s) en el gráfico isomorfismo complejidad del estudio.

Answer 2

Solución Propuesta:

La disposición de $G$: $A$ es la matriz de la gráfica de $G$ donde $|G|=|A|=n$. Basado en la adyacencia de último vértice($n$ th vértice), puede ser dividido en 4 sub-matrices donde 2 son matrices simétricas($C,D$) y 2 no son matrices cuadradas($E^{T}, E$). Una matriz simétrica, dicen, $D$ , tiene el tamaño de $<n/2$. Repita todo el procedimiento para la matriz de $D$ $k$ th vértice $; 0<k<n$. Este procedimiento puede realizarse máximo $log_2(n)$ veces.

Descripción del Algoritmo:$A,B$ son matrices simétricas de los gráficos de $G,H$ respectivamente. Para $x \in G$,considere la gráfica de $(G-x)$, tiene vértices adyacentes a $x$ y vértices no adyacentes a $x$.

$ A_x$ es la matriz simétrica de la gráfica de $(G-x)$ donde $C$ es la matriz simétrica de la gráfica creada por los vértices de $(G-x)$ cuales son adyacentes a $x$ $D$ es la matriz simétrica de la gráfica creada por los vértices de $(G-x)$ que no son adyacentes a $x$.

$ A_x = \left( \begin{array}{cc} C & E \\ E^{T} & D\\ \end{array} \right)$

Cabe señalar, que-

1. Intercambiando/intercambio de cualquiera de las dos filas(o columnas) de a $C$ no afecta a la matriz de $D$ (y viceversa) . 2. Cualquier cambio en $C$ o $D$ o ambos $C$ $D$ cambios de la matriz $E$.

Si $G \simeq H $ existe $u \in H$, de modo que, $(G-x)\simeq (H-u)$, la matriz de $(H-u)$$B_u$, donde$ B_u= \left( \begin{array}{cc} S & R \\ R^{T} & Q\\ \end{array} \right) $

Considere la situación en la que $S \neq C,D \neq Q$. Desde $(G-x)\simeq (H-u)$ ,por lo tanto, existe una matriz de permutación $P$ ,por lo que el $PQ=D$. Una vez $Q$ está dispuesto exactamente igual a $D$ $C$ se pueden organizar en el no-tiempo exponencial el uso de la disposición de las filas de $E$ porque después de $Q=D$, las filas de $E$ $R$ sería el mismo pero dispuestos en orden diferente. Por ejemplo, en la 1ª hilera, puede ser colocado en la 4ª fila, pero la 1ª vta buscará mismo en la 4ª fila, aquí sólo se cambia el orden de(1º a 4º).

[ Una vez Q se arregla exactamente igual a D, no se puede cambiar / reordenar/ permutar vértices que hizo Q, porque si cambia / reordenar / permutar los vértices de P, entonces Q no va a ser igual a D. Si usted no puede cambiar a P(=D), entonces no habrá cambios de la columna R(que se espera igual a la E), como el cambio de cualquier columna en R cambio de P( pero no Es). Así que , después de todo, Q se arregla exactamente igual que D, el cambio puede ser hecho en S de la matriz, si usted cambia de S, entonces sólo las filas de E va a cambiar su orden].

Así, organizar el orden de las filas de $R$ como $E$, se hará $S = C$.