Минимальная проблема с переворотом

Я сформулировал следующую проблему сегодня, играя с моим GPS. Вот :

Пусть - ориентированный граф такой, что если то , т. является ориентацией основного неориентированного графа. Рассмотрим следующие операции:e = ( u , v ) ∈ E ( v , u ) ∉ E $G(V,E)$$e=(u,v) \in E$$(v,u) \notin E$$G$

• $Flip(u,v)$ : заменить ребро ребром( V , U $(u,v)$$(v,u)$
• $undirect(u,v)$ : сделать ребро ненаправленным$(u,v)$

Пусть две специальные вершины. Рассмотрим следующие проблемы оптимизации:$s,t \in V$

• Min-Flip st-связность: Учитывая и две вершины найти минимальное количество ребер, которые нужно перевернуть, чтобы сделать направленный путь от до .$G$$s,t$$s$$t$
• Мин-флип сильной связности: учитывая найти минимальное количество ребер, которые нужно перевернуть, чтобы сделать сильной связности. Если невозможно сделать сильно связанным, переворачивая ребра, выведите NO.$G$$G$$G$
• Минимальная непрямая сильная связность. Учитывая найдите минимальное количество ребер, которые должны быть ненаправленными, чтобы сделать сильной связью.$G$$G$

Обратите внимание, что вы не можете добавлять «новые» ребра. Вы только модифицируете существующие ребра, используя вышеуказанные операции. Известна ли эта проблема в литературе? Если да, каковы известные результаты?

Реферат: Проблемы могут быть решены за полиномиальное время путем нахождения сильно связанной ориентации с минимальными затратами.

Более подробно: Теорема Роббинса говорит, что ребра неориентированного графа могут быть ориентированы так, чтобы результирующий ориентированный граф был сильно связным тогда и только тогда, когда неориентированный граф связан с 2 ребрами. Существует несколько расширений, и одно из них говорит, что с помощью алгоритма субмодулярного потока за полиномиальное время мы можем решить следующую проблему за полиномиальное время: учитывая неориентированный граф с затратами на ребро (для обоих направлений), найдите ориентацию с минимальными затратами, которая делает граф сильно связан. Например, см. Статью Фрэнка . Более свежий алгоритм предоставлен Иватой и Кобаяси .

Этот результат должен быть полезен для решения поставленных задач. Первая проблема может быть решена методом, предложенным Томеком . Поэтому мы сосредоточимся на других проблемах.

Для второй задачи мы используем ту же конструкцию гранично-взвешенного графа, что и Томек, и находим сильно связную ориентацию с минимальными затратами за полиномиальное время.

Для третьей задачи, чтобы разрешить оба направления для каждого ребра, мы дублируем каждое ребро, а затем применяем ту же конструкцию и тот же алгоритм. Это действительное сокращение, поскольку использование одного и того же направления для дублированных ребер не влияет на сильную связность.

Это ответ для первой задачи:
рассмотрим новый взвешенный граф , где E ′ = { ( u , v , 0 ) | ( u , v ) ∈ E } ∪ { ( v , u , 1 ) | ( u , v ) ∈ E } (веса всех ребер из $G'=(V,E')$$E'=\{(u,v,0)|(u,v) \in E\} \cup \{(v,u,1)|(u,v)\in E \}$$G$равны 0, а веса «перевернутых» ребер равны 1). Теперь вам просто нужно найти кратчайший путь от до t .$s$$t$

$k$$k=0$$s$$t$$k$

В моей недавней книге «Связи в комбинаторной оптимизации» (Oxford University Press, 2011) центральная тема - проблемы ориентации графа, включая рассмотренные выше варианты. Известно, что 2k-ребро-связанный граф имеет k-ребро-связную ориентацию (это теорема Нэша-Вильямса). Если граф не связан с 2k-ребрами, может быть интересно решить, является ли данное подмножество F ребер хорошим (в том смысле, что F имеет ориентацию, так что результирующий смешанный граф связан с k-ребрами). В книге я описал, как эта проблема может быть решена за полиномиальное время. Но я не знаю, как найти хороший набор минимальной мощности.

Андрас Франк

Min-Flip st-связность Base: вычислить все вершины, которые достижимы из s (T). если t находится в T, остановитесь. Индуктивный: рассмотрите все вершины, не принадлежащие T, которые смежны с T, одним щелчком и назовите это U. Вычислите вершины, достижимые из U, назовите это V. Если t - V, остановите, иначе добавьте V к T и продолжайте.

Мин-флип сильной связности Вы должны иметь в виду, непрямой, потому что у вас будут проблемы с: A -> B