离散数学中如何判断一个数列是不是无向简单图的度数列
展开全部
这是一个很经典的问题。
这个问题叫“graph realization”问题,解决的算法叫“Havel Hakimi”算法。
你可以搜索上面那2个英文,其实算法很简单,几句话就能说清楚。
首先,将度数从大到小排序:
关键是下面这个定理(当然这个定理需要证明,这里略):
原度数序列能构成图,当且仅当将度数最大的点 v1,与除 v1 外度数最大的 d1 个点分别连一条边后,剩下的度数序列能构成图。也就是:
能构成图,当且仅当:
能构成图。
这样就把 n 个顶点的问题,转化为 n-1 个顶点的问题。
如此做下去,可以继续转化为 n-2、n-3、……个顶点的问题。
如果能构成图,最后的结果是个全零的向量。除此之外,都是不能构成图的,比如某一步时:某个度数为负、或是 d1 的值大于剩余顶点的个数,等等。。。
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询