2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Неподвижная точка(нт) в графе
Сообщение11.01.2016, 02:04 


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

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


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

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


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

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


24/12/09
25
Skeptic писал(а):
1. Имеются только две вершины, соединённыё направленным ребром из вершины 1 в вершину 2. Для равенства числа исходящих рёбер в вершине 2 добавлена петля.
$2$ - нт, тк можно взять путь единичной длины.
Skeptic писал(а):
2. Имеем кольцевой граф с направленными рёбрами, образующими контур.
Никакая вершина не является нт.
Skeptic писал(а):
3. Имеется двоичное дерево с ветвями направленными от корня. Для равенства числа исходящих рёбер на концевые вершины добавлены петли.
Никакая вершина не является нт.

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

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

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


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

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


24/12/09
25
Skeptic писал(а):
если неподвижная точка - это вершина направленного графа, из которой нет перехода на другие вершины
Не согласен, необязательно у нт могут быть только петли.

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


22/12/08
17
Санкт-Петербург
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, поможет ли нам это предположение или опять не туда смотрим ?
Не знаю, мне не помогает.
Первая моя мысль из поста где-то выше точно не работает в таком виде: мы можем ошибиться и пойти не туда, после чего все вершины никогда не склеятся, хотя по другому пути могли бы склеиться.

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

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


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

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


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

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


24/12/09
25
Skeptic, кол. в пределах $[0, n]$

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


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

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


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

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

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



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

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


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

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