离散数学专题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知识点讲解