问题:给定一个无向图,使用邻接列表实现。我正在寻找一种算法,通过一个顶点删除将其转换为规则图(每个顶点具有相同的度数)。
例如:
迭代所有顶点,按度数对它们进行分区。
如果所有都具有相同的度数,则只有存在具有度数n - 1的顶点才有可能。
如果你可以将它们划分为2个不同的度数集:让我们用较低的度数调用X,用较高的度数调用Y.让我们调用dg(X)和dg(Y)这些顶点的程度
如果你可以分成3组:
任何其他情况,它是不可能的