离散数学专题知识点讲解.ppt

离散数学专题知识点讲解
第一页，共21页
*
专题一：图论基础问题
知识点讲解
该材料用于图论第2讲课知识点讲解环节
第二页，共21页
在无向图G＝<V，E>中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；
结点的度数 （次数）
在有向图G＝<V，E>中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)＝deg+(v)+deg-(v)；
第三页，共21页
对于图G＝<V，E>，度数为1的结点称为悬挂结点，它所关联的边称为悬挂边。
在图G＝<V，E>中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。
结点的度数 （次数）
v5是悬挂结点，<v1，v5>为悬挂边。
第四页，共21页
度数序列
设V＝{v1, v2,…,vn}为图G的结点集，称
(deg(v1),deg(v2),…,deg(vn))为G的度数序列。
上图的度数序列为（3,3,5,1,0）。
第五页，共21页
（3,3,2,3），（5,2,3,1,4）能成为图的度数序列吗？为什么？
已知图G中有10条边，4个度数为3的结点，其余结点的度数均小于等于2，问G中至少有多少个结点？为什么？
度数序列
解　1）由于这两个序列中，度数为奇数的结点个数均为奇数，由握手定理的推论知，它们都不能成为图的度数序列。
2）图中边数为10，由握手定理知，G中所有结点的度数之和为20，4个度数为3的结点占去12度，还剩下8度。若其余全是度数为2的结点，还需要4个结点来占用这8度，所以G至少有8个结点。
第六页，共21页
握手定理
在无向图G＝<V，E>中，则所有结点的度数的总和等于边数的两倍，即：
在有向图G＝<V，E>中，则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：
第七页，共21页
推论
在图G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝
{e1，e2，……，em}，度数为奇数的结点个数为偶数。
证明设V1＝{v|vV且deg(v)＝奇数}，V2＝{v|vV且deg(v)＝偶数}。显然，V1∩V2＝Φ，且V1∪V2＝V，于是有：
由于上式中的2m和(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。■
第八页，共21页
度数序列
设V＝{v1, v2,…,vn}为图G的结点集，称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。
上图的度数序列为（3,3,5,1,0）。
第九页，共21页
（3,3,2,3），（5,2,3,1,4）能成为图的度数序列吗？为什么？
已知图G中有10条边，4个度数为3的结点，其余结点的度数均小于等于2，问G中至少有多少个结点？为什么？
解　1）由于这两个序列中，度数为奇数的结点个数均为奇数，由握手定理的推论知，它们都不能成为图的度数序列。
2）图中边数为10，由握手定理知，G中所有结点的度数之和为20，4个度数为3的结点占去12度，还剩下8度。若其余全是度数为2的结点，还需要4个结点来占用这8度，所以G至少有8个结点。
度数序列
第十页，共21页