Итак, мы хотим найти все возможные циклы на графике.Предположим, что каждая вершина соединена, так как это сгенерирует все возможные ребра.Теперь давайте начнем с простого случая и продолжим наш путь.
Давайте начнем с цикла длины 3. Это наименьший простой цикл, который мы можем иметь в нашем графике.Любые три вершины в нашем графе могут составить такой цикл.Порядок не имеет значения для этого случая, потому что каждая вершина в нашем наборе из трех будет соединяться с двумя другими.Таким образом, число простых циклов длины три будет количеством способов, которыми мы можем выбрать три вершины из набора V вершин, игнорируя порядок.Это «n выбрать k» или nck(3, V), где nck равно:
function nck(k, n):
return factorial(n) / (factorial(k) * factorial(n - k))
Это решает количество циклов длины 3 для нас.Мы можем повторить аналогичную логику для длины 4, но возникает новая проблема.Для группы из четырех вершин a, b, c, d существует несколько способов соединить их в цикле.Мы могли бы подключить b к a и d, a и c или c и d.Короче говоря, нам нужно найти число перестановок этих вершин k! и применить две поправки.Во-первых, мы разделим на два, чтобы учесть перестановки, которые «переворачивают» порядок другой перестановки (которая все еще соединяла бы те же самые смежные вершины).Во-вторых, мы разделим на k, чтобы учесть перестановки, которые просто вращают другую перестановку (что опять-таки не меняет, какие вершины смежны друг с другом).Таким образом, число различных порядков цикла из k вершин равно:
function orderings(k):
return factorial(k - 1) / 2
Теперь мы можем вычислить количество циклов с длиной 4 на nck(4, V) * orderings(4).Теперь этот процесс можно распространить на все циклы длины, вплоть до V.
. Чтобы получить общее количество циклов, нам нужно сложить все количество циклов длин [3, V]включительно.Обратите внимание, что мы можем немного упростить, отменив термины из наших двух функций.Если мы напишем factorial(k - 1) как factorial(k) / k и вставим две функции в строку, factorial(k) отменит.Тогда нам просто нужно разделить на 2 * k * factorial(n - k).Вы также можете упростить factorial(n) / factorial(n - k) как просто произведение всех целых чисел в [k + 1, n] включительно, чтобы избежать деления на большой факториал.
В целом, это не должно быть слишком дорого для вычисления.Вычисляя factorial(n) / factorial(n - k) в порядке возрастания, мы можем даже избежать пересчета частичных произведений или любых факториалов.Это означает, что мы можем посчитать общее количество циклов за линейное время.В python:
def cycles(v):
count = 0
product = v * (v - 1) * (v - 2) // 2
for k in range(3, v + 1):
count += product // k
product *= (v - k)
return count
Обратите внимание, что я попытался найти решение в закрытой форме, но безуспешно.Если бы нам не нужно было умножать на порядки каждого цикла, мы могли бы вычислить мощность набора мощностей этих вершин (минус число подмножеств размера 0..2).Я также пытался понять, может ли [wolfram alpha] (https://www.wolframalpha.com/input/?i=sum+from+k%3D3+to+v+of+(v%5E2+%2F+2)+%2F+((v-k)%5E2+*+k) упростить его, но это дало мне кое-что еще более сложное.