ランダム拘束グラフの生成

Question

固定数の頂点を持つランダム化グラフを生成する必要があります。毎回解決策を得るのが難しいです。

グラフルール

1. 各頂点はN頂点の総数で最もN-1である接続のランダムな数を有することになります。
2. 頂点には直接接続することはできません
3. 頂点には他の頂点への重複接続を含めることはできません。
4. 頂点Aが頂点Bに接続されている場合、頂点Bは頂点Aに接続する必要があります。
5. 各頂点は少なくとも3つの他の頂点に接続する必要があります。したがって、各頂点は[3、N-1]の辺を持ちます。

私は時間の約70％の解決策を得ていますが、それ以外のときはグラフにかなりの距離があり、有効な頂点が残っていません。解決策を保証するために頂点接続のどのような制約が必要ですか？

私がやっている何

これまで

1. [3、N-1]の間の各頂点の接続数をランダム。
2. 接続の総数が均一であることを確認します。 AがBとBを指してAを指している場合、グラフ内の接続の総数は偶数でなければならない。そうでなければ解は存在しない。それが奇数ならば、総数が偶数になるように頂点を修正してください。
3. 完全に拘束されている各頂点を入力します。したがって、N-1個の接続を持つ頂点は、他のすべての頂点を指していなければなりません。その頂点から他のすべての頂点への接続を記入し、他のすべての頂点に完全に拘束された頂点への接続を与えます。
4. 各頂点をどれだけ拘束して処理するか。したがって、生成されたランダムな頂点インデックスによってN-2接続を持つすべての頂点、N-3接続、N-4などを処理します。
5. 新しいランダムインデックスが有効な場合は、有効な値を取得するまでインデックスに有効でない場合は、続行します。 （グラフは7〜15ノード程度しかないので極端に長くなりません）。

一般に、最後の2つの頂点に達しますが、このメソッドで有効な値が残っていません。それぞれ1つの接続が必要ですが、すでに相互に接続されています。誰かが私に助けになる接続数の数に、より良いアルゴリズムや追加の制約がありますか？

偶数のエッジがある場合、多くのソリューションが必要ですが、上記のアルゴリズムは、明らかにそのエッジが見つかるとは限りません。

Answer 1

1. 3つ未満のエッジを持つすべての頂点のベクトルを作成します。
2. ランダムにベクトルから頂点を選択します。
3. 選択した頂点を削除したベクトルをコピーします（選択した頂点と最後の頂点を入れ替えてサイズを調整できます）。
4. すでに選択した頂点に接続しているすべてのターゲット頂点も削除します。
5. コピーベクターから頂点を選択し、2つの選択した間にN
6. 繰り返しステップ1..5限り未満3つのエッジを有するすべての頂点のベクトルを頂点各方向のエッジを作成する空でない