¿Cómo encontraría una cantidad de triángulos en un gráfico no dirigido dado?

Consideremos un gráfico que consiste en vértices [matemáticos] N [/ matemáticos] y bordes [matemáticos] M [/ matemáticos]. Definamos el vértice como pesado si tiene más de [math] \ sqrt {M} [/ math] vecinos y light de lo contrario. De acuerdo con la definición, se puede demostrar que no hay más de [math] \ sqrt {M} [/ math] vértices pesados. Considere cuatro casos de triángulos en un gráfico no dirigido:
1. Pesado-pesado-pesado
2. Pesado-pesado-ligero
3. Pesado-ligero-ligero
4. Luz-luz-luz
También necesitamos un conjunto de hash para verificar de manera eficiente si se presenta algún borde en nuestro gráfico.
Para contar el número de triángulos de tipo (1) podemos iterar a través de triples de vértices pesados ​​y verificar si están conectados por pares. Como hay [math] O (\ sqrt {M}) [/ math] de ellos, el tiempo total sería: [math] O (M ^ {1.5}) [/ math].
En los casos (2) – (3) tienes al menos un vértice pesado para que puedas iterar sobre él. Deja que sea q para notación. También debe tener un ciclo interno que recorra todos los bordes (u, v) y compruebe si se ajusta al tipo (2) o (3) (por ejemplo, un par de vértices son pesados ​​y ligeros o ligeros y ligeros) y eso (u , v, q) es un triángulo. Esto también requeriría tiempo [matemático] O (M ^ {1.5}) [/ matemático].
Finalmente, en el caso (4) necesita iterar a través de todos los bordes (u, v) de modo que u y v sean vértices claros y solo intersequen sus listas de adyacencia en tiempo lineal. Como son vértices de luz, el tiempo total aquí sería [matemática] O (M ^ {1.5}) [/ matemática].

Entonces, este algoritmo itera a través de cada triángulo en un gráfico y tiene una complejidad [matemática] O (M ^ {1.5}) [/ matemática].

Tome la matriz de adyacencia, donde una entrada i, j es 1/0 si el borde de i a j existe / no existe y multiplíquelo consigo mismo. Luego tome el producto interno de Frobenius de esa matriz y el original, que es un nombre elegante para la suma de sus productos basados ​​en elementos. Esta idea es similar a cómo funciona el algoritmo Floyd-Warshall, donde las rutas se pueden combinar al ver el gráfico como una matriz de adyacencia.

El tiempo de ejecución de esto será mejor que el algoritmo ingenuo [matemático] O (n ^ 3) [/ matemático] si utiliza un algoritmo de multiplicación de matriz rápida.