节点的度数课件.ppt

第第45讲讲 节点的度数节点的度数0节点的度数课件6.2 节点的度数节点的度数第第6章章 图论图论1节点的度数课件本讲内容无向图节点的度数无向图节点的度数1有向图节点的出度、入度有向图节点的出度、入度和和度数度数2握手定理握手定理3k- -正则图、最大正则图、最大( (小小) )度、度数序列度、度数序列42节点的度数课件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)图图, 且且2n – 3 = m, 求求n和和m各是多少各是多少? ¡Hint 根据握手定理有根据握手定理有:13节点的度数课件¡Def 6-9¡任意图任意图G = (V, E):¡有向图有向图G = (V, E):¡例子例子?14节点的度数课件¡对于无向图对于无向图G = (V, E), V = {v1, v2, …, vn},称称deg(v1), deg(v2), …, deg(vn)为的度数序列为的度数序列. 对对于有向图于有向图, 还可以定义其出度序列和入度序还可以定义其出度序列和入度序列列.¡例例6-3 是否存在一个无向图是否存在一个无向图G, 其度数序列分其度数序列分别为别为¡(1) 7, 5, 4, 2, 2, 1.¡(2) 4, 4, 3, 3, 2, 2.¡(度数序列与节点排列度数序列与节点排列 顺序关系不大顺序关系不大)15节点的度数课件¡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.16节点的度数课件¡Remark¡I. Δ(G)节点相当节点相当Hub节点节点: 鲁棒而脆弱鲁棒而脆弱.¡R.Albert, H.Jeong, A.L.Barabasi.¡The Internet’s 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?20节点的度数课件21节点的度数课件。