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

[arseniiv]

Как хотите. Это ещё раз подчёркивает, что я не понял, что у вас там с маркировкой, поскольку у Skeptic она не упоминается.

[jhendrix]

arseniiv, а как определить есть ли у графа замкнутая цепь ?

[arseniiv]

А почему вопрос ко мне одному?

[Gassa]

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

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

Кажется, что это неправильная переформулировка. Ведь все вершины должны быть достижимы не просто так, а по одному и тому же "пути". Путь - это номера рёбер, которые нужно выбирать на каждом шаге. Рёбра из каждой вершины (или в каждую вершину, если мы уже развернули задачу) пронумерованы.

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

-- Сб янв 09, 2016 02:41:48 --

В целом есть две мысли.

1. Идти и склеивать вершины. Пусть мы изначально стоим во всех вершинах одновременно. Сделаем, например, из каждой ход по ребру номер 123. Множество вершин, в которых мы сейчас могли оказаться, явно не увеличилось. Возможно, уменьшилось.

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

Если вершины "склеились", они во всём дальнейшем пути так и останутся склеенными.

Осталось понять, могли ли мы при этом ошибиться - то есть сделать ход из всех вершин по такому ребру, что дальше не получится их склеить. Если не могли, то из этого делается полиномиальное решение: нужно всего лишь научиться любым образом уменьшать размер множества хотя бы на единицу за полином.

Аналогично можно идти с конца и расклеивать одну исходную вершину на много, пока не получим все.

2. Построить матрицу переходов за 2, 3, 4, ... шага. Или за 2, 4, 8, ... шагов.

Хочется понять, что такое матрица переходов за два шага. Понятно, что можно построить матрицу $n \times (m \cdot m)$, в которой для каждой начальной вершины и для каждой пары номеров рёбер указать, куда мы попали. Но хочется уместить это в матрицу $n \times m$, не потеряв полезную для задачи информацию.

Если это возможно, решение будет такое: найти матрицу переходов за какое-нибудь большое число шагов, а потом доказать, что такого количества шагов точно хватит.

[Skeptic]

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


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

[jhendrix]

Есть еще один вариант, возводить матрицу в степень пошагово и сохранять пути в каждой ячейке, если при этом на каком-нибудь шаге в столбце/строке(направления ребер поменяли) окажутся все $1$ и пересечение ячеек по столбце/строке не пустое то нам повезло. Если такой вариант неправильный то нужно применить динамику, обычно такой подход спасает нас от перебора.

[Skeptic]

Всё на самом деле проще. Оставляем исходную формулировку задачи, и строим матрицу смежности $M$.
Выражение $\sum^n_{k=1} M^k$ вычисляет количество прямых и обратных путей от любой вершины до всех остальных. Подбираем $n$ (максимальная длина пути) таким, чтобы интересующая нас строка или столбец были заполнены полностью, кроме, может быть, самой вершины. В получающейся матрице строки содержат прямые пути, а столбцы обратные.

[arseniiv]

(Оффтоп)

Skeptic
Вы упорно игнорируете, что рассматриваются не все пути разом, а классы путей, содержащие каждый ровно по одному пути, начинающемуся в каждой из вершин, и все пути одного класса должны быть равной длины (и это не все ограничения). При этом вопрос состоит в том, есть ли хотя бы один класс, все пути из которого заканчиваются в одной и той же вершине. Так что всё не «гораздо проще» — простой достижимости тут недостаточно.

Остаётся вопрос, почему сам автор темы не заметил отличия, но ладно уж, пускай он останется риторическим.

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

кроме, может быть, самой вершины

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

[Skeptic]

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

Дается ориентированный граф в котором могут быть циклы в том числе и петли. Каждая вершина имеет одинаковое количество исходящих ребер.
Каждый путь характеризуется набором ребер начиная с некоторой вершины. Если найдется хотя бы какой-нибудь путь(длина тут не важна) стартующая с любой вершиной и заканчивающая в одной и той же вершине то эту вершину мы называем нт. Требуется определить сущ. ли в графе нт.

(Подчёркнуто мной)
arseniiv, я не вижу никаких ограничений длины пути и один класс путей.
В постановке неясная фраза

Цитата:

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

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

[arseniiv]

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

я не вижу никаких ограничений длины пути и один класс путей

Потом Gassa привёл интерпретацию

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

Условие на самом деле можно понять. Есть матрица $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)$.

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

[Skeptic]

Gassa сказал, что, если есть путь $P = (p_1, p_2, \ldots, p_k)$, то проходить его надо сначала по ребру $p_1$, затем по ребру $p_2$ и т.д. Закончил вопросом: "Есть ли такой путь?". В чём другая интерпретация постановки задачи?

arseniiv в сообщении #1089604 писал(а):

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

arseniiv, смотрите постановку задачи. Там пути разной длины, я даже это специально для вас подчеркнул.
arseniiv, возражать и обвинять оппонента в непонимании проще, чем помочь ТС и привести своё решение задачи.

[arseniiv]

А я приводил, если что. На предыдущей странице.

-- Вс янв 10, 2016 21:59:34 --

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

смотрите постановку задачи. Там пути разной длины, я даже это специально для вас подчеркнул.

Да понял, что вас не переубедить. Ну а то, что jhendrix считает постановки вашу и Gassa одинаково хорошими, видимо, тоже незачем пытаться исправить. Коммуникационные провалы в жизни случаются, увы.

-- Вс янв 10, 2016 22:05:15 --

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

помочь ТС

Помощью было бы сначала убедиться, что все понимают задачу одинаково — в том числе сам ТС. А я уже и в последнем не уверен.

[jhendrix]

Давайте я приведу решение методом перебора. Пусть у нас $n$ вершин и каждая вершина имеет ровно $m$ - исходящих ребер. Я начинаю переберать все пути по возрастанию длин и лексикографическому порядку.

Пути длины $1 : (0), (1), \dots (m-1)$
Пути длины $2 : (0, 0), (0, 1), \dots (m-1, m-1)$
Пути длины $3 : (0, 0, 0), (0, 0, 1), \dots (m-1, m-1, m-1)$

$\dots$

Путь это последовательность номеров ребер.

После всего этого я начинаю проверять каждый путь. Пусть мы сейчас проверяем путь длиной $3$, а сам путь такой $(1, 0, 0)$. Теперь начинаем проверять для каждой вершины куда этот путь ведет. Допустим мы получили вершины $\{v_1, v_3\}$. Значит этот путь не подходит. Нам нужно чтоб в множестве получившихся вершин содержался только один элемент, тогда это озн. что мы нашли путь кот. стартует с любой вершины и заканчивается в одной и той же вершине.
Путей могут быть слишком много причем разной длины удовлетворяющий этому условию, но нам нужен хотябы один.

[jhendrix]

Я тут кое-что заметил. Если такой путь найдется и предположим что его длина минимальная из всех сущ. например $p = (p_1, p_2, \dots p_k)$, то путь $p^1 = (p_1, p_2, \dots p_k, p_1)$ длиной $k+1$ заканчивающийся на $p_1$-ом ребре после $p_k$-го тоже подходит и если продолжить дальше то мы сможем получить др нт-и. Так что их примерно будет $k$, те рассматриваем пути длиной $[k, 2k]$. А дальше тоже самое $(2k, 3k, 4k \dots)$. Теперь главный вопрос, количество н.т. может быть больше $k$ ? Если не больше то будет супер. Дальше я не знаю как нам это поможет. Может быть походу поиска цикла для каждой вершины проверять за линейное время вершину на нт.

[Gassa]

jhendrix писал(а):

Давайте я приведу решение методом перебора.

Описанное решение согласуется с моей переформулировкой условия, если что.

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

Я тут кое-что заметил. Если такой путь найдется и предположим что его длина минимальная из всех сущ. например $p = (p_1, p_2, \dots p_k)$, то путь $p^1 = (p_1, p_2, \dots p_k, p_1)$ длиной $k+1$ заканчивающийся на $p_1$-ом ребре после $p_k$-го тоже подходит и если продолжить дальше то мы сможем получить др нт-и.

Если путь является искомым (сводит все вершины в одну), то все пути, префиксом которых он является, тоже сводят все вершины в одну: раз "склеившись", вершины уже не могут "расклеиться" обратно.
Из этого следует, что все вершины, достижимые из неподвижной точки, также являются неподвижными точками.
Но ничего не следует об их количестве (может быть от $1$ до $n$).

-- Пн янв 11, 2016 00:52:04 --

Кстати, jhendrix, откуда задача?