Question

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

Answer 1

这个问题叫“graphrealization”问题，解决的算法叫“HavelHakimi”算法。

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

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

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

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

扩展资料：

数列的函数理解：

①数列是一种特殊的函数。其特殊性主要表现在其定义域和值域上。数列可以看作一个定义域为正整数集N*或其有限子集{1，2，3，…，n}的函数，其中的{1，2，3，…，n}不能省略。

②用函数的观点认识数列是重要的思想方法，一般情况下函数有三种表示方法，数列也不例外，通常也有三种表示方法：a.列表法；b。图像法；c.解析法。其中解析法包括以通项公式给出数列和以递推公式给出数列。

③函数不一定有解析式，同样数列也并非都有通项公式。

Answer 2

这个问题叫“graphrealization”问题，解决的算法叫“HavelHakimi”算法。

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

这样就把n个顶点的问题，转化为n-1个顶点的问题。如此做下去，可以继续转化为n-2、n-3、……个顶点的问题。如果能构成图，最后的结果是个全零的向量。除此之外，都是不能构成图的，比如某一步时：某个度数为负、或是d1的值大于剩余顶点的个数，等等。

性质

讨论的图不但与节点位置无关，而且与边的形状和长短也无关。

若有一条边连一个图的某两个节点，则称这两个节点相邻，并称这两个节点为这条边的端点；若某一节点是某一条边的端点，则称这个节点和这条边关联；若两条边和同一节点关联，则称这两条边相邻；两个端点是同一个节点的边称为环。

以上内容参考：百度百科-简单图

Answer 3

首先要求所有数(度)之和是偶数，其次判断是否为简单图，方法：依次删去度最大的点，递归下去，最后可确定是否是简单图。

追问

删掉最大的度的点后其他的点是否也要减一？例如：1，2，4，3，3，5怎么判断？

追答

当然要减1，对这个例子：
1. 和是偶数
2. 降序排列：5，4，3，3，2，1
3. 删去5，剩下的序列中前5个分别减1，得到3，2，2，1（删去0）
依次下去。。。。

最后，首位变为0，可以判定是简单图的度序列。如果最后得到的不是0（如2，0)，则不是简单图的度序列。