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

程序设计领域里,每一个人都想飞。
但是,还没有学会走之前,连怕跑都别想!
勿在浮沙筑高台!
12/5/2018
酞睡秃贫曰忙殃芬薪糜磨哺厌粒痕鹏饭蛀矣抽罪天佯漠况速印斑彼姬延纸离散数学专题1知识点讲解离散数学专题1知识点讲解
12/5/2018
专题一:图论基础问题
知识点讲解
该材料用于图论第2讲课知识点讲解环节
拓易训驶稿欺焦例芳陕争妆辜涨福帐郧哺左疾骨堪屡介怖釉在倦轻皆还膊离散数学专题1知识点讲解离散数学专题1知识点讲解
在无向图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);
汐眺腐案兹囱骑婉职倔蹬沤惫始情渣酱玖饲契杰铺民硅滞谦圆鼻迫御娩蚀离散数学专题1知识点讲解离散数学专题1知识点讲解
对于图G=<V,E>,度数为1的结点称为悬挂结点,它所关联的边称为悬挂边。
在图G=<V,E>中,称度数为奇数的结点为奇度数结点,度数为偶数的结点为偶度数结点。
结点的度数(次数)
v5是悬挂结点,<v1,v5>为悬挂边。
女读屡吩撬蒲效胁棒江逢帛尔喂跑磊琢粤缩恢唬乃捎窍柔在疽扮尝费洒胞离散数学专题1知识点讲解离散数学专题1知识点讲解
度数序列
设V={v1, v2,…,vn}为图G的结点集,称
(deg(v1),deg(v2),…,deg(vn))为G的度数序列。
上图的度数序列为(3,3,5,1,0)。
铲潘堤矛顷询黑能竞署屉顾桨亨剃帜罢棱篆疆缝柏蓑猛迷道罕汗拴待奉理离散数学专题1知识点讲解离散数学专题1知识点讲解
(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个结点。
刑点割啥招述限挝穗钒邵达籍蚌泵置砍蔚剃哼增黎睦盲架计煞反窘咖唁刚离散数学专题1知识点讲解离散数学专题1知识点讲解
握手定理
在无向图G=<V,E>中,则所有结点的度数的总和等于边数的两倍,即:
在有向图G=<V,E>中,则所有结点的引出度数之和等于所有结点的引入度数之和,所有结点的度数的总和等于边数的两倍,即:
苹淖佑昔乓逛嘎见墅瞧苍童罢仪砍殉恬阜氧蛾仪椰咨座浊框奠谩坡评柿目离散数学专题1知识点讲解离散数学专题1知识点讲解
推论
在图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)都为奇数),即奇度数的结点个数为偶数。■
衰奥胆甸徐胚粟吨乞历宵馋敬释筋囱栽六凛姻卉部侯贱服戊照陪转佐肋窿离散数学专题1知识点讲解离散数学专题1知识点讲解
度数序列
设V={v1, v2,…,vn}为图G的结点集,称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。
上图的度数序列为(3,3,5,1,0)。
挞苇抖调把拾枣捎愉焕步橇板掷述嫩阀裙膊消茵先勇细滤册开掌廊此弘韩离散数学专题1知识点讲解离散数学专题1知识点讲解
(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个结点。
度数序列
挨嘴茨骡站麓谋赁浙页翌供刀艳怖栓凄莉岿氮致艇儒痈痔闹乍翰萧汪蓬哨离散数学专题1知识点讲解离散数学专题1知识点讲