Подсчет треугольников на графике

Question

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

Answer 1

Простой подход состоит в том, чтобы посетить каждый узел и попробовать каждый путь от него, который имеет длину 3. Если он заканчивается на стартовом узле, он будет треугольником.

Это не оптимально, учитывая потребление времени, но это просто.