¿Qué es un "triángulo" en un grafo y cuál es la fórmula para calcular el número de triángulos de un grafo utilizando los valores propios de la matriz de adyacencia?
Cualquier ayuda será muy apreciada,
Respuesta
¿Demasiados anuncios?
user3658307
Puntos
33
Para un gráfico $G=(V,E)$ , a triángulo es un camino de longitud 3, es decir, un ciclo con 3 nodos (si dibujamos el grafo, gráficamente forma un triángulo). Sea $A$ sea la matriz de adyacencia, donde $[A]_{ij} = a_{ij} = \mathbb{I}[e_{ij}\in E] $ . Supongamos que no hay bordes propios.
En primer lugar, tenga en cuenta que $A^k=\prod_{i=1}^k A$ cuenta el número de longitudes $n$ caminos entre cada par de nodos. Es decir $ a_{ij}^k = \#_k(i\rightarrow j)$ es el número de caminos para llegar desde el vértice $i$ a $j$ en $k$ pasos. ¿Por qué? Pues por inducción, $A$ lo cumple, ya que las aristas son la única longitud $1$ caminos. Suponiendo que la propiedad sea cierta para algún $k$ Obsérvese que la multiplicación de $A^k$ por $A$ tiene componentes: $$ [A^k]_{ij} = a^k_{ij} = \sum_{v\in V} \#_k(i\rightarrow v) \#_1(v\rightarrow j) $$ Tenga en cuenta que una vez que llegue a $v$ de $i$ todos los caminos posibles desde $v$ a $j$ forman las rutas completas desde $i$ y $j$ a través de $v$ . Así que multiplicamos los recuentos. Todos estos recorridos tienen una longitud $k+1$ porque $i$ a $v$ requiere un paso y la suma de todos los $v$ cubre toda la longitud $k+1$ (y sólo la longitud $k+1$ caminos). Esto nos da todos los caminos de $i$ a $j$ a través de cada $v$ que significa $ a_{ij}^k = \#_{k+1}(v\rightarrow j) $ . Otra forma de verlo es considerando normalizarlo y tratarlo como la matriz de transición de la cadena de Markov. Véase aquí también.
Teniendo esto en cuenta, considere que $a^3_{ii}$ cuenta el número de rutas de longitud 3 desde $i$ a $i$ Cada uno de ellos es un triángulo. Así que podemos obtener un recuento de todos los triángulos a través de: $$ C_a(G) = \sum_i a^k_{ii} = \text{tr}(A^3) $$ Pero esto cuenta demasiado los triángulos, porque cada triángulo aparecerá $6$ veces ( $v_i\rightarrow v_j \rightarrow v_\ell$ pueden reordenarse/permutarse en $3\cdot 2\cdot 1=6$ formas). Así que deberíamos utilizar $$ C(G) = \frac{1}{6}\text{tr}(A^3) $$
Por último, recuerde que la traza de una matriz es igual a la suma de sus valores propios . Así que $\lambda_\alpha$ sea el $\alpha$ eigenvalor de $A$ . A continuación, recordemos que $A$ que sea simétrica significa que tiene una composición propia y que los valores propios de $A^k$ son los $k$ potencias de los valores propios de $A$ ( aquí y aquí ). Así que $\lambda_i^3$ es el $i$ eigenvalor de $A^3$ .
Así, podemos escribir la solución en términos de los valores propios de la matriz de adyacencia mediante $$ C(G) = \frac{1}{6}\sum_i \lambda_i^3 $$ donde utilizamos el hecho de que $\text{tr}(A^3) = \sum_i \lambda^3_i$ .
Ver también esta entrada como señala el comentarista anterior.
