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

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

Вот пример:

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

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