通过一次顶点删除创建正则图

Question

问题:给定一个使用邻接表实现的无向图。我正在寻找一种算法，通过一个顶点删除将其转换为规则图(每个顶点具有相同的度)。

例如：

​

​

Answer 1

迭代所有顶点，按其度数进行划分。

如果所有顶点的阶数都相同，则只有当存在阶数为n- 1的顶点时才有可能。

如果你能把它们分成两个不同的度集:让我们称X为低度集，Y为高度集。让我们称dg(X)和dg(Y)为这些顶点的阶数

如果其中一个分区只有1个顶点，并且其次数为0或者是另一个分区中顶点的数量，则将其删除。如果dg(Y) - dg(X) > 1，则不可能删除它，如果dg(Y) - dg(X) =1且|Y| = dg(X)，则检查X中的一个顶点是否与Y中的所有顶点相连并将其删除。

• if dg(Y) - dg(X) =1

• |X| = dg(Y)，检查Y中的顶点是否连接到X中的所有顶点，并将其移除。

• 2 partitions

不可能出现任何其他情况

如果你可以分成3组：

• 其中一个必须只有一个顶点，并且该顶点必须连接到另一个最高阶集的所有顶点，而不连接到剩余集的任何顶点。另一个最高度集和剩余集之间的度差也必须为1

任何其他情况，都是不可能的