Ориентированные графы "делимости"

[kotenok gav]

Возник вот такой вопрос. Пусть мы строим ориентированный граф (вершины - натуральные числа), так, что из вершины $d$ строится стрелка в вершину $a$, если и только если, для заданных функций $f$ и $g$ $f(d)$ делится на $g(a)$. Что можно сказать о графе, зная что-нибудь о этих функциях?

Пока только ясно, что если $f$ - константа, то граф выглядит как некое конечное множество точек (такие $a$, что $g(a)$ делит эту константу), и из всех точек идет ребро в каждую точку из этого множества. Если $f(a)$ делится на $g(a)$ для всех $a$, то граф будет "транзитивным".

[kotenok gav]

kotenok gav в сообщении #1453850 писал(а):

Если $f(a)$ делится на $g(a)$ для всех $a$

Ой, наоборот, если $g(a)$ делится на $f(a)$.

[iifat]

kotenok gav в сообщении #1453850 писал(а):

Что можно сказать о графе, зная что-нибудь о этих функциях?

Зная — что-нибудь да можно. А вот не зная — такое у меня чувство, что дайте мне граф, а уж функции я подберу.

[kotenok gav]

Ок, можете ли вы привести алгоритм нахождения $f$ и $g$ по заданному графу?

[arseniiv]

Если в граф вершинами входят все натуральные числа, то некоторые графы точно не реализуемы, потому что всего их будет несчётное число, да. А вот если только отрезок натурального ряда…

[Serm314]

Близко к обсуждаемому вопросу.
В работе DOI: 10.21681/2311-3456-2018-4-70-76
в связи с графами де Брейна рассматривался граф на множестве вершин ${0,1,...,N}$ такой что $i \to ki(modN)$. Каждая его компонента связности - паук (цикл и подходы). Там же считался его спектр.