@dalbio

Как найти в графе все циклы определённой длины?

Моя задача найти в графе все циклы длины 3.Как мне лучше это сделать?
  • Вопрос задан
  • 496 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
В общем случае, чтобы найти все циклы длины n надо подсчитать Tr(A^n)/n. A - матрица смежности. Tr() - это след (сумма элементов на диаганали). Т.е. возводите матрицу смежности из 0 и 1 в степень n и суммируете элементы по диагонали. Делить на n надо, потому что тут циклы считаются ориентированными и упорядочеными. Т.е. A->B->C посдчитается отдельно от B->C->A. Если граф неориентированный, то надо будет дополнительно поделить на 2 в конце.

Важно, тут будут считаться циклы, ходящие по одним и тем же вершинам и ребрам. Но для n=3 это не важно, если только у вас петель в графе нет.

Для n=3 можно чуть быстрее - возвести матрицу в квадрат и получить матрицу количеств путей длины 2. Потом можно пройтись по всем ребрам и просуммировать все циклы с этим ребром (известное уже количество путей длины 2 между двумя концами ребра). Тут как бы последнее, третье умножение пропускается и вместо него считаются только элементы на диагонали. Потом надо будет поделить на 3, потому что тут вы считаете каждый цикл 3 раза.

Можно воспользоваться быстрым умножением матриц Штрессена или присобачить какое-нибудь битовое сжатие, как я уже советовал вам в этом вопросе.

В зависимости от размерности матрицы (количества вершин) битовое сжатие может быть быстрее Штрассена или какого-либо другого быстрого алгоиртма умножения матриц.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
iChar Санкт-Петербург
от 120 000 до 180 000 ₽
Яндекс Москва
от 100 000 до 300 000 ₽
23 янв. 2021, в 21:30
20000 руб./за проект
23 янв. 2021, в 20:57
750 руб./в час