离散数学考点序列的简单图化
积累下知识点。
如题2021年4月
分析
之前从没遇到过的知识点。
基础知识
什么是度序列？
若把图G所有顶点的度数排成一个序列，则称该序列为图G的一个序列
什么是度序列可简单图化？
给定一个非负整数序列{d1,d2,…dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。
简单说，就是给出了每个结点的度，知道这些能否做题了呢？
和度相关的判断就两个：
-
每个结点的度，最大度数为n-1
-
奇顶点必有偶数个。
-
握手定理，所有顶点的度数之和等于边的两倍（换言之，所有顶点度数之和一定为偶数）
给出答案:
A：一共有5个顶点，但度数为5，显然不符
D：也是一样，4个顶点，最大度数为4，显然也不行
C：三个度为3的顶点，又不能有重边或环，只有完全图可以达到这个要求。但最后一个顶点度为1，画不出这样的图。
所以，答案只能是B.
扩展知识
什么是 Havel-Hakimi定理 ？
在非递增序列下判别是否可图的定理 。
由非负整数组成的有限非递增序列，S={d1,d2,d3…dn}，当且仅当S1={d2-1,d3-1…d(d1+1),d(d1+2)…dn}也是可图的，也就是说，序列S1也是由非负整数组成的有限非递增序列，S1是由S的删除第一个元素d1之后的前d1个元素分别减一后得到的序列。
验证答案B
{3,3,2,2,1,1}这个序列：
-
按降序排列，本身就是非递增，所以直接删去最大元素3，把前3个元素减1，变成{2，1，1，1，1}
-
再删去最大元素2，把前2个元素减1，变成{0，0，1，1}，此时不再是非递增了，需要重新排序了{1，1，0，0}
-
删去最大元素1，把剩下元素前1个元素减1，变成{0，0，0}
没有出现负数，所以此数据是可以简单图化的。
定理原理
删去最大的度结点，相当于去掉了一个结点，所以f去掉的度数是多少后面相应的几个度减1，就完全去掉了与最大度结点相连的结点连线。至于为什么是前几位的最大度，因为最大度只能与度最大度才可能相连.