Всем привет. Прошлый вопрос был решён настолько быстро и успешно, что я решил попробовать и следующий .

Допустим, у нас есть связный ориентированный граф с известной стартовой вершиной.
Берём некоторую вершину этого графа V. В неё есть не менее одного пути из стартовой вершины. (В графе возможны циклы, так что множество путей в V может быть бесконечным).
Задача: найти такие вершины графа, что на любом пути в V они встречаются ровно столько же раз, как и V.
Это похоже на поиск доминирующих вершин, но доминаторов может быть больше, чем интересующих нас вершин.

Вот пример:

Для вершины 1 таких вершин нет.
Для вершины 2 таких вершин нет (1 её доминирует, но возможен путь 1232, в котором 1 встречается однократно, а 2 — дважды)
Для вершины 3 такая вершина только одна — 2 (пути к 3 выглядят как 123, 12323, 1(23)*, так что в любом из них двоек столько же, сколько троек)
Для вершины 4 такая вершина — 1.
Для вершины 5 таких вершин две — 1 и 4.

Наверняка существует формальный алгоритм на эту тему, но я не знаю по каким словам его искать.

Здравствуйте, Sinclair, Вы писали:

S>Наверняка существует формальный алгоритм на эту тему, но я не знаю по каким словам его искать.

Не знаю, есть ли формальный алгоритм (тем более, как называется). Но можно придумать свой. Вроде бы не слишком сложный процесс.

Задача

Пусть есть граф G, начальная вершина S (черный кружок в примере) и целевая вершина V. Мы хотим найти такие вершины T, которые на любом пути из S в V встречаются столько же раз, сколько сама V.

Шаг 1: Упрощаем циклы с V

Построим граф G1, который повторяет G за исключением ребер, выходящих из V (целевой вершины). Вместо ребер (V->T) мы добавим ребра (S->T) (т.е. ребро из "конечной" вершины мы заменяем на ребро из "стартовой" вершины). Если в примере V=3, то мы заменяем ребро 3->2 на ребро S->2. По сложности мы укладывается в O(V+E) (сумма количества вершин и ребер).

Шаг 2: Удаляем "недостижимые" вершины

Строим граф G2, который состоит из вершин G1, которые одновременно:

• Достижимы из S
  
• Из этих вершин достижима V

Также сохрянем все ребра между оставленными вершинами. Реализация — два прохода по графу (в ширину или глубину), O(V+E).

Вершины, которые мы удалили, не лежат ни на одном пути из S в V (либо не достижимы со старта, либо ни один путь не ведет в целевую вершину).

Шаг 3: Схломываем циклы

Строим граф G3 путем удаления циклов. Пусть у нас есть цикл из вершин L1, L2, ... LN. Удаляем цикл и заменяем "транзитные" ребра. Т.е. если было ребро I->Lk и ребро Lm->J, то в результате удаления цикла у нас получается ребро I->J. Граф G3 — это результат процесса, когда циклов не осталось.

Очевидно, что ни одна из вершин, удаленных в процессе, не удовлетворяет условию задачи. У нас есть путь S...Lk...V. Тогда мы можем построить и путь S...LkL(k+1)...LNL1...L(k-1)...V. В этом пути все вершины из цикла встречаются на один раз больше, чем в исходном (мы добавили цикл). Т.е. если количество Lk и V совпадало в одном пути, то не совпадает в другом. Сложность зависит от реализации, поэтому

Шаг 3: Детали реализации

В описании выше мы создаем много ребер. Это не очень хорошо. В реализации можно просто заменять весь цикл L1, ..., LN одной новой вершиной L. В этом случае в L будут входить все ребра, которые входили в Li. Соответсвенно, исходящими из L будут все ребра, исходящие из Li. Каждую такую "слитую" вершину мы будем специально помечать. Такие помеченные вершины не будут входит в ответ (но могут использоваться как любые другие на следующих шагах алгоритма).

Сливать мы будем поиском в глубину (Depth-first search). Как только мы видим обратное ребро, мы начинаем объединять текущую вершину с предыдущей (top на стеке вызовов с ее предшественником). Вершины мы представляем как

struct Node {
  incomingFromInidices: DoubleLinkedList[Int],
  visitedOutgoingIndices: DoubleLinkedList[Int],
  notVisitedOutgoingIndices: DoubleLinkedList[Int],
}

Ну и далее объединяем, пока ребро не вырождается в тривиальное L->L. Два списка для outgoing (посещенные и не посещенные) нужны, чтобы их эффективно объединять и потом продолжать depth first search из "объединенной" вершины (мы не хотим повторно ходить туда, где уже были).

В такой структуре слияние списокв связности выполняется за O(1) (мы "разрушаем" один из двухсвязных списков и целиком переносим его цепочку элементов). Обратите внимание — мы не перенумеровываем узлы! Вместо перенумерации мы используем систему непересекающихся множеств. В результате мы получаем амортизированную сложность (amortized cost) O(V*alpha(E)+E) где alpha — функция, обратная функции Аккермана. На практике в земных условиях эту alpha(E) можно ограничить константной .

Шаг 4: Построение результата

Строим граф G4, который является ненаправленной версией G3. Строим множество точек сочленения (Articulation Points). Найденные шарниры (точки сочленения) являются исходными вершинами (если мы сливаем цикл в вершину, нужно исключить вершины, которые явлюятся результатом слияния).

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

Лемма 4.1. Пусть J является шарниром в G4. Тогда любой путь из S в V в G3 проходит через J в G3

Доказательство от противного. Пусть J является шарниром в G4, но в G3 есть путь из S в V, не проходящий через J. В этом случае такой же путь из S в V есть и в G4. Для любой вершины T в G3 у нас есть хотя бы один путь из S в T и хотя бы один путь из T в V (шаг 2). Кроме того, один из путей S...T и T...V (в G3) не содержит J (иначе есть путь S.J.T.J.V, т.е. есть цикл J.T.J в G3, это противоречит критерую остановки на шаге 3). Т.е. в G4 есть либо путь S...T, либо путь T...V. Т.е. все вершины связны. Т.е. J не является шарниром в G4. Противоречие.

Лемма 4.2. Пусть все пути из S в V в G3 проходят через J. Тогда J является шарниром в G4.

Допустим, утверждение не выполняется. Все пути из S в V проходят через J, но J не является шарниром в G4. Рассмотрим граф G3\J, который получается из G3 удалением вершины J. Покрасим вершину S и все вершины, достижимые из S в G3\J в красный цвет. V в красный цвет не покрашена (иначе есть путь S...V, не проходящий через J). Но при этом есть какой-то путь между S и V в G4 (неориентированном графе). В таком случае есть какое-то ребро N->R (где R — красная вершина, N — не красная вершина) в G3 (мы можем пройти в обратном направлении в G4 и дойти до V). Рассмотрим пристальнее вершину N. Все пути из S в N в G3 ведут через J (иначе N была бы красной). При этом все пути из любой красной вершины в V (в G3) тоже идут через J (иначе V была бы красной). Т.е. в G3 есть путь S.J.N.J.V. Т.е. есть цикл J.N.J, что противоречит построению на шаге 3.

Лемма 4.3. Пусть все пути из S в V в G3 проходят через J. Тогда J удовлетворяет условию задачи

Рассмотрим любой путь из S в V в G. Пусть этот путь S...V...V...V...V. В этом случае вершина J находится как на сегменте S...V (начальный граф), так и на каждом сегменте V...V (мы видим эти пути через ребра, добавленные на шаге 1). Наше преобразование на шаге 3 удаляло вершины (и могло удалить из пути в G), но не добавляло новые вершины ни в какие из путей (мы не рассматриваем "синтетические" вершины, полученные в результате слияния). Т.е. J присутствует как минимум столько раз, сколько присутствет сама V. По построению, мы не можем попать из J в J в G3 (шаг 3, где мы удалили циклы). Значит мы можем попасть из J в J в G только через V. Т.е. на каждом сегменте S...V и V...V у нас ровно одна J. Что и требовалось.

Лемма 4.4. Пусть J удовлетворяет условию задачи. Тогда все пути из S в V в G3 проходят через J.

Во-первых, если есть цикл J...J, не проходящий через V (т.е. не существует в G3), J не может удовлетворять условию задачи. Если есть маршрут S...J...V, мы может построить альтернативу S..J..J..V (где J..J не проходит через V). И в одном из маршрутов количество J и V будет различным. Значит J присутствует в G3.

Допустим, есть маршрут S...V в G3, не проходящий через J. Рассмотрим первое ребро S->I этого маршрута SI..V. Если S->I есть в G, тогда маршрут SI..V есть в исходном графе и не включает J (т.е. J не удовлетворяет условию). Если же S->I нет в G, значит в G есть ребро V->I (и мы добавили S->I в G1 на шаге 1). Тогда есть маршрут S...VI...V. Здесь два V. И максимум один J (на первом сегменте). Т.е. J не удовлетворяет условию задачи.

Шаг 4: Заключение

Таким образом, исходя из лемм, все шарниры в G4 явлюятся ответами (и только шарниры являются искомыми вершинами). Сложность алгоритма построения шарниров (на основе алгоритма Тартьяна) О(V+E).

Итоги

Итого, мы имеем сложность O(O(V*alpha(E)+E), что на практике эквивалентно O(V+E).

Проверяйте, может где-то ошибся. Если никто не предложит названия существующего алгоритма, может нам статью куда-нибудь написать? Пусть назовут алгоритм нашими именами .