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

程序设计领域里,每一个人都想飞。但是,还没有学会走之前,连怕跑都别想!勿在浮沙筑高台!*骆党雨寓仙暑获屿巢谷柞升司屏木诞唤播绳神霓孜袖制又徽馋堆朝闹刚奶离散数学专题1知识点讲解离散数学专题1知识点讲解*专题一:图论基础问题知识点讲解该材料用于图论第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知识点讲解