Как найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными?

Question

[Тимур Мухамедишин]

Здравствуйте! Задача состоит в следующем:

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

Не совсем разобрался с методом решения. Представляется наиболее удобным использование обхода графа в глубину. Граф храню в виде списка смежности. Думаю, нужно делать что-то в таком духе: 1) найти первый путь между двумя заданными вершинами, положить путь в массив 2) найти еще один путь, сравнить с тем, что в массиве, вершины второго пути, которых нет в массиве, убрать оттуда. Так делать до тех пор пока массив не опустел (значит, нет искомой вершины) или не нашли все пути (искомые вершины останутся в массиве).

Остается вопрос: как найти все эти различные пути? Буду очень признателен любым подсказкам.

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

Answer 1

[Labunsky]

1. Представим все вершины числами от 0 до n;
2. Заводим массив visited, забитый нулями, и переменную count = 0;
3. Находим кратчайший путь между v и u (например, Дейкстрой). Если такой путь существует, то count++ и для каждой его вершины g, отличной от u и v, visited[g]++. Если пути не существует, перейти к шагу 6;
4. Удаляем последнее ребро в найденом пути;
5. Возвращаемся к 3.
6. Ищем такую g, что visited[g] == count. Если такая есть, она и является искомой;

Возможно, данный алгоритм не самый оптимальный, зато простой.

Comments

[Labunsky]

upd: На ночь глядя не заметил, что алгоритм не будет работать в 100% случаев, так как удаляемое ребро может принадлежать нескольким путям сразу.
Вместо поиска кратчайших и удаления ребер стоит искать сразу все пути поиском в ширину, обработка же их для нахождения остается такой же

Answer 2

[Wataru]

Все такие вершины являются точками сочленения. Ведь, удалив такую вершину из графа больше не будет пути между двумя вершинами, а значит граф развалился на новые компоненты связности. Есть алгоритм на основе Dfs, который их ищет. Это все работает за O(V+E). Предложенный вами алгоритм с удалением по одной вершине вполне себе работает, но будет медленнее: O(V(V+E)). Для небольших графов может и подойдет.

Потом надо найти путь между заданными вершинами и вывести в ответ точки сочленения. Лучше ищите путь тем же DFSом, что и ищите точки сочленения. Так путь будет идти по дереву DFS. Надо найти в нем LCA двух искомых точек (Пик пути, после которого он пойдет вниз в другую ветку).

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