Si dos gráficos son isomórficos, ¿serán iguales sus determinantes?
Gráficos de 10 vértices G1 y G2
Estoy resolviendo los ejercicios del capítulo 2 de la teoría de grafos con algoritmos y sus aplicaciones. Hasta ahora, para el isomorfismo, simplemente escribo todos los bordes y trato de encontrar los patrones, lo que para gráficos pequeños es suficiente. Para estos 2 gráficos de 10 vértices y 30 bordes, creo que necesito algo más escalable. Intenté 'traducir' ambos gráficos a una estructura unificada, pero, por supuesto, si un vértice cambia de nombre, el gráfico también se verá diferente. Escribí la matriz de adyacencia tratando de encontrar un patrón, y hay una columna que me hace sospechar que estos dos pueden no ser isomórficos. Sin embargo, siempre puedo cambiar el nombre de un vértice para que las columnas se vean un poco más similares. De todos modos, encontré que dos gráficos (A, B) son isomorfos si A = PBP (t) donde P es una matriz de permutación y P (t) es su transpuesta.
Dado que det (P) = 1 o -1 = det (P (t)) y det (AB) = det (A) * det (B), entonces si A y B son isomorfos:
det (A) = 1 | -1 * det (B) * 1 | -1 det (A) = det (B)
¿Podrían dos matrices de adyacencia tener el mismo determinante y no ser isomórficas? ¿O es la igualdad en el determinante una condición suficiente (y mucho más escalable) para el isomorfismo?
Mejor,
Sergio
Respuestas
De hecho, es cierto que la matriz de adyacencia de los gráficos isomorfos tendrá el mismo determinante. De hecho, si$A = PBP^T$ para una matriz de permutación $P$, luego $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ De hecho, podemos decir más: porque $A$ y $B$son matrices similares, tendrán los mismos valores propios. Tenga en cuenta que si dos matrices tienen los mismos valores propios, automáticamente tienen el mismo determinante.
Lo contrario no se cumple: si $A,B$ son las matrices de adyacencia de dos gráficos y tenemos $\det(A) = \det(B)$, no significa necesariamente que los gráficos sean isomórficos. De hecho, incluso si$A$ y $B$tienen los mismos valores propios, no significa necesariamente que las gráficas sean isomorfas. Los ejemplos de este fenómeno se denominan pares de gráficos isospectrales (o cospectrales) .
No, la ruta de longitud 2 (2 aristas, 3 vértices) tiene det 0, y el gráfico con 3 vértices y sin aristas también tiene det 0.