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].