Линейный алгоритм, чтобы найти количество различных замкнутых кривых в ориентированном графе?
Существует ли какой-либо алгоритм с линейным временем для определения количества различных замкнутых путей в ориентированном графе?
Псевдокод объяснение будет достаточно.
1 ответ
В последующем "цикл" всегда означает "простой цикл" - то есть последовательность вершин, в которой каждая смежная пара вершин связана ребром в исходном графе G, первая и последняя вершины равны, а все остальные вершина в последовательности появляется не более одного раза.
Немного посмотрев, я нашел доказательство того, что эта проблема NP-сложна - поэтому не только никто не знает, как решить ее за линейное время, никто не знает, как решить ее за полиномиальное время.
Доказательство, которое я нашел, находится на с. 2 из http://www.cs.umd.edu/~jkatz/complexity/f11/lecture23.pdf, который был связан с этим ответом на Quora.
Я перефразирую и немного расшифрую его (я не понимаю, почему они написали "n^n" как "2^(n log n)") здесь:
Предположим, у нас есть орграф G, и мы хотим знать, содержит ли G гамильтонов цикл. Мы могли бы решить эту трудную задачу с известным NP в полиномиальное время, если бы у нас было полиномиальное время для вашей задачи (считая количество простых циклов в ориентированном графе) следующим образом:
Создайте новый граф G'из G, взяв каждое ребро (u, v) в G и заменив его "гаджетом", который создает n ^ n различных путей от u до v. Это можно сделать следующим образом: для каждого ребра (u, v) в G, создайте n-на-n сетку из n^2 свежих вершин в G', соединяя u с каждой из n вершин в первой строке, каждая из этих n вершин с каждой из n вершин в следующий ряд (для n^2 всего ребер от первого ряда к второму ряду), от каждой вершины во втором ряду до каждой из вершин в третьем ряду и так далее до n-го и последнего ряда. Соедините каждую вершину в последней строке с v. Мы можем получить от u до v ровно n ^ n различными способами через эти вершины: в каждой из n строк мы можем выбрать любую из n вершин в этой строке, чтобы быть на путь от u до v. Очевидно, что этот гаджет имеет полиномиальный размер (n^2 вершин и (n-1)n^2 + 2n ребер), и нам потребуется не более n^2 его копий (по одной на каждое ребро в G) так что G'тоже. Мы передадим этот построенный граф G'любому алгоритму подсчета направленных циклов в орграфе и воспользуемся ответом, чтобы определить, имеет ли G гамильтонов цикл.
Сначала предположим, что G имеет гамильтонов цикл. Тогда этот цикл, будучи гамильтонианом, имеет n ребер, поэтому в G'он соответствует (n^n)^n различным циклам, поэтому в G' есть по крайней мере столько циклов. (Вероятно, будет больше, соответствующих другим циклам, присутствующим в G, но это не имеет значения.)
ОТО, предположим, у G нет гамильтонова цикла. Тогда самый длинный цикл, который он может иметь, имеет длину n-1, а максимальное число циклов, которое он может иметь, ограничено сверху n^(n-1). Чтобы увидеть это, обратите внимание, что любой цикл длиной не более n-1 можно записать в виде последовательности из n-1 чисел, каждое из которых находится в диапазоне от 1 до n, путем нахождения вершины с наименьшим номером в цикле, ее записи и затем записывать каждую последующую вершину в цикле до тех пор, пока исходная вершина не будет достигнута снова, после чего мы могли бы (скажем) продолжать записывать номер исходной вершины, пока мы не записали n-1 чисел в общей сложности. Каждый цикл дает отдельный вектор из n-1 чисел, и таких векторов может быть не более n ^ (n-1), поэтому в G. может быть не более n ^ (n-1) различных циклов. число и длина циклов в G, теперь мы можем вычислить верхнюю границу количества циклов в G: поскольку один цикл в G может иметь не более n-1 ребер, он может дать не более (n^n)^(n-1) циклов в G'; и поскольку в G может быть не более n ^ (n-1) различных циклов, в G может быть не более n^(n-1)*(n^n)^(n-1) циклов в целом. Но это упрощается до n^(n^2-n)*n^(n-1) и оттуда до n^(n^2-1), что явно строго меньше, чем n^(n^2).
Таким образом, мы можем сказать, имеет ли G цикл гамильтониана, подавая G'в алгоритм подсчета циклов в орграфе и глядя на ответ: если оно по крайней мере n ^ (n^2), то G имеет гамильтонов цикл, а если ниже n ^ (n^2), тогда G не имеет гамильтонова цикла. Таким образом, если бы существовал алгоритм полиномиального времени для подсчета циклов в орграфе, мы могли бы также решить гамильтонов цикл (и все другие NP-полные задачи) за полиномиальное время.