查找具有给定节点数和边数的图的算法
Algorithm to find a graph with given number of nodes and edges
我有很多节点，每个节点都有很多边。
例如节点 A 有 3 条边，B 有 2 条边，C 有 2 条边，D 有 1 条边。我正在寻找一种算法，以找到两个节点之间没有多条边的可能无向图。
这个简单示例的可能解决方案是：
A
/|\
/ | \
B--C D
所以A与其他3个节点相连，因为它有3个连接，B与A和C相连，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 个节点及其给定的边数制作图。
现在，我正在寻找一种算法来为这个问题找到可能的解决方案。是否可能已经存在这样的已知问题？
我很乐意提供任何帮助或提示。
这被称为 Graph Realization Problem。
Erdős–Gallai theorem gives an easily-coded criterion for deciding when it is solvable and the Havel–Hakimi algorithm 给出了构造这种图的递归方法。我最喜欢的图论书籍之一，Harsfield 和 Ringel 合着的 "Pearls in Graph Theory" 对 Havel–Hakimi 算法进行了很好的讨论。
我有很多节点，每个节点都有很多边。 例如节点 A 有 3 条边，B 有 2 条边，C 有 2 条边，D 有 1 条边。我正在寻找一种算法，以找到两个节点之间没有多条边的可能无向图。 这个简单示例的可能解决方案是：
A
/|\
/ | \
B--C D
所以A与其他3个节点相连，因为它有3个连接，B与A和C相连，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 个节点及其给定的边数制作图。
现在，我正在寻找一种算法来为这个问题找到可能的解决方案。是否可能已经存在这样的已知问题？ 我很乐意提供任何帮助或提示。
这被称为 Graph Realization Problem。
Erdős–Gallai theorem gives an easily-coded criterion for deciding when it is solvable and the Havel–Hakimi algorithm 给出了构造这种图的递归方法。我最喜欢的图论书籍之一，Harsfield 和 Ringel 合着的 "Pearls in Graph Theory" 对 Havel–Hakimi 算法进行了很好的讨论。