从度分布重建图

Question

给定学位分布，我们可以构建遵循给定度分布的图的速度？链接或算法草图将很好。该算法应报告一个“否”，如果可以构造多个图，则可以构建图形。

Answer 1

如果您是指如何构建这样的简单图（没有自我循环，没有平行的边缘），则可能是Havel-Hakimi定理。您可以自己谷歌和Wikipedia页面 程度（图理论） 也很有帮助。

Answer 2

如果给出学位分布列表，则可以执行以下操作，给定具有学位$ d_1的$ n $节点，...，...，d_n $：

在$ n $ vertices上创建一个完整的图形$ k_n $。对于$ k_n $中的每个顶点$ v_i $，将其分为$ d_i $副本。在这里分开表示，创建许多具有边缘的副本，每个顶点$ v_i $都有优势，但没有$ v_i $的其他副本。如果$ d_i = 0 $，则只需删除顶点即可。在新图中，以$ 1 leq j leq d_i $为$ v_ {ij} $调用这些顶点$ v_ {ij} $。

完成后，您将在$ n = d_1 + ... + d_n $ vertices上有一个非常密集的图；称此图$ H $。选择您喜欢的算法以进行最大匹配（由于图是如此密集，因此您可能应该使用基于快速矩阵的算法之一），并以$ h $进行运行。这将返回匹配的$ m $。如果匹配不是完美的（即，如果不能覆盖每个顶点），那么您的学位分配是不可能的；所以返回 不.

如果您有一个完美的匹配$ m $，请从$ h $中删除所有不在$ m $中的边缘，然后每$ 1 leq i leq n $合并$ d_i $ pertices $ v_ {i1}，。 ..，v_ {id_i} $ to一个顶点$ u_i $。合并两个顶点意味着将它们组合成一个，因此所得的顶点对每个顶点具有边缘至少一个原始的边缘。调用结果图$ g $;它具有所需的学位分布。

最终的运行时是$ O（n^ omega）$，其中$ omega $是最快的矩阵 - 杂质算法的常数（在写作时为$ 2.373 $）。就最终图中的顶点数量而言，在最坏的分布的情况下，我们有$ o（n^{2 omega}）$。