4 цикла в неориентированном графе
У меня есть неориентированный граф, который представлен в виде матрицы соседства. Мне нужно найти количество 4 циклов: циклы, которые содержат 4 ребра. Если у вас есть идеи по поводу алгоритма, пожалуйста, помогите мне.
Решение
Простой (не оптимальный) подход псевдокода:
output = []
skip_nodes = []
for node in input_graph:
if node in skip_nodes:
continue
for path in deep_search(start=node, max_depth=4):
if len(path) == 4 and path[1] == path[4]:
output.append(path)
skip_nodes.append(path[2], path[3], path[4])
return output
Другие решения
Умножьте матрицу на 4 раза, насколько я помню, диагональные элементы, отличные от 0, будут участвовать в циклах с 4 ребрами (здесь могут быть неправильные критерии, но вы можете копать дальше)
detector