与えられた数のノードとエッジを持つグラフを見つけるアルゴリズム

Question

私はいくつかのノードを持ち、各ノードにはいくつかのエッジがあります。例： ノードAには3つのエッジがあり、Bには2があり、Cには2があり、Dには1があります。2つのノード間に複数のエッジを持たない無向グラフを見つけるアルゴリズムを探しています。 この単純な例のために可能な解決策は、次のようになりますの

A 
    /|\ 
/| \ 
B--C D 

だからAは、それが3つの接続を持っているので、BはAとCに接続されている3つの他のノードと接続され、DはAと接続されている すべての辺すべてのノードが満足されなければならない。 別の例：

A（3）、B（3）、C（2）、D（1）、E（1）

溶液：

 A-----D  OR:  A-----E 
    /\     /\ 
/ \     / \ 
    C-----B-----E   C-----B-----D 

だから、時々あります複数のソリューション。しかし、解決策が存在しない場合よりも可能である。 A（2）、B（2）、C（1）

これらの3つのノードとそれらの与えられた辺の数でグラフを作成する方法はありません。

今、この問題の解決策を見つけるアルゴリズムを探しています。このような既知の問題は既に存在するのでしょうか？ 私は何らかの助けやヒントがあればうれしいです。

Answer 1

これはGraph Realization Problemとして知られています。

Erdős–Gallai theoremは、それが解決可能なときを決定するための簡単にコーディングされた基準を与え、Havel–Hakimi algorithmは、そのようなグラフを再構成する方法を与える。グラフ理論の私の好きな本の1つ、HarsfieldとRingelの "Graphs in Pearls in Graph Theory"は、Havel-Hakimiアルゴリズムの素敵な議論をしています。