Demostración de la isomorfía de dos grafos mediante sus matrices de adyacencia

Question

No sé cómo resolver el siguiente problema:

Demuestre que dos gráficos simples $G$ y $H$ son isomorfas si y sólo si existe una matriz de permutación $P$ tal que $A_G=PA_HP^t$ .

Aquí $A$ es la matriz de adyacencia. Tengo la sensación de que esto no debería ser muy difícil, pero mi álgebra lineal no es muy buena, ¿me estoy perdiendo algo obvio?

Answer 1

He aquí un ejemplo que puede hacerte pensar en la dirección correcta. Considere $PAP^t$ , donde $P$ es la matriz de permutación

$$\begin{bmatrix} 0&0&0&1\\ 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0 \end{bmatrix}$$

y, como ejemplo ilustrativo,

$$A=\begin{bmatrix} 1&2&3&4\\ 2&3&4&5\\ 0&1&2&3\\ 3&2&1&0 \end{bmatrix}\;.$$

Tenemos

$$PA=\begin{bmatrix} 0&0&0&1\\ 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0 \end{bmatrix} \begin{bmatrix} 1&2&3&4\\ 2&3&4&5\\ 0&1&2&3\\ 3&2&1&0 \end{bmatrix}= \begin{bmatrix} 3&2&1&0\\ 1&2&3&4\\ 0&1&2&3\\ 2&3&4&5 \end{bmatrix}\;, $$

y luego

$$ PAP^t=\begin{bmatrix} 3&2&1&0\\ 1&2&3&4\\ 0&1&2&3\\ 2&3&4&5 \end{bmatrix} \begin{bmatrix} 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\\ 1&0&0&0 \end{bmatrix}= \begin{bmatrix} 0&3&1&2\\ 4&1&3&2\\ 3&0&2&1\\ 5&2&4&3 \end{bmatrix}\;. $$

La primera fila de $A$ es la segunda fila de $PAP^t$ y la primera columna de $A$ es la segunda columna de $PAP^t$ . La segunda fila y la segunda columna de $A$ son la cuarta fila y columna de $PAP^t$ . La cuarta fila y columna de $A$ son la primera fila y la primera columna de $PAP^t$ . Y la tercera fila y columna de $A$ siguen siendo la tercera fila y columna de $PAP^t$ . En otras palabras, tanto las filas como las columnas han sido permutadas por la permutación $(1,2,4)$ en notación de ciclo o

$$\pmatrix{1&2&3&4\\2&4&3&1}\tag{1}$$

en notación de dos líneas. Si $A$ es la matriz de adyacencia de un grafo, $PAP^t$ es simplemente la matriz de adyacencia del mismo grafo después de que los vértices se hayan renumerado según la permutación $(1)$ .