Неподвижная точка(нт) в графе

[jhendrix]

Дается ориентированный граф в котором могут быть циклы в том числе и петли. Каждая вершина имеет одинаковое количество исходящих ребер. Можно задать граф таблицой $g$ размером $n \times m$, где $n$ - количество вершин пронумерованных от $0$, $m$ - количество исходящих ребер у вершин, пронумерованных также от $0$. Тогда элемент таблицы $g[v][e]$ показывает номер вершины(место назначения) eсли мы перешли по ветке $e$ из вершины $v$.
Каждый путь характеризуется набором ребер начиная с некоторой вершины. Если найдется хотябы какой-нибудь путь(длина тут не важна) стартующая с любой вершиной и заканчивающая в одной и той же вершине то эту вершину мы называем нт. Требуется определить сущ. ли в графе нт.
Пример:
$n = 4$, $m = 2$. Таблица $g = [ [1, 2], [3, 2], [1, 3], [1, 2] ]$, где $g[0][1] = 2$, означает что у вершин $0$ и $2$ есть ветка с номером $1$. Ответ будет да(true), т.к. сущ. нт $2$, можно взять путь(набор ребер) $(0, 1)$, тогда если применить этот путь к любой вершине включая саму нт, то мы попадем всегда в нее.
Я ее решил простым перебором, но хотелось бы узнать есть ли лучший метод ?

[sqribner48]

jhendrix

jhendrix в сообщении #1088644 писал(а):

Если найдется хотябы какой-нибудь путь(длина тут не важна) стартующая с любой вершиной и заканчивающая в одной и той же вершине

Что-то не понятно: «путь»… «стартующая», путь обычно стартует поэтому он стартующий. А вот это - «стартующая с любой вершиной». Он(путь) что, стартует вместе с любой вершиной, или стартует с нее? И, наконец, ударная концовка - "заканчивающая в одной и той же вершине". Sic!

jhendrix в сообщении #1088644 писал(а):

$n = 4$, $m = 2$. Таблица $g = [ [1, 2], [3, 2], [1, 3], [1, 2] ]$, где $g[0][1] = 2$, означает что у вершин $0$ и $2$ есть ветка

Какая-то странная у вас таблица. Вы не находите? И что такое «ветка»? Это ребро, или последовательность попарно смежных ребер?
Мне кажется, что для большей наглядности необходимо привести тут диаграмму графа из этого примера или его матрицу смежности.

[jhendrix]

sqribner48, матрица смежности не нужна, т.к. мы должны учитывать номера ребер. Ветка это ребро графа. У каждой ветки есть вес - номер этой ветки. Представьте, что у каждой вершины есть состояния и в зависимости от того какое вы состояние выберите вы попадете в некоторую вершину. Путь это последовательность веток. Если найдется путь в независимости от того откуда вы стартуете и получите в конце одну и ту же вершину, то нам повезло.

[arseniiv]

Похоже, всё-таки не стоило выкидывать «лишнюю» информацию о состояниях из графа. Верните её, пожалуйста, назад. А то получается весьма странная задача. Если в графе есть цикл, все его вершины в интересующем смысле неподвижные точки? Или надо рассматривать только пути, которые нельзя продолжить? Но о последнем не упомянуто.

[jhendrix]

arseniiv, мы же путь фиксируем для каждой стартовой вершины.

[Gassa]

jhendrix в сообщении #1088644 писал(а):

Пример:
$n = 4$, $m = 2$. Таблица $g = [ [1, 2], [3, 2], [1, 3], [1, 2] ]$, где $g[0][1] = 2$, означает что у вершин $0$ и $2$ есть ветка с номером $1$. Ответ будет да(true), т.к. сущ. нт $2$, можно взять путь(набор ребер) $(0, 1)$, тогда если применить этот путь к любой вершине включая саму нт, то мы попадем всегда в нее.
Я ее решил простым перебором, но хотелось бы узнать есть ли лучший метод ?

Условие на самом деле можно понять. Есть матрица $A$ размера $n \times m$. Путь - это последовательность чисел от $0$ до $m - 1$. Чтобы пройти по пути $P = (p_1, p_2, \ldots, p_k)$, начиная из вершины $u$, нужно сначала пойти по ребру номер $p_1$ из вершины $u$, то есть оказаться в $v = A[u][p_1]$. Далее нужно сделать шаг по ребру номер $p_2$ из новой вершины, то есть оказаться в $w = A[v][p_2] = A[A[u][p_1]][p_2]$. И так далее. Назовём $P (u)$ конечную вершину пути $P$, который мы начали в вершие $u$.

Вопрос в том, есть ли такая последовательность $P$, что $P (0) = P (1) = \ldots = P (n - 1)$.

Это комментарий для тех, кому сложно понять условие (я тоже не с первого раза понял, но разобрался). Как решать - не знаю.

[jhendrix]

arseniiv, что вам не понятно конкретно ? Берем путь(фиксируем его), начинаем проверять для каждой вершины куда этот путь ведет. Если он ведет для всех вершин в одну и ту же вершиу $x$, то $x$ - нт.

-- Пт янв 08, 2016 00:50:38 --

Gassa, да вы правильно поняли условие.
Решить ее можно перебором, но сложность будет экспонента. Ясно, что можно сгенерировать все пути(наборы) длины равной не больше количеству вершин $n$, со значениями $[0, m - 1]$. Т.е. ${ {(0), (1), \dots (m-1)}, {(0, 0), (0, 1), \dots (m-1, m-1)}, \dots (m-1, \dots m - 1)}$ и проверять для каждой вершины. Сложность $O(m^{n + 1} \cdot n)$

[arseniiv]

Gassa в сообщении #1088846 писал(а):

Это комментарий для тех, кому сложно понять условие (я тоже не с первого раза понял, но разобрался). Как решать - не знаю.

Спасибо! Мне в терминах конечного автомата, которому на вход подаётся одна и та же строка, но начинает который из разных состояний, кажется более ясной. Вопрос в том, есть ли такая строка, которая приведёт из чего угодно в одно и то же, OK.

Мне в голову приходит идти в обратном направлении. Сначала за $O(n)$ строим какую-нибудь удобную для этого структуру, по вершине и индексу дуги выдающую вершины, из которых дуги с таким индексом ведут в данную. Потом поехали по вершинам смотреть, куда можно уйти. Если куда угодно — ура, и заканчиваем. Оптимизации пока в голову не приходят.

[Skeptic]

jhendrix в сообщении #1088644 писал(а):

Дается ориентированный граф в котором могут быть циклы в том числе и петли. Каждая вершина имеет одинаковое количество исходящих ребер. Можно задать граф таблицой $g$ размером $n \times m$, где $n$ - количество вершин пронумерованных от $0$, $m$ - количество исходящих ребер у вершин, пронумерованных также от $0$. Тогда элемент таблицы $g[v][e]$ показывает номер вершины(место назначения) eсли мы перешли по ветке $e$ из вершины $v$.
Каждый путь характеризуется набором ребер начиная с некоторой вершины. Если найдется хотя бы какой-нибудь путь(длина тут не важна) стартующая с любой вершиной и заканчивающая в одной и той же вершине то эту вершину мы называем нт. Требуется определить сущ. ли в графе нт

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

[jhendrix]

Skeptic, принцип понятен, но надо еще рассмотреть краевой случай когда у нас граф представляется ввиде колца($v_1 \to v_2 \to \dots v_n \to v_1$).

[Skeptic]

jhendrix, для возведения матрицы смежности в степень конкретная форма графа безразлична.

(Оффтоп)

Из вершин графа может исходить разное количество рёбер, связывающих вершины.

[arseniiv]

Skeptic
Уже ведь стало известно, что задача не такая простая.

Skeptic в сообщении #1088975 писал(а):

Из вершин графа может исходить разное количество рёбер, связывающих вершины.

jhendrix в сообщении #1088644 писал(а):

Каждая вершина имеет одинаковое количество исходящих ребер.

[jhendrix]

arseniiv, у Skeptic все равно правильный подход, но нужно как то проверить краевой случай, дело в том что когда мы получаем матрицу достижимости в котором есть строка $i$ состоящая только из $1$, это еще не означает что $v_i$ - нт. Как это преодолеть я не понимаю, т.к в графе слишком много циклов, а нужно проверит наличие замкнутой цепи.

Как вы говорили arseniiv, я меняю направления ребер на противоположное и строю мд.

[arseniiv]

(Оффтоп)

jhendrix в сообщении #1089076 писал(а):

у Skeptic все равно правильный подход

Значит, я всё-таки не понял Gassa, или вы не поняли, понял ли вас Gassa, или что-то в этом роде.

[jhendrix]

arseniiv, в смысле ? Ваш подход и у Skeptic одинаковый и условие кот. Gassa переформулировал правильное. Даже если там будет разные кол. исходящих ребер как Skeptic говорил этот подход все равно правильный, проблема только возникает в краевом случае.