¿Hay alguna forma de representar la matriz de grados con la matriz de adyacencia?

Si.

Deje que [math] G = (V, E) [/ math] sea un gráfico simple no dirigido sobre vértices [math] n [/ math] y bordes [math] m [/ math]. Defina [math] x \ in \ mathbb {R} ^ n [/ math] como un mapeo desde el conjunto de vértices a los reales, es decir, [math] x: V \ rightarrow \ mathbb {R} [/ math]. Ahora consideremos el operador lineal [math] \ displaystyle [/ math] [math] A: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} ^ n [/ math] sobre el campo binario [math] {0 , 1} [/ matemáticas]. Cuando aplicamos [matemáticas] A [/ matemáticas] a [matemáticas] x [/ matemáticas], el valor resultante en un vértice [matemáticas] a [/ matemáticas] es la suma de los valores de la función [matemáticas] x [/ matemática] sobre todos los vecinos, [matemática] b [/ matemática], de [matemática] a [/ matemática]. Por lo tanto, la acción del operador [matemática] A [/ matemática] en [matemática] x [/ matemática] en [matemática] a [/ matemática] puede capturarse como

[matemática] \ displaystyle (Ax) (a) = \ sum_ {b: ab \ en E (G)} x (b). [/ matemática]

Nos referimos a [matemáticas] A [/ matemáticas] como la matriz de adyacencia de [matemáticas] G [/ matemáticas]. Generalmente se define como:

[matemáticas] A_ {ij} = [/ matemáticas]

[matemáticas] 1, [/ matemáticas] si [matemáticas] ij \ en E (G) [/ matemáticas]

[matemáticas] 0, [/ matemáticas] de lo contrario.

Ahora, uno puede escribir la matriz de grados como:

[matemáticas] D_ {ii} = diag (d_i) [/ matemáticas]

dónde

[matemáticas] \ displaystyle d_i = – \ sum_ {j = 1, j \ neq i} A_ {ij}. [/ matemáticas]

Esto significa que cada entrada diagonal de [math] D [/ math] es igual a una suma de filas de la fila equivalente de la matriz de adyacencia correspondiente.

Una forma sería [math] D = \ textrm {diag} (Aj) [/ math], donde [math] j [/ math] es el vector de todos y [math] \ textrm {diag} (v) [ / math] es la matriz diagonal cuya [math] i ^ {th} [/ math] entrada diagonal es la entrada [math] i ^ {th} [/ math] del vector [math] v [/ math].

No puede escribir [matemáticas] D [/ matemáticas] en la forma [matemáticas] XAY [/ matemáticas] en general. Para ver por qué, suponga que [math] A [/ math] es la matriz de adyacencia del ciclo en cuatro vértices [math] C_4 [/ math]. Este es un gráfico regular de grado dos, entonces [matemáticas] D = 2 I [/ matemáticas] y tenemos

[matemáticas] XAY = 2I. [/ matemáticas]

Pero la matriz de adyacencia de [math] C_4 [/ math] es [math] \ begin {pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \ end {pmatrix} [/ math] que tiene rango dos. Por lo tanto, [math] XAY [/ math], que tiene rango como máximo dos, es igual a [math] 2I [/ math], que tiene rango cuatro, una contradicción manifiesta.