Здравствуйте! Задача состоит в следующем:
Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вершинами и отлична от каждой из них.
Не совсем разобрался с методом решения. Представляется наиболее удобным использование обхода графа в глубину. Граф храню в виде списка смежности. Думаю, нужно делать что-то в таком духе: 1) найти первый путь между двумя заданными вершинами, положить путь в массив 2) найти еще один путь, сравнить с тем, что в массиве, вершины второго пути, которых нет в массиве, убрать оттуда. Так делать до тех пор пока массив не опустел (значит, нет искомой вершины) или не нашли все пути (искомые вершины останутся в массиве).
Остается вопрос: как найти все эти различные пути? Буду очень признателен любым подсказкам.
Также есть другая идея, но, как мне кажется, не совсем хорошая. Последовательно удалять каждую вершину графа (кроме двух заданных) и проверять тем же обходом в глубину, есть ли путь между двумя этими вершинами. (Т.е. не оказались ли они в двух разных компонентах связности). Если оказались, то удаленная вершина искомая.
P.S. Найти все пути между двумя вершинами графа не думаю, что подходит мне. В моем графе могут (и скорее всего будут) присутствовать циклы.