离散数学考点之度序列简单图化 |
您所在的位置:网站首页 › 离散数学简单图定义 › 离散数学考点之度序列简单图化 |
离散数学考点序列的简单图化
如题2021年4月分析基础知识什么是度序列?什么是度序列可简单图化?
扩展知识什么是 Havel-Hakimi定理 ?验证答案B定理原理
积累下知识点。
如题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,就完全去掉了与最大度结点相连的结点连线。至于为什么是前几位的最大度,因为最大度只能与度最大度才可能相连. |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |