Cómo demostrar que el número de triángulos en G es $\frac{1}{6}Tr(A^3)$

Question

Supongamos que tenemos un gráfico $G$ . Cómo debo mostrar el que el número de triángulo de en $G$ es $$\frac{1}{6}Tr(A^3)$$ donde A es la matriz de adyacencia de $G$ ? No tengo ni idea de qué debo hacer primero. Gracias de antemano

Answer 1

Dejemos que $A$ sea la matriz de adyacencia. Entonces $A_{ij}=1$ si hay una arista que conecta $i\leftrightarrow j$ . Teniendo esto en cuenta, $i\rightarrow j \rightarrow k$ es un triángulo si $A_{ij}A_{jk}A_{ki}=1$ . Ahora suma sobre $ijk$ y obtener ${\rm tr}\left(A^{3}\right)$ . Pero espere, usted sobre cuenta esto por exactamente el número de permutaciones en $ijk$ que es $3!=6$ . Por lo tanto, el número de triángulos es

$$\text{Number of triangles}=\dfrac{1}{6}{\rm tr}\left(A^{3}\right)$$

Answer 2

El $i,j$ entrada de $A^3$ nos da el número de paseos de longitud tres $iklj$ . Si $i=j$ (y el grafo no tiene bucles), dicho paseo $ikli$ necesariamente tiene $k\ne i$ et $k\ne l$ es decir, es un ciclo de longitud $3$ . Como la traza es la suma de las entradas diagonales, cuenta esos ciclos, pero cada uno se cuenta seis veces, es decir, para cada vértice inicial y dirección de marcha.