Экземпляр: неориентированный графс двумя выделенными вершинами и целым числом .
Вопрос: существует ли путь в , такой, что путь пересекает не болеетреугольники? (Для этой задачи говорят, что путь пересекает треугольник, если путь содержит хотя бы одно ребро из треугольника.)
cc.complexity-theory
graph-algorithms
Андрас Фараго
источник
источник
Ответы:
Предположим, что вG ,
Для каждого ребра между узламиvi а также vj в G , позволять E[i,j]=1 , а также E[i,j]=0 если нет края. вычислениеn×n матрица C[i,j]=∑nk=1E[i,k]⋅E[k,j] , который дает количество двухшаговых путей между каждой парой узлов vi а также vj , Тогда для края междуvi а также vj в G вычисление D[i,j]=E[i,j]⋅C[i,j] иначе установлено D[i,j]=∞ , который дает количество треугольников, частью которых является ребро (или бесконечность, если ребра нет). Матричное умножение, необходимое для вычисленияC расходы O(n3) (может быть вычислено быстрее в зависимости от разреженности G ).
Теперь вычислимn×n матрица A такой, что A[i,j]=min(D[i,j],mink(D[i,k]+D[k,j]−E[i,j])) , A все кратчайшие пути в D длиной до двух дополнен, чтобы учесть пути, которые идут по двум краям некоторого треугольника.
Теперь просто вычислите кратчайший путь междуvi а также vj в G на новом графике которого A является (взвешенной) матрицей смежности с использованием Дейкстры (поскольку все ребра-веса положительны), т.е. A∗[i,j]≤k , где A∗ это замыкание над тропическим полукольцом (которое дает матрицу расстояний).
источник