第45讲-节点的度数.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,6.2,节点的度数,第,6,章 图论,1,本讲内容,无向图节点的度数,1,有向图节点的出度、入度,和,度数,2,握手定理,3,k,-,正则图、最大,(,小,),度、度数序列,4,2,6.2,节点的度数,从一个地方出发的桥的数目就是对应节点的度数,.,边与节点的,关联次数,?,3,Def,设,G,=(,V,E,),是无向图,v,V,称与节点,v,关联的所有边的关联次数之和为节点,v,的,度数,(degree),记为,deg(,v,).,一个环算,2,度,?,4,Def,设,G,=(,V,E,),是有向图,v,V,:,deg,+,(,v,)=,od(,v,),;,deg,-,(,v,)=,id(,v,),;,deg,(,v,),=od(,v,)+id(,v,).,一个环算,2,度,?,5,下面的定理是,L.Euler,在,1736,年证明的图论中的第一定理,常称为“握手,(?),定理”,.,Theorem 6-1,在任何,(,n,m,),图,G,=(,V,E,),中,其所有节点度数之和等于边数,m,的,2,倍,即,6,Corollary,在任意图,G,=(,V,E,),中,度数为奇数的节点个数必为偶数,.,Proof,7,由定理及其推论很容易知道,在任何一次聚会上,所有人握手次数之和必为偶数并且握了奇数次手的人数必为偶数,.(,环的解释,?),在任意有向图中,显然有,Theorem 6-2,在任意有向图中,所有节点的出度之和等于入度之和,.,8,在任意图中,度数为,0,的节点称为,孤立点,(isolated vertex),度数为,1,的节点称为悬挂点,(pendant vertex).,9,例,6-1,证明,:,对于任意,n,(,n,2,),个人的组里,必有两个人有相同个数的朋友,.,Proof,将组里的每个人看作节点,两个人是朋友当且仅当对应的节点邻接,于是得到一个,n,阶,简单,无向图,G,进而,G,中每节点的度数可能为,0,1,2,n,-1,中一个,.,10,当,G,中无孤立点时,于是每节点的度数可能为,1,2,n,-1.,由于共有,n,个节点,于是必有两节点度数相同,.,当,G,中有孤立点时,这时每节点的度数只可能为,0,1,2,n,-2.,同样由于共,n,有个节点,因此必有两节点度数相同,.,11,若一个,Simple,无向图,G,的每节点度数均为,k,则称,G,为,k,-,正则图,(,k,-regular graph).,12,例,6-2,设无向图,G,是一个,3-,正则,(,n,m,),图,且,2,n,3=,m,求,n,和,m,各是多少,?,Hint,根据握手定理有,:,13,Def 6-9,任意图,G,=(,V,E,):,有向图,G,=(,V,E,):,例子,?,14,对于无向图,G,=(,V,E,),V,=,v,1,v,2,v,n,称,deg(,v,1,),deg(,v,2,),deg(,v,n,),为的度数序列,.,对于有向图,还可以定义其出度序列和入度序列,.,例,6-3,是否存在一个无向图,G,其度数序列分别为,(1)7,5,4,2,2,1.,(2)4,4,3,3,2,2.,(,度数序列与节点排列,顺序关系不大,),15,Solution(1),由于序列,7,5,42,2,1,中,奇数个数为奇数,.,根据握手定理的推论知,不可能存在一个图其度数序列为,7,5,4,2,2,1.,(2),因为序列,4,4,3,3,2,2,中,奇数个数为偶数,可以得到一个无向图,(,见图,7-11),其度数序列为,4,4,3,3,2,2.,16,Remark,I.,(,G,),节点相当,Hub,节点,:,鲁棒而脆弱,.,R.Albert,H.Jeong,A.L.Barabasi.,The Internets Achilles heel:Error and attack tolerance of complex networks,.,Nature ,2000,406:378-382.,17,II.,度数序列,分布,.,A.L.Barabasi,R.Albert et al.,Power-law distribution of the World Wide Web,.,Science ,2000,287:130-131.,18,小结与作业,无向图节点的度数,有向图节点的出度、入度和度数,握手定理,k,-,正则图、最大,(,小,),度、度数序列,习题,6.2 2,3,7,9(,选,),作业,19,Any Questions,?,Thank You!,