Генерация сильно связанных, равномерно распределенных, случайных диаграмм
Поэтому я строю программу, которая использует симуляции Монте-Карло, чтобы найти свойства эволюционной теории графов. Одной из ключевых функций этого является способность генерировать равномерно распределенные случайные графы, чтобы мы могли определить обобщенные свойства графов. Для случая связанных неориентированных графов я реализовал решение, изложенное в этом ответе.
Однако для ориентированных графов генерация однонаправленного однородного остовного дерева, которое вы получаете из алгоритма Уилсона, не гарантирует, что граф сильно связан, и кажется, что добавление дополнительных ребер, чтобы сделать связующее дерево двунаправленным, внесло бы смещение в графики, которые вы генерируете.
Я чувствую, что могу упустить что-то очевидное / неправильно понять что-то, но, по сути, моя просьба, может ли кто-нибудь порекомендовать мне схему высокого уровня, которая позволяет мне генерировать сильно связанные, равномерно распределенные, случайные диаграммы?
2 ответа
Может ли кто-нибудь порекомендовать мне схему высокого уровня, которая позволяет мне генерировать сильно связанные, равномерно распределенные, случайные диаграммы?
У меня была похожая проблема генерации деревьев выражений для тестовых данных. Я обнаружил, что если вы узнаете, как считать уникальные деревья, тогда проблема станет легкой. Под этим я подразумеваю, что для полных бинарных деревьев с N внутренними узлами я нашел число уникальных деревьев, основанных на N, это каталонские числа. Тогда для бинарных деревьев, которые имеют одинарные ветви с N полными узлами, число уникальных деревьев, основанных на N, представляет собой числа Моцкина.
Затем я нашел онлайн-энциклопедию целочисленных последовательностей®. Поэтому, если вам известно значение N, которое может однозначно идентифицировать граф, и вы знаете соответствующее количество уникальных графов для этого N и поместите эти числа в поиск OEIS, вам следует вернуться на страницу, которая поможет вам в вашем поиске. например, каталонские числа для полных бинарных деревьев или числа Моцкина для регулярных двоичных деревьев. По пути я обнаружил, что одним из ключей к их генерации было рекуррентное отношение.
Или вы можете использовать ключевые слова в поиске, но это не может получить точный успех. Я нашел только числа Моцкина, используя последовательность чисел, а не через ключевые слова.
Вот запрос OEIS для сильно связанного орграфа
Теперь, если вы знаете количество для данного N и вы генерируете все графики для данного N или можете иметь однозначное соответствие между значением и графом, тогда вы просто генерируете случайные целые числа и получаете / генерируете соответствующий граф. Если я правильно понимаю вашу проблему, это должно решить ее.
Мое лучшее предположение последовательности OEIS для этого вопроса:
Количество ациклических орграфов с n немечеными узлами. A003087
Который имеет отношение к равномерной случайной генерации больших ациклических орграфов
TL;DR
Для некоторой связанной истории см. Мой вопрос: Улучшение алгоритма для перечисления двоичных деревьев
Самое простое решение, которое я могу придумать, - это случайным образом генерировать равномерно распределенные орграфы и отбрасывать любые, которые не сильно связаны. Это сохранит равномерное распределение и гарантирует собственность, которую вы хотите. Это, вероятно, не очень эффективно, но вы наверняка будете знать, если вы запустите несколько тестов.