各ノードに最大次数が関連付けられている無向グラフを生成しようとしています。つまり、ノードの最大次数が 2 の場合、最大 2 つのノードに接続できます (接続されたノードは許可されますが、0 は許可されません)。私の問題は、あるノードから別のノードに移動できるグラフを生成しようとしていることです。現在、ノードを「ランダムに」互いに接続させることができますが、問題は、分割されたグラフを作成できることです。つまり、ノードが 10 個ある場合、うっかり 5 ノードずつ 2 つのグラフが形成されることがあります。誰かが効率的な解決策を知っているなら、私はそれを聞きたいです!
編集: 10 個のノードを持つグラフがあり、次数の最大値を 2 に指定するとします。この場合、望ましいものは次のとおりです。
これは私が避けようとしているものですが：
どちらのグラフもノードあたり最大次数は 2 ですが、2 番目のイメージでは、任意のノードを選択して他の任意のノードに到達することはできません。