¿A qué equivale la fórmula de una matriz de adyacencia de un grafo no dirigido traspuesto?

Question

Dejemos que $A\in\mathbb{R}^{n\times n}$ sea la matriz de adyacencia de un grafo no dirigido con n nodos y sea 1 $\in R^n$ sea un vector columna cuyos elementos son todos 1. ¿Qué hace la fórmula $1^T \cdot A \cdot 1$ ¿Igual?

Dos veces el número de aristas de un gráfico o ¿El cuadrado del número de nodos de un gráfico?

¿y por qué?

gracias de antemano

Answer 1

$1^T \cdot A \cdot 1$ es la suma de todas las entradas de la matriz $A$ . Estas entradas son, en posición $ij$ 1 si hay una arista desde el vértice $i$ al vértice $j$ y 0 en caso contrario. (O, en un multigrafo, el número de aristas del vértice $i$ al vértice $j$ .) Como el grafo es no dirigido, cada arista aparece dos veces: una en la posición $ij$ y una vez en posición $ji$ (excepto los bucles, que sólo aparecen en la posición $ii$ .)

Por lo tanto, sumando todo esto se obtiene el doble de aristas en el gráfico, al menos si no hay bucles.

(Con los bucles, sigue siendo cierto, si se adopta una convención adecuada, por ejemplo, poner un 1 en la entrada $ii$ y contar los bucles como media arista, o bien poner un 2 en la entrada $ii$ (porque el bucle es incidente en el vértice $i$ dos veces))