¿Tienen los grafos isomórficos los mismos valores para las matrices de adyacencia y el espectro?

Question

Hay dos grafos isomórficos para los que quiero encontrar su espectro (sus valores propios). Estoy confundido que el espectro será el mismo para ambos gráficos ya que son isomorfos, pero no estoy seguro.

Primero escribí la matriz de adyacencia para ambos y también son iguales, a menos que haya hecho algo mal. Los gráficos tienen nodos codificados por colores, así que cuando hice las matrices de adyacencia para ambos, escribí los nodos de la manera codificada por colores (como el mapeo de los nodos del primer gráfico a otro gráfico para la fila y la columna de la matriz de adyacencia, y por lo tanto, los valores tenían que ser los mismos). Pero también hice la matriz de adyacencia para el segundo gráfico de acuerdo con los números-etiquetas dados a los nodos, y entonces la respuesta tuvo que ser diferente porque ahora la alineación es diferente.

Quiero decir que si son isomorfos, sus matrices de adyacencia serán iguales o no. Si es así, lo que parece obvio debido a su propiedad de isomorfismo, entonces ¿por qué la pregunta pide resolver la adyacencia y el espectro para ambos gráficos?

(He visto vídeos de youtube y he leído páginas en internet pero sigo teniendo dudas de si estoy resolviendo esto correctamente).

Estos conceptos son nuevos para mí, así que quizá me esté perdiendo algo importante. Por favor, si alguien puede simplificar esto o señalar dónde estoy haciendo mal en este problema, sería muy apreciado.

Como referencia, aquí hay una imagen de los gráficos-> gráficos isomórficos

Matrices de adyacencia de los grafos. solución

Answer 1

Dejemos que $G_1=(V_1,E_1)$ y $G_2=(V_2, E_2)$ sean dos grafos isomorfos.

Si $V_1= \{ v_1,.., v_n\}$ y $V_2=\{w_1,..,w_n\}$ y $f: V_1 \to V_2$ es el isomorfismo, se puede definir una permutación $\sigma$ a través de $$f(v_i)=w_{\sigma(i)}$$

Ahora bien, si $P:=P_\sigma$ es la matriz de permutación correspondiente, entonces se tiene $$A_1=PA_2 P^{-1}$$ de donde se puede deducir que $A_1,A_2$ tienen el mismo espectro.

Answer 2

Para escribir la matriz de adyacencia de un grafo, fijas una numeración de los vértices. Lo has hecho de dos formas distintas para el grafo correcto y, he aquí, que has obtenido dos matrices distintas.

Si te dan los dos gráficos de la primera figura sin los colores, puedes pasar uno o dos minutos antes de averiguar la numeración de los vértices que te dará matrices de adyacencia idénticas. En ese par de minutos, estás resolviendo el problema de isomorfismo de esos dos grafos.

Supongamos que has numerado los dos grafos de forma que las dos matrices de adyacencia no son iguales. Como sabemos que los dos grafos son isomorfos, sabemos que existe una matriz de permutación, llamémosla $P$ que nos dará una matriz de adyacencia de la otra. Esto se muestra en la respuesta de N.S.: se pre-multiplica para permutar las filas y se post-multiplica para permutar las columnas.

Si conoces la numeración correcta de los vértices, conoces la matriz de permutación para otra numeración, y viceversa.

El álgebra lineal define las matrices similares como aquellas que pueden obtenerse entre sí mediante este proceso de pre y postmultiplicación por una matriz y su inversa. Así, las dos matrices de adyacencia pueden no ser iguales (muy probablemente, a no ser que nos pongamos a trabajar o alguien lo haga por nosotros coloreando los nodos) pero al menos son similar .

Ahora, una propiedad clave de las matrices similares es que tienen el mismo espectro. Así, si dos matrices de adyacencia tienen espectros diferentes, los gráficos correspondientes no son isomorfos. Por supuesto, si el número de unos en las dos matrices es diferente, los dos gráficos tampoco son isomorfos, pero el método espectral proporciona un filtro adicional.