早教吧 育儿知识 作业答案 考试题库 百科 知识分享

顶点度序列为(d1,d2,...,dn),d1+d2+...+dn为偶数,证明该度序列必有对应的一般图,构造一个算法求该图

题目详情
顶点度序列为(d1,d2,...,dn),d1+d2+...+dn为偶数,证明该度序列必有对应的一般图,构造一个算法求该图
▼优质解答
答案和解析

显然若存在这样的图,则必有n个节点

对于图中的任意一条边,它对左端点形成出度,对右端点形成入度,所以一条边形成两个度,所以所有点的度之和必为偶数.

构造算法:

将所有点置于集合中

取出集合中任意两个度不为0的点,在它们之间连一条边,并将它们的度都减一

重复2直到集合中所有点度数均为0