Подсчет треугольников на графике
Мой профессор сказал, что я должен найти способ найти количество треугольников на графике. У меня проблема с тем, какой график использовать, но мой профессор предложил сначала найти способ подсчета треугольников на графике. Я искал его в Google и обнаружил, что существует алгоритм подсчета треугольников на графике, но я не очень разбираюсь в этом, потому что я не студент ComSci (Computer Science). И я также обнаружил, что могу посчитать количество треугольников по матрице. (1/6)(А)^3. Это след А. Так что... сейчас я спрашиваю еще одну идею найти количество треугольников в графе. Спасибо, если я получил ответ!
1 ответ
Простой подход состоит в том, чтобы посетить каждый узел и попробовать каждый путь из него, имеющий длину 3. Если он заканчивается в начальном узле, это будет треугольник.
Это не оптимально с точки зрения затрат времени, но это просто.