Поиск неподвижной точки(нт) в графе

@jhendrix · Регистрация: 23.02.2010

Author24 — интернет-сервис помощи студентам

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

@jhendrix 0 / 0 / 0 Регистрация: 23.02.2010 Сообщений: 184
		1
	Поиск неподвижной точки(нт) в графе 07.01.2016, 05:12. Показов 559. Ответов 0 Метки нет (Все метки) Дается ориентированный граф в котором могут быть циклы в том числе и петли. Каждая вершина имеет одинаковое количество исходящих ребер. Можно задать граф таблицой $https://www.cyberforum.ru/cgi-bin/latex.cgi?$g$$ размером $https://www.cyberforum.ru/cgi-bin/latex.cgi?$n \times m$$ , где $https://www.cyberforum.ru/cgi-bin/latex.cgi?$n$$ - количество вершин пронумерованных от $https://www.cyberforum.ru/cgi-bin/latex.cgi?$0$$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?$m$$ - количество исходящих ребер у вершин, пронумерованных также от $https://www.cyberforum.ru/cgi-bin/latex.cgi?$0$$ . Тогда элемент таблицы $https://www.cyberforum.ru/cgi-bin/latex.cgi?g[v][e]$ показывает номер вершины(место назначения) eсли мы перешли по ветке $https://www.cyberforum.ru/cgi-bin/latex.cgi?e$ из вершины $https://www.cyberforum.ru/cgi-bin/latex.cgi?v$ . Каждый путь характеризуется набором ребер начиная с некоторой вершины. Если найдется хотябы какой-нибудь путь(длина тут не важна) стартующая с любой вершиной и заканчивающая в одной и той же вершине то эту вершину мы называем неподвижной точкой. Требуется определить сущ. ли в графе неподвижная точка. Пример: $https://www.cyberforum.ru/cgi-bin/latex.cgi?$n = 4$$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?$m = 2$$ . Таблица $https://www.cyberforum.ru/cgi-bin/latex.cgi?$g = [ [1, 2], [3, 2], [1, 3], [1, 2] ]$$ , где $https://www.cyberforum.ru/cgi-bin/latex.cgi?$g[0][1] = 2$$ , означает что у вершин $https://www.cyberforum.ru/cgi-bin/latex.cgi?$0$$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?$2$$ есть ветка с номером $https://www.cyberforum.ru/cgi-bin/latex.cgi?$1$$ . Ответ будет да(true), т.к. сущ. неподвижная точка $https://www.cyberforum.ru/cgi-bin/latex.cgi?$2$$ , можно взять путь(набор ребер) $https://www.cyberforum.ru/cgi-bin/latex.cgi?$(0, 1)$$ , тогда если применить этот путь к любой вершине включая саму нт, то мы попадем всегда в нее. Я ее решил простым перебором, но хотелось бы узнать есть ли лучший метод ? 0

	07.01.2016, 05:12

Опции темы