1、节点的度数幻灯片 本课件本课件PPT仅供大家学习使用仅供大家学习使用 学习完请自行删除，谢谢！学习完请自行删除，谢谢！本课件本课件PPT仅供大家学习使用仅供大家学习使用 学习完请自行删除，谢谢！学习完请自行删除，谢谢！本课件本课件PPT仅供大家学习使用仅供大家学习使用 学习完请自行删除，谢谢！学习完请自行删除，谢谢！本课件本课件PPT仅供大家学习使用仅供大家学习使用 学习完请自行删除，谢谢！学习完请自行删除，谢谢！6.2 节点的度数第6章 图论本讲内容无向图节点的度数无向图节点的度数1有向图节点的出度、入度有向图节点的出度、入度和和度数度数2握手定理握手定理3k-正则图、最大正则图、最大(小小
2、)度、度数序列度、度数序列46.2 节点的度数从一个地方出发的桥的数目就是对应节点的度数.边与节点的关联次数?Def 设G=(V,E)是无向图,v V,称与节点v关联的所有边的关联次数之和为节点v的度数(degree),记为deg(v).一个环算2度?1v2v3v.3)deg(,5)deg(,2)deg(321vvv2e1e3e4e5eDef 设G=(V,E)是有向图,v V:deg+(v)=od(v);deg-(v)=id(v);deg(v)=od(v)+id(v).一个环算2度?1v2v3v4v下面的定理是L.Euler在1736年证明的图论中的第一定理,常称为“握手(?)定理.Theor
3、em 6-1 在任何(n,m)图G=(V,E)中,其所有节点度数之和等于边数m的2倍,即.2)deg(mvVvCorollary 在任意图G=(V,E)中,度数为奇数的节点个数必为偶数.Proof.)deg()deg()deg(2)deg()deg(奇数偶数vvVvvvvm由定理及其推论很容易知道,在任何一次聚会上,所有人握手次数之和必为偶数并且握了奇数次手的人数必为偶数.(环的解释?)在任意有向图中,显然有Theorem 6-2 在任意有向图中,所有节点的出度之和等于入度之和.在任意图中,度数为0的节点称为孤立点(isolated vertex),度数为1的节点称为悬挂点(pendant v
4、ertex).1v2v3v4v5v6v7v例6-1 证明:对于任意n(n2)个人的组里,必有两个人有一样个数的朋友.Proof 将组里的每个人看作节点,两个人是朋友当且仅当对应的节点邻接,于是得到一个n阶简单无向图G,进而G中每节点的度数可能为0,1,2,n-1中一个.当G中无孤立点时,于是每节点的度数可能为1,2,n-1.由于共有n个节点,于是必有两节点度数一样.当G中有孤立点时,这时每节点的度数只可能为0,1,2,n-2.同样由于共n有个节点,因此必有两节点度数一样.假设一个Simple无向图G的每节点度数均为k,那么称G为k-正那么图(k-regular graph).例6-2 设无向图
5、G是一个3-正那么(n,m)图,且2n 3=m,求n和m各是多少?Hint 根据握手定理有:.23mn.32mn9,6mnDef 6-9任意图G=(V,E):有向图G=(V,E):例子?),deg(max)(vGVv).deg(min)(vGVv),(degmax)(vGVv),(degmax)(vGVv),(degmin)(vGVv).(degmin)(vGVv对于无向图G=(V,E),V=v1,v2,vn,称deg(v1),deg(v2),deg(vn)为的度数序列.对于有向图,还可以定义其出度序列和入度序列.例6-3 是否存在一个无向图G,其度数序列分别为(1)7,5,4,2,2,1.(
6、2)4,4,3,3,2,2.(度数序列与节点排列 顺序关系不大)Solution(1)由于序列7,5,4,2,2,1中,奇数个数为奇数.根据握手定理的推论知,不可能存在一个图其度数序列为7,5,4,2,2,1.(2)因为序列4,4,3,3,2,2中,奇数个数为偶数,可以得到一个无向图(见图7-11),其度数序列为4,4,3,3,2,2.RemarkI.(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.II.度数序列分布.A.L.Barabasi,R.Albert et al.Power-law distribution of the World Wide Web.Science ,2000,287:130-131.)32()(kkP小结与作业无向图节点的度数无向图节点的度数有向图节点的出度、入度和度数有向图节点的出度、入度和度数握手定理握手定理k-正则图、最大正则图、最大(小小)度、度数序列度、度数序列习题习题6.2 2,3,7,9(选选)作业作业Any Questions?
