2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Орграфы - классификация вершин подсчётом исходящих путей.
Сообщение28.06.2018, 17:48 


23/10/10
89
Приветствую всех присутствующих. Есть несколько вопросов вокруг да около следующей конструкции.

Задан ориентированный граф. Каждой его вершине сопоставим функцию, значением которой на целом неотрицательном числе $n$ будет число всех путей длины $n$, выходящих из этой вершины. Говоря формально, для графа $(V, E), E \subseteq V^2$, и $v \in V$ положим
$$F_v(0) = 1,\quad F_v(n + 1) = \sum_{\substack{w \in V \\ (v, w) \in E}}F_w(n).$$
Вершины назовём эквивалентными, если их функции совпадают.

Вот это самое отношение эквивалентности меня и интересует. Встречалась ли эта конструкция где-либо ещё? Можно ли его выразить "как-нибудь попроще"? Является ли множество всех (различных) полученных функций линейно независимым, или необязательно? И, наконец, есть ли хороший алгоритм расчёта этого отношения для заданного орграфа (который, скажем, пронумеровал бы классы эквивалентности и пометил бы вершины номерами их классов). Последний вопрос, конечно, наиболее важен - самостоятельную попытку его построить я предпринял (есть некоторая аналогия с алгоритмом Хопкрофта для минимизации детерминированных конечных автоматов), но (задачи всё-таки разные и,) во-первых, он получился довольно сложным, а во-вторых, я не уверен, что он вообще правилен :mrgreen: (три раза он меня не подвёл, впереди четвёртый).

Что касается "интернетов", поиски и вопросы в других форумах результатов пока не дали (спрошу ещё на mathoverflow...).

 Профиль  
                  
 
 Re: Орграфы - классификация вершин подсчётом исходящих путей.
Сообщение28.06.2018, 18:56 
Заслуженный участник


27/04/09
28128
MetaMorphy в сообщении #1323181 писал(а):
Является ли множество всех (различных) полученных функций линейно независимым, или необязательно?
Необязательно. Можно попробовать взять несвязный граф и каждую компоненту «настраивать», чтобы функции для одной из вершин в каждой компоненте получились какие надо. Попробуйте, например, реализовать функции $(1, 1, 2, 0\ldots)$, $(1, 2, 1, 0\ldots)$, $(1, 1, 1, 0\ldots)$, $(1, 2, 2, 0\ldots)$. И вообще произвольные примеры можно строить, беря разные орграфы-леса — из корня дерева можно иметь сколько угодно путей любой положительной длины, пока, конечно, их для одной из длин не окажется ноль.

-- Чт июн 28, 2018 20:59:00 --

Ну или даже не леса, это я чересчур. Можно и одним деревом, интересуясь вершинами, следующими непосредственно за корнем.

 Профиль  
                  
 
 Re: Орграфы - классификация вершин подсчётом исходящих путей.
Сообщение28.06.2018, 22:02 


23/10/10
89
arseniiv: Спасибо, тут я действительно поторопился.

(Оффтоп)

Да и вообще на выходных покопаюсь "в теории" поаккуратнее... глядишь и вопросы будут поконкретнее.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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