2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Неподвижная точка(нт) в графе
Сообщение07.01.2016, 05:33 


24/12/09
25
Дается ориентированный граф в котором могут быть циклы в том числе и петли. Каждая вершина имеет одинаковое количество исходящих ребер. Можно задать граф таблицой $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)$, тогда если применить этот путь к любой вершине включая саму нт, то мы попадем всегда в нее.
Я ее решил простым перебором, но хотелось бы узнать есть ли лучший метод ?

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение07.01.2016, 13:32 


13/05/14
231
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$ есть ветка

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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение07.01.2016, 19:43 


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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение07.01.2016, 23:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 00:25 


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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 00:26 


22/12/08
17
Санкт-Петербург
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)$.

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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 00:30 


24/12/09
25
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)$

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 01:14 
Заслуженный участник
Аватара пользователя


27/04/09
19781
Уфа
Gassa в сообщении #1088846 писал(а):
Это комментарий для тех, кому сложно понять условие (я тоже не с первого раза понял, но разобрался). Как решать - не знаю.
Спасибо! Мне в терминах конечного автомата, которому на вход подаётся одна и та же строка, но начинает который из разных состояний, кажется более ясной. Вопрос в том, есть ли такая строка, которая приведёт из чего угодно в одно и то же, OK.

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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 09:58 


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

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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 13:24 


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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 14:53 


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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 14:54 
Заслуженный участник
Аватара пользователя


27/04/09
19781
Уфа
Skeptic
Уже ведь стало известно, что задача не такая простая.

Skeptic в сообщении #1088975 писал(а):
Из вершин графа может исходить разное количество рёбер, связывающих вершины.
jhendrix в сообщении #1088644 писал(а):
Каждая вершина имеет одинаковое количество исходящих ребер.

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 20:31 


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

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

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 20:56 
Заслуженный участник
Аватара пользователя


27/04/09
19781
Уфа

(Оффтоп)

jhendrix в сообщении #1089076 писал(а):
у Skeptic все равно правильный подход
Значит, я всё-таки не понял Gassa, или вы не поняли, понял ли вас Gassa, или что-то в этом роде.

 Профиль  
                  
 
 Re: Неподвижная точка(нт) в графе
Сообщение08.01.2016, 21:11 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 42 ]  На страницу 1, 2, 3  След.

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group