Орграфы - классификация вершин подсчётом исходящих путей.

[MetaMorphy]

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

Задан ориентированный граф. Каждой его вершине сопоставим функцию, значением которой на целом неотрицательном числе $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).$$

Вершины назовём эквивалентными, если их функции совпадают.

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

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

[arseniiv]

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 --

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

[MetaMorphy]

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

(Оффтоп)

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