离散数学中如何判断一个数列是不是无向简单图的度数列

Question

离散数学中如何判断一个数列是不是无向简单图的度数列

Answer 1

这是一个很经典的问题。

这个问题叫“graph realization”问题，解决的算法叫“Havel Hakimi”算法。

你可以搜索上面那2个英文，其实算法很简单，几句话就能说清楚。

首先，将度数从大到小排序：

关键是下面这个定理（当然这个定理需要证明，这里略）：

原度数序列能构成图，当且仅当将度数最大的点 v1，与除 v1 外度数最大的 d1 个点分别连一条边后，剩下的度数序列能构成图。也就是：

 能构成图，当且仅当：

 

能构成图。

这样就把 n 个顶点的问题，转化为 n-1 个顶点的问题。

如此做下去，可以继续转化为 n-2、n-3、……个顶点的问题。

如果能构成图，最后的结果是个全零的向量。除此之外，都是不能构成图的，比如某一步时：某个度数为负、或是 d1 的值大于剩余顶点的个数，等等。。。