Случайное создание графа на основе количества соединений на каждом узле

Question

Я пытаюсь создать график на основе некоторых имеющихся у меня данных.

Этот график должен иметь N узлы, где количество ребер в каждом узле равно случайному числу P(k), где k — «индекс» узла (в основном произвольный).

Мой вопрос: есть ли реальный способ сделать это?Я думаю, что мне нужно больше данных, определяющих либо плотность, либо другую степень связей (N1->N2->N3), но я не совсем уверен.

Answer 1

По сути, вы хотите создать график с некоторой последовательностью степеней (которая должна быть случайной, но это не имеет значения);это называется проблема реализации графа что решается, например.посредством Алгоритм Гавела-Хакими в том смысле, что алгоритм вернет (простой) граф с желаемой последовательностью степеней, если это возможно (такие последовательности называются графика).Обратите внимание, что не все конечные последовательности над $\mathbb Н$ являются графическими, напримерлюбая последовательность, сумма членов которой дает нечетное число, не может быть изображена с помощью лемма о рукопожатии (который утверждает, что сумма всех степеней в графе равна 2-кратному числу ребер в графе и, следовательно, четна).Далее решения в общем случае не будут единственными:Последовательность степеней $(2, 2, 2, 2, 2, 2)$ например, может быть реализовано с помощью графа цикла $C_6$ размера $6$ или непересекающийся союз $C_3 \mathop{\dot\cup} C_3$ двух графов циклов $C_3$ размера $3$ каждый.

Многие библиотеки графов для языков программирования имеют реализации алгоритмов для этой задачи, например библиотека Python сетьx.