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

[jhendrix]

Gassa, поможет ли нам это предположение или опять не туда смотрим ?

[jhendrix]

Есть предположение: Любая задача сводится к детерминированному конечному автомату, а у нас в условии уже есть дка. Осталось только найти задачу, кот. сводится к ней. Тогда алфавит для дка - множество путей удовл. условию нт. Теория об обратном переходе есть в ка ?

[Skeptic]

jhendrix, определите точно, что такое неподвижная точка на конкретных графах
Например.
1. Имеются только две вершины, соединённыё направленным ребром из вершины 1 в вершину 2. Для равенства числа исходящих рёбер в вершине 2 добавлена петля.
2. Имеем кольцевой граф с направленными рёбрами, образующими контур.
3. Имеется двоичное дерево с ветвями направленными от корня. Для равенства числа исходящих рёбер на концевые вершины добавлены петли.
Какие вершины в этих графах будут неподвижными точками?

[jhendrix]

Skeptic писал(а):

1. Имеются только две вершины, соединённыё направленным ребром из вершины 1 в вершину 2. Для равенства числа исходящих рёбер в вершине 2 добавлена петля.

$2$ - нт, тк можно взять путь единичной длины.

Skeptic писал(а):

2. Имеем кольцевой граф с направленными рёбрами, образующими контур.

Никакая вершина не является нт.

Skeptic писал(а):

3. Имеется двоичное дерево с ветвями направленными от корня. Для равенства числа исходящих рёбер на концевые вершины добавлены петли.

Никакая вершина не является нт.

-- Пн янв 11, 2016 10:16:25 --

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

[Skeptic]

jhendrix, если неподвижная точка - это вершина направленного графа, из которой нет перехода на другие вершины, то, удалив петли, получим висячие вершины, не имеющие выходящих рёбер. Их них нужно выбрать те, которые достижимы из других вершин графа. Эта задача решается последовательным возведением матрицы смежности графа в степень с анализом на каждом шагу заданных столбцов. Можно использовать матрицу рёбер, как вы предложили, но это более сложный и ненаглядный способ решения.

[jhendrix]

Skeptic писал(а):

если неподвижная точка - это вершина направленного графа, из которой нет перехода на другие вершины

Не согласен, необязательно у нт могут быть только петли.

[Gassa]

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

jhendrix, определите точно, что такое неподвижная точка на конкретных графах
Например.
1. Имеются только две вершины, соединённыё направленным ребром из вершины 1 в вершину 2. Для равенства числа исходящих рёбер в вершине 2 добавлена петля.
2. Имеем кольцевой граф с направленными рёбрами, образующими контур.
3. Имеется двоичное дерево с ветвями направленными от корня. Для равенства числа исходящих рёбер на концевые вершины добавлены петли.
Какие вершины в этих графах будут неподвижными точками?

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

Эти два примера показывают, что порядок рёбер из вершины в задаче важен. Матрица смежности теряет информацию о порядке.

-- Пн янв 11, 2016 17:04:24 --

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

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

...

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

Теперь главный вопрос, количество н.т. может быть больше $k$ ?

Да, может. Может быть любым от $1$ до $n$. Может быть как больше, так и меньше $k$.

jhendrix писал(а):

Gassa, поможет ли нам это предположение или опять не туда смотрим ?

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

А откуда всё-таки задача?

[jhendrix]

Есть еще один вариант. Пусть у нас есть граф из $n$ вершин. Обозначим $t(m)$ - количество вершин у которых ровно $m$ исходящих петель. Тогда $\forall m$ 1) $t(m) \geqslant 2$ $\Rightarrow$ нт нет. 2) $t(m) = 1$ $\Rightarrow$ Инвертируем ребра, удаляем $m$ петель и забываем про нумерацию(тк любая последовательность гарантирует нам ту самую вершину с петлями), остается пройтись по всем остальным вершинам. Если прошлись то нам повезло.
В остальных случаях не понятно что делать, остается только перебор.

[Skeptic]

jhendrix, сколько НТ может быть в графе?

[jhendrix]

Skeptic, кол. в пределах $[0, n]$

[Skeptic]

Можно ли из нт попасть в другие вершины графа?

[Skeptic]

Если в графе есть НТ, то она единственная.