Задача о цикле с нулевым весом

В информатике и теории графов проблема цикла с нулевым весом — это проблема определения, имеет ли ориентированный граф с весами на ребрах (которые могут быть положительными, отрицательными или нулевыми) цикл , в котором сумма весов равна 0.

Связанная с этим задача — решить, есть ли в графе отрицательный цикл, цикл, в котором сумма весов меньше 0. Эта связанная задача может быть решена за полиномиальное время с помощью алгоритма Беллмана–Форда . Если отрицательного цикла нет, то расстояния, найденные алгоритмом Беллмана–Форда, можно использовать, как в алгоритме Джонсона , для перевзвешивания ребер графа таким образом, чтобы все веса ребер стали неотрицательными, а все длины циклов остались неизменными. С этим перевзвешиванием цикл с нулевым весом становится тривиальным для обнаружения: он существует тогда и только тогда, когда ребра с нулевым весом не образуют направленный ациклический граф . Следовательно, особый случай проблемы цикла с нулевым весом на графах без отрицательного цикла имеет алгоритм с полиномиальным временем . ^[1]

Напротив, для графов, содержащих отрицательные циклы, обнаружение простого цикла с весом точно 0 является NP-полной задачей. ^[1] Это верно даже тогда, когда веса являются целыми числами полиномиальной величины. В частности, существует сокращение от задачи о гамильтоновом пути на -вершинном невзвешенном графе с указанными начальными и конечными вершинами и до задачи о цикле с нулевым весом на взвешенном графе, полученной путем присвоения всем ребрам веса, равного единице, и добавления дополнительного ребра из в с весом . ^[2]${\displaystyle n}$${\displaystyle G}$${\displaystyle с}$${\displaystyle т}$${\displaystyle G}$${\displaystyle т}$${\displaystyle с}$${\displaystyle 1-н}$