Генерация случайных ограничений График

Question

Мне нужно создать рандомизированный граф с фиксированным числом вершин. Я испытываю трудности с получением решения каждый раз.

График Правило

1. каждая вершина будет иметь случайное число соединений, которое не более чем N-1, где N представляет собой общее количество вершин.
2. Вершины не могут содержать прямые подключения к себе
3. Вершины не могут содержать повторяющиеся соединения с другими вершинами.
4. Если вершина A связана с Vertex B, то Vertex B должен подключиться к Vertex A.
5. Каждая вершина должна соединяться с не менее чем тремя другими вершинами. Таким образом, каждая вершина будет располагаться между краями [3, N-1].

Я получаю правильное решение примерно в 70% случаев, но в других случаях я довольно далеко добираюсь до графика, после чего не верны верные вершины. Какие ограничения для вершинных соединений необходимы для гарантии решения?

Что я делаю до сих пор

1. Randomize ряд соединений для каждой вершины между [3, N-1].
2. Убедитесь, что общее количество соединений равно. Если A указывает на B и B указывает на A, то общее количество соединений на графике должно быть четным, или нет решения. Если это нечетно, измените вершину, чтобы общее число было четным.
3. Заполните все вершины, которые полностью ограничены. Таким образом, вершина с N-1 соединениями должна указывать на ВСЕ другие вершины. Заполните соединение из этой вершины ко всем остальным и дайте всем другим вершинам соединение с полностью ограниченными.
4. Обработать каждую вершину тем, насколько сильно она ограничена. Итак, обработайте все вершины с N-2 соединениями, затем N-3-соединение, затем N-4 и т. Д. Сгенерированными случайными индексами вершин.
5. Если новый случайный индекс действителен, подключите их, затем продолжите, если он недействителен, повторите индекс, пока не получите действительное значение. (Графики будут составлять только 7-15 узлов или максимум, поэтому это не займет очень много времени).

Как правило, я добираюсь до последних 2 вершин, но не имею никаких действительных значений, оставшихся с этим методом. Каждому требуется еще одно соединение, но они уже подключены друг к другу. У кого-нибудь есть лучший алгоритм или дополнительное ограничение на количество значений соединений, которые могли бы помочь мне?

Должно быть много решений, учитывая, что существует четное число ребер, но мой алгоритм выше, очевидно, не гарантирует, что он будет найден.

Answer 1

1. Создайте вектор всех вершин с менее чем тремя ребрами.
2. Выберите вершину из вектора в случайном порядке.
3. Скопируйте вектор с выбранной вершиной (вы можете поменять выбранный текст и последний и отрегулировать размер).
4. Также удалите все целевые вершины, уже подключенные к выбранной вершине.
5. Выберите вершину из скопированного вектора, и создать преимущество в каждом направлении между двумя выбрали п вершинами
6. Повторите шаги 1..5 до тех пор, как вектор всех вершин с менее чем 3-х ребер не пусто