Учитывая сильно связанный орграф G со взвешенными ребрами, я хотел бы идентифицировать ребра, которые доказуемо не являются частью какого-либо минимального сильно связного подграфа (MSCS) группы G.
Одним из способов нахождения таких ребер является модифицированный алгоритм Флойда-Варшалла. Используя алгоритм Флойда-Варшалла, можно определить, какие ребра никогда не являются наилучшим вариантом для перехода от вершины i к j. Эти узлы не могут быть частью MSCS, потому что лучше заменить их двумя или более другими ребрами.
Техника обрезки Флойд-Варшалла работает довольно хорошо, когда граничные веса значительно различаются, но очень плохо, когда граничные веса одинаковы, но велики по величине.
Знаете ли вы какие-либо эффективные методы обрезки для больших, схожих краев? Эта проблема эквивалентна более распространенной проблеме, которую я не узнаю? Этот вид обрезки изучался ранее в литературе?
Ответы:
Мы предполагаем, что веса ребер являются положительными целыми числами. Учитывая , ориентированный граф G с весами ребер, вызовите ребро е излишний , если адрес не принадлежит к какому - либо минимальному весу сильно связному остовному подграфы G .
Мы утверждаем, что, если P = NP, не существует алгоритма полиномиального времени, который всегда находит избыточное ребро в данном ориентированном графе с весами ребер, пока он есть. Точнее:
Теорема . Для ориентированного графа G с весами ребер сложно найти избыточное ребро в G или объявить, что у G нет лишнего ребра.
Доказательство . Ключевое наблюдение заключается в том, что, если G имеет уникальный сильно связанный остовный подграф минимального веса, то вы можете вычислить этот подграф, удалив лишние ребра по одному. Таким образом, остается показать, что единственность не облегчает задачу о сильно связном остовном подграфе минимального веса, но это доказывается следующей леммой. КЕД .
Лемма . Для заданного ориентированного графа G с весами ребер трудно вычислить вес сильно связанного остовного подграфа минимального веса в G даже при условии, что G имеет единственный остовный сильно связный подграф минимального веса.
Доказательство . Как вы знаете , проблема без обещания является NP-трудной (даже для случая единичного веса) из-за сокращения от проблемы гамильтоновой схемы. Мы сводим проблему без обещания к проблеме с обещанием.
Пусть G - ориентированный граф с весами ребер. Добавьте ребра G с помощью й 0 , х 1 , ..., х м -1 , где т есть число ребер в G . Пусть w i будет заданным весом ребра e i . Пусть новый вес w ′ i = 2 m w i +2 i . Тогда легко проверить, что G с новыми весами имеет единственный сильно связный остовной подграф минимального веса. Также легко проверить, что минимальный весW сильно связного остовного подграфа в G с исходными весами можно вычислить из минимального веса W ′ в G с новыми весами как W = ⌊ W ′ / 2 m ⌋. КЕД .
источник