图论及其应用(11)

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1 图论及其应用图论及其应用 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2本次课主要内容本次课主要内容(一一)、敏格尔定理、敏格尔定理(二二)、图的宽直径相关概念、图的宽直径相关概念图的宽直径简介图的宽直径简介(三三)、一些主要研究结果简介、一些主要研究结果简介 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 敏格尔定理是图的连通性问题的核心定理之一，它敏格

2、尔定理是图的连通性问题的核心定理之一，它是描述图的连通度与连通图中不同点对间的不相交路的是描述图的连通度与连通图中不同点对间的不相交路的数目之间的关系。数目之间的关系。(一一)、敏格尔定理、敏格尔定理 定义定义1 设设u与与v是图是图G的两个不同顶点，的两个不同顶点，S表示表示G的一个的一个顶点子集或边子集，如果顶点子集或边子集，如果u与与v不在不在G-S的同一分支上，的同一分支上，称称S分离分离u和和v。 例如：例如：u6u5u2u3u4u1 u1, u4, u1u2, u1u4, u4u5分离点分离点u2与与u6。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

3、 1 0.5 0 0.5 1 n 4 定理定理1(敏格尔敏格尔1902-1985) (1) 设设x与与y是图是图G中的两个中的两个不相邻点，则不相邻点，则G中分离点中分离点x与与y的最小点数等于独立的的最小点数等于独立的(x, y)路的最大数目；路的最大数目； (2)设设x与与y是图是图G中的两个不相邻点，则中的两个不相邻点，则G中分离点中分离点x与与y的最小边数等于的最小边数等于G中边不重的中边不重的(x, y)路的最大数目。路的最大数目。 例如：例如：u6u5u2u3u4u1 在该图中，独立的在该图中，独立的(u6 ,u2)路最大条数是路最大条数是2，分离点，分离点u6与与u2的最小分离集

4、是的最小分离集是u1, u4, 包含两个顶点。包含两个顶点。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5u6u5u2u3u4u1 又在该图中，边不重的又在该图中，边不重的(u6 ,u2)路最大条数是路最大条数是2，分离，分离点点u6与与u2的最小分离集是的最小分离集是u6u1, u6u4, 包含两条边。包含两条边。 该定理是图论中，也是通信理论中的最著名的定理之该定理是图论中，也是通信理论中的最著名的定理之一，是由奥地利杰出数学家一，是由奥地利杰出数学家Menger在在1927年发表的。年发表的。 敏格尔敏格尔(1902-19

5、85）早年显示出数学物理天赋，）早年显示出数学物理天赋，1920年入维也纳大学学习物理，次年，由于参加德国物理学家年入维也纳大学学习物理，次年，由于参加德国物理学家Hans Hahn的的“曲线概念的新意曲线概念的新意”讲座，而把兴趣转向了讲座，而把兴趣转向了数学。因为数学。因为Hans提到当时没有满意的曲线概念定义，包括提到当时没有满意的曲线概念定义，包括大数学家康托、约当，豪斯道夫等都尝试过，没有成功。大数学家康托、约当，豪斯道夫等都尝试过，没有成功。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6而且，认为不可能彻底解决。但是

6、，尽管作为几乎没有数而且，认为不可能彻底解决。但是，尽管作为几乎没有数学背景的本科生，通过自己的努力，敏格尔还是解决了该学背景的本科生，通过自己的努力，敏格尔还是解决了该问题。由此，他就转向曲线和维数理论的研究。问题。由此，他就转向曲线和维数理论的研究。 敏格尔本科期间，身体很差，父母双亡。但在敏格尔本科期间，身体很差，父母双亡。但在1924年年在在Hahn指导下完成了他的研究工作。指导下完成了他的研究工作。1927年做了维也纳年做了维也纳大学几何学首席教授，同年，发表了大学几何学首席教授，同年，发表了“n弧定理弧定理”，即，即敏格尔定理。敏格尔定理。 1930年，敏格尔来到匈牙利布达佩斯做访

7、问，当时哥年，敏格尔来到匈牙利布达佩斯做访问，当时哥尼正在写一本书，要囊括图论中的所有知名定理。敏格尔尼正在写一本书，要囊括图论中的所有知名定理。敏格尔向他推荐自己的定理，但哥尼最初不相信他，认为敏格尔向他推荐自己的定理，但哥尼最初不相信他，认为敏格尔定理一定不对，花了一个晚上找反例试图否定敏格尔定理，定理一定不对，花了一个晚上找反例试图否定敏格尔定理，但没有成功，于是要了敏格尔的证明，终于把敏格尔定理但没有成功，于是要了敏格尔的证明，终于把敏格尔定理加在了他的著作的最后一节。加在了他的著作的最后一节。 敏格尔被认为是敏格尔被认为是20世纪最杰出数学家之一。世纪最杰出数学家之一。 0.8 1

8、0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 哈恩哈恩 (18791968 ) 德国物理学家，化学家。最大的贡德国物理学家，化学家。最大的贡献是献是1938年和年和F.斯特拉斯曼一起发现核裂变现象。哈恩获斯特拉斯曼一起发现核裂变现象。哈恩获得得1944年诺贝尔化学奖年诺贝尔化学奖 。 借助于敏格尔定理，数学家惠特尼在借助于敏格尔定理，数学家惠特尼在1932年的博士论年的博士论文中给出了文中给出了k连通图的一个美妙刻画。这就是人们熟知的连通图的一个美妙刻画。这就是人们熟知的所谓所谓“敏格尔定理敏格尔定理” 定理定理2 (惠特尼惠特尼1932)

9、 一个非平凡的图一个非平凡的图G是是k (k2)2)连通的，连通的，当且仅当当且仅当G G的任意两个顶点间至少存在的任意两个顶点间至少存在k k条内点不交的条内点不交的(u ,v)(u ,v)路。路。 证明证明: (必要性必要性) 设设G是是k (k2)2)连通的，连通的，u u与与v v是是G G的两个的两个顶点顶点 。 如果如果u与与v不相邻，不相邻，U为为G的最小的最小u-v分离集分离集,那么有那么有|U|k(G)k,k(G)k,于是由敏格尔定理，结论成立；于是由敏格尔定理，结论成立； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1

10、 n 8 若若u与与v邻接，其中邻接，其中e=uv,那么，容易证明：那么，容易证明：G-e是是(k-1)连通的。设连通的。设W是是G-e的最小的最小uv分离集，由敏格尔定理知，分离集，由敏格尔定理知，G-e至少包含至少包含k-1条内点不交的条内点不交的u-v路，即路，即G至少包含至少包含k条内条内点不交的点不交的u-v路。路。 (充分性充分性) 假设假设G中任意两个顶点间至少存在中任意两个顶点间至少存在k条内部不条内部不交路。设交路。设U是是G的最小顶点割，即的最小顶点割，即|U|=k (G)。令。令x与与y是是G-U的处于不同分支的两个点。所以的处于不同分支的两个点。所以U是是x与与y的分离

11、集，由敏的分离集，由敏格尔定理：格尔定理： |U|k,k,即证明即证明G G是是k k连通的。连通的。 例例1 设设G是是k连通图，连通图，S是由是由G中任意中任意k个顶点构成的集个顶点构成的集合。若图合。若图H是由是由G通过添加一个新点通过添加一个新点w以及连接以及连接w到到S中所中所有顶点得到的新图，求证：有顶点得到的新图，求证：H是是k连通的。连通的。 证明：首先，分离证明：首先，分离G中两个不相邻顶点至少要中两个不相邻顶点至少要k个，其个，其次，分离次，分离w与与G中不在中不在S中顶点需要中顶点需要k个顶点。因此个顶点。因此H是是k连连通的。通的。 0.8 1 0.6 0.4 0.2

12、0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 例例2 设设G是是k连通图，连通图，u , v1,v2,vk为为G中中k+1个不同顶点。个不同顶点。求证：求证：G中有中有k条内点不交路条内点不交路(u ,vi) (1ik)ik) 证明：在证明：在G外添加一点外添加一点w,让让w与与vi邻接邻接(1ik)得得H.Gv1uv2vkHv1uv2vkw 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 由例由例1，H是是k连通的，于是由定理连通的，于是由定理2，u与与w间存在间存在k条条内点不交的内点不交的u-

13、w路，所以路，所以 G中有中有k条内点不交路条内点不交路(u ,vi) (1ik)。 对于边连通度，有类似定理：对于边连通度，有类似定理： 定理定理3 (惠特尼惠特尼1932) 一个非平凡的图一个非平凡的图G是是k (k2)2)边连边连通的，当且仅当通的，当且仅当G G的任意两个顶点间至少存在的任意两个顶点间至少存在k k条边不重的条边不重的(u ,v)(u ,v)路。路。 推论推论 对于一个阶至少为对于一个阶至少为3的图的图G，下面三个命题等价。，下面三个命题等价。 (1) G是是2连通的；连通的； (2) G中任意两点位于同一个圈上；中任意两点位于同一个圈上； (3) G无孤立点，且任意两

14、条边在同一个圈上。无孤立点，且任意两条边在同一个圈上。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 证明：证明：(1)(2) G是是2连通的连通的,则则G的任意两个顶点间存在两条内点不交的任意两个顶点间存在两条内点不交路路P1与与P2,显然这两条路构成包含该两个顶点的圈。显然这两条路构成包含该两个顶点的圈。 G无孤立点显然。设无孤立点显然。设e1与与e2是是G的任意两条边，在的任意两条边，在e1与与e2上上分别添加两点分别添加两点u与与v得图得图H，则，则H是是2连通的，由连通的，由(1)(2)，H的的任意两个顶点在同一个圈

15、上，即任意两个顶点在同一个圈上，即u与与v在同一个圈上，也即在同一个圈上，也即e1与与e2在同一个圈上。在同一个圈上。 (2)(3) (3)(1) 设设u u与与v v是是G G的任意两个不相邻顶点，由于的任意两个不相邻顶点，由于G G无孤立点，所无孤立点，所以可设以可设e e1 1,e,e2 2分别与分别与u, vu, v相关联。由相关联。由(3),e(3),e1 1,e,e2 2在同一个圈在同一个圈上，所以上，所以u u与与v v在同一个圈上，因此分离在同一个圈上，因此分离u u与与v v至少要去掉两至少要去掉两个顶点，即证明个顶点，即证明G G是是2 2连通的。连通的。 0.8 1 0.

16、6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12(二二)、图的宽直径相关概念、图的宽直径相关概念 1、问题背景、问题背景 分析评价互联网络的性能有多个指标，如网络的开销分析评价互联网络的性能有多个指标，如网络的开销(通信与材料开销通信与材料开销), 网络的容错性网络的容错性(连通性连通性), 网络中信息传网络中信息传递的传输延迟等。递的传输延迟等。 所谓传输延迟，又称为时间延迟，是指信息从源传到所谓传输延迟，又称为时间延迟，是指信息从源传到目的地所需要的时间。目的地所需要的时间。 如何度量网络的传输延迟？如何度量网络的传输延迟？ 信息从源到目的地

17、需要经过若干中间站存储和转发。信息从源到目的地需要经过若干中间站存储和转发。因此，信息传输延迟可以用图的顶点间距离来度量。当然，因此，信息传输延迟可以用图的顶点间距离来度量。当然，每条边的长度可以定义为每条边的长度可以定义为1. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 于是，网络的最大通信延迟可以通过图的直径来度量。于是，网络的最大通信延迟可以通过图的直径来度量。图的直径定义为：图的直径定义为：( )max( , ) ,( )d Gd u v u vV G 在信息的单路径传输中，分析通信延迟，只需要考虑在信息的单路径传输

18、中，分析通信延迟，只需要考虑网络的直径即可。图论工作者、计算机、通信领域研究者网络的直径即可。图论工作者、计算机、通信领域研究者通过研究，已经确定了若干典型网络的直径和一些图的直通过研究，已经确定了若干典型网络的直径和一些图的直径的界。径的界。 例如：例如：d(Pn)=n-1 ; d(Cn)=n/2; d(Kn)=1。 定理定理1 设设G是强连通有向图是强连通有向图.如果它的阶如果它的阶n22且最大度且最大度为为，则：，则：1,1( )log ( (1) 1)1,2nd Gn 若若 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14

19、11,22( )(2)2log,3nd Gn 若若 定理定理2 设设G是连通无向图是连通无向图.如果它的阶如果它的阶n33且最大度为且最大度为 2 ，则：，则： 定理定理3 设设G是连通无向图是连通无向图.如果它的阶如果它的阶n，且最小度为且最小度为，则：则：3( )1nd G 定理定理4 设设G是连通无向图是连通无向图.如果它的阶如果它的阶n，直径为直径为k k，则：，则：1( )(4)(1)2E Gknknk 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 定理定理5 n级超立方体网络的直径为级超立方体网络的直径为n 直径虽

20、然能够刻画网络的通信延迟，但毕竟是在最坏直径虽然能够刻画网络的通信延迟，但毕竟是在最坏情形下的通信延迟，而网络中大距离点对并不多，所以用情形下的通信延迟，而网络中大距离点对并不多，所以用直径对信息传输延迟进行描述，还有点不精细。于是，有直径对信息传输延迟进行描述，还有点不精细。于是，有如下平均距离的概念：如下平均距离的概念：,()1( )( , )(1)u v V GGd u vn n 设设G是是n阶图阶图(n2)2)，G G的平均距离的平均距离(G)(G)定义为：定义为： 例：计算例：计算n点圈点圈Cn的平均距离。的平均距离。 解：首先计算解：首先计算n点圈点圈Cn中任意一点中任意一点u到其

21、余各点的距离到其余各点的距离之和：之和：1+2+,+(n-1)=n(n-1); 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16n点圈点圈Cn中所有点对的距离之和：中所有点对的距离之和：n2(n-1);所以，所以，n点圈点圈Cn的平均距离为：的平均距离为： (G)= n 平均距离是网络信息平均传输延迟的度量。跟直径研平均距离是网络信息平均传输延迟的度量。跟直径研究一样，平均距离问题也吸引很多学者的研究，有很多研究一样，平均距离问题也吸引很多学者的研究，有很多研究结果。例如：究结果。例如： 定理定理6 如果如果G是是n阶连通的无向图

22、，则：阶连通的无向图，则：( )21nG 定理定理7 如果如果G是是(n，m)图，则：图，则： (1) 如果如果G是无向图，则：是无向图，则：,()( )( , )2 (1)2u v V GGd u vn nm 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 (2) 如果如果G是有向图，则：是有向图，则：,()( )( , )2 (1)u v V GGd u vn nm 注：定理注：定理7的结论是由的结论是由Slater和和Ng等得到的。等得到的。2004年中年中国科技大学少年班学生周涛利用国科技大学少年班学生周涛利用Ore定理

23、给出了巧妙的证定理给出了巧妙的证明，文献是：明，文献是： Zhou T, Xu J-M, Li J. On diameter and average distanceOf graphs. 运筹学报，运筹学报，8 (4) (2004),33-38 求平均距离的一个值得研究的方向是求平均距离算法求平均距离的一个值得研究的方向是求平均距离算法复杂性。求平均距离的最著名的复杂性。求平均距离的最著名的Fredman算法时间复杂性算法时间复杂性是是o(v2+vm);求直径最著名算法是求直径最著名算法是Floyd算法，时间复杂性算法，时间复杂性是是o (v m).确定平均距离问题是否比确定所有距离容易？确定

24、平均距离问题是否比确定所有距离容易？这还是一个没有完结的挑战性问题。这还是一个没有完结的挑战性问题。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 信息的单路径传输延迟用直径或平均距离刻画。但是，信息的单路径传输延迟用直径或平均距离刻画。但是，如果要一次传输的信息量较大，远远超出链路带宽，就需如果要一次传输的信息量较大，远远超出链路带宽，就需要所谓的分包传送。要所谓的分包传送。 所谓的分包传送，就是按照带宽要求，把信息在起点进所谓的分包传送，就是按照带宽要求，把信息在起点进行分割打包，每个信息小包按照若干内点不交路从起点传行分

25、割打包，每个信息小包按照若干内点不交路从起点传到终点。基于此，上世纪到终点。基于此，上世纪90年代初，年代初，D Frank等图论学者等图论学者和一些计算机专家从图论角度对信息分包传送的若干问题和一些计算机专家从图论角度对信息分包传送的若干问题展开研究。研究的典型问题是：展开研究。研究的典型问题是： (1) 分包传送的通信延迟度量；分包传送的通信延迟度量； (2) 分包传送的路由选择，即网络中平行寻径算法；分包传送的路由选择，即网络中平行寻径算法； (3) 互联网络的设计与网络结构分析问题；互联网络的设计与网络结构分析问题； (4) 基于分包传送下互联网络的容错分析。基于分包传送下互联网络的容

26、错分析。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 为了描述通信延迟，为了描述通信延迟，D Frank等拓展了图的普通距离和等拓展了图的普通距离和普通直径的概念，提出了用宽距离来描述点对间信息传递普通直径的概念，提出了用宽距离来描述点对间信息传递的通信延迟，而用所谓的宽直径来描述网络的最大通信延的通信延迟，而用所谓的宽直径来描述网络的最大通信延迟。由此而形成的组合网络理论研究成为最近迟。由此而形成的组合网络理论研究成为最近10多年来图多年来图论和通信网络相结合的热点研究问题。论和通信网络相结合的热点研究问题。 国内，中国科

27、技大学以徐俊明为代表的研究团队取得国内，中国科技大学以徐俊明为代表的研究团队取得了很多重要成果，在该领域处于世界领先水平，出版了专了很多重要成果，在该领域处于世界领先水平，出版了专著著组合网络理论组合网络理论，科学出版社，科学出版社，2007年。年。 2、宽直径相关概念、宽直径相关概念 定义定义1 设设x, y V(G), C w (x, y)表示表示G中中w条内点不交路的条内点不交路的路族，路族，w称为路族的宽度，称为路族的宽度， C w (x, y)中最长路的路长成为该中最长路的路长成为该路族的长度，记为：路族的长度，记为：l (C w (x, y)。 0.8 1 0.6 0.4 0.2

28、0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 在上图中，在上图中，G的一个宽度为的一个宽度为3的的u, v间的路族为：间的路族为：uv图图GP3P2P13123( , ),C u vP P P 该路族的长度为：该路族的长度为：33( , )()4l C u vl P 注：路族也称为容器。注：路族也称为容器。 定义定义2 设设x, y V(G), 定义定义x与与y间所有宽度为间所有宽度为w的路族长度的路族长度的最小值的最小值d w( x , y)为为x与与y间间w宽距离，即：宽距离，即：( , )min( , ):( , )wwwdx yl Cu vCu v 0.

29、8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 在上图中，在上图中，G的一个宽度为的一个宽度为3的的u, v间的距离为：间的距离为：uv图图GP3P2P1 注：注：x与与y间长度等于间长度等于w宽距离的路族称为宽距离的路族称为x与与y间最优路族。间最优路族。所以，求所以，求w宽距离，就是要找到最优路族。宽距离，就是要找到最优路族。 定义定义3 设设G是是w连通的，连通的，G的所有点对间的的所有点对间的w宽距离的最大宽距离的最大值，称为值，称为G的的w宽直径，记为宽直径，记为d w (G)。即：。即：333( , )min( , ):

30、( , )3d u vl C u vC u v( )max( , ): ,( )wdGd x yx yV G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 例例3 求求n点圈点圈Cn和和n阶完全图阶完全图Kn的宽直径。的宽直径。 分析：对于分析：对于Cn来说，连通度为来说，连通度为2，因此，可以求它的，因此，可以求它的1直径直径和和2直径；而对于直径；而对于Kn来说，连通度是来说，连通度是n-1,所以，可以考虑它的所以，可以考虑它的1到到n-1直径。直径。 解解: (1) n点圈点圈Cn的宽直径。的宽直径。 显然：显然：1()

31、2nndC 因为因为C n中任意点对间只有一个唯一的宽度为中任意点对间只有一个唯一的宽度为2的路族，点的路族，点对间的对间的2距离就是该点对的唯一路族的长度。当距离就是该点对的唯一路族的长度。当x与与y邻接时，邻接时，路族的长度最长，为路族的长度最长，为n-1,所以，由宽直径定义得：所以，由宽直径定义得：2()1ndCn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 (2) kn的宽直径。的宽直径。 显然：显然：1()1ndK 对于任意的对于任意的w(2wn-1),wn-1),点对间的最优路族长为点对间的最优路族长为2.2.所

32、以，所以，有：有：()2(21)wndKwn 注：从定义看出：对一般图来说，计算注：从定义看出：对一般图来说，计算w宽直径是一件很宽直径是一件很困难的工作。对宽直径的研究，主要是两方面：一是对一般困难的工作。对宽直径的研究，主要是两方面：一是对一般图而言，研究图而言，研究w宽直径的界；二是根据各种互联网络的结构特宽直径的界；二是根据各种互联网络的结构特征，确定其宽直径。当然，研究宽直径与图的其它不变量之征，确定其宽直径。当然，研究宽直径与图的其它不变量之间的关系也是一个很有意义的方向。间的关系也是一个很有意义的方向。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

33、1 0.5 0 0.5 1 n 24 经过经过10多年的研究，组合网络理论取得了很多有意义结果，多年的研究，组合网络理论取得了很多有意义结果，同时也有许多公开性问题等待人们继续研究。同时也有许多公开性问题等待人们继续研究。(三三)、一些主要研究结果简介、一些主要研究结果简介 1、 一般图的一般图的w宽直径宽直径 定理定理1 对于任意连通图对于任意连通图G,有：有：12()()()()wd GdGdGdG 定理定理2 设设G是是n阶阶w连通图连通图, w 22。则。则: :2()1wdGnw 而且，上界和下界都能达到。而且，上界和下界都能达到。 0.8 1 0.6 0.4 0.2 0 x t 0

34、 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25 定理定理3 设设G是是n阶阶w连通图连通图, w 22，G G 满足如下条件：满足如下条件：( )()1,()GGdxdynwx yV G 那么，那么，dw(G)=2, 并且上面条件是紧的。并且上面条件是紧的。 定理定理4 设设G是是w连通连通w正则图正则图, w 22，那么：，那么：()()1wdGd G 定理定理5 设设G是是n阶阶w连通连通w正则无向图正则无向图, w 33，那么：，那么：1()2wdGn 2、 图运算与图运算与w宽直径宽直径 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0

35、.5 0 0.5 1 n 26 定理定理1 设设Gi是是wi连通有向图连通有向图, 且：且： ，1iim.如果如果 ,那么：那么： 注：该结果是由徐俊明得到的。注：该结果是由徐俊明得到的。1()m ax()1;()();1immwjjwiijidGdGdGdGim()()iwirGdG12,mGGGG 定理定理2 (1) 设设Gi是阶至少为是阶至少为3的的wi连通无向图连通无向图, i=1, 2, , m。如果如果 ，且，且w=w1+w2+wm，则：，则：12,mGGGG()m ax()();1imwjwijidGdGdGim 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1

36、.5 2 1 0.5 0 0.5 1 n 27 注：该结果是由徐俊明得到的。注：该结果是由徐俊明得到的。 (2) 设设G是是w22连通无向图连通无向图.如果如果d w(G)=d(G)+1,则：则：12()()2wdKGd G (3) 设设Gi是是wi11连通无向图连通无向图, i=1,2。如果。如果Gi是是wi正则的，正则的，且且i=1或或2，则：，则：1212()()2wwidGGd G 3、 图参数与图参数与w宽直径宽直径 图论中，对图参数进行研究时，一个自然的研究是考察研图论中，对图参数进行研究时，一个自然的研究是考察研究的参数与其它参数之间的关系。因为很多图参数的计算是究的参数与其它参

37、数之间的关系。因为很多图参数的计算是NP完全问题，如果建立了参数之间的联系，可以间接计算。完全问题，如果建立了参数之间的联系，可以间接计算。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 定理定理1 设设G是是w连通无向图连通无向图, w2,2,且且(G)(G)是是G G的独立数。的独立数。则则()2 ()wdGG 4、 w宽直径与容错直径宽直径与容错直径 容错直径的概念是由容错直径的概念是由Krishnamoorthy等在等在1987年提出的，年提出的，它是度量容错网络的最大通信延迟的量。即一个网络它是度量容错网络的最大通信

38、延迟的量。即一个网络G,如果如果F是它的一个容错顶点集合，则是它的一个容错顶点集合，则G-F是连通的，它有一个确定直是连通的，它有一个确定直径，容错直径就是基于这样的背景提出的。径，容错直径就是基于这样的背景提出的。 定义定义1 设设G是是w连通无向图连通无向图, 则对则对V(G)的任意子集的任意子集F，如果，如果有有|F|w, 定义定义G的的w-1容错直径容错直径Dw(G)为：为：()max()(),wDGd GFFV GFw 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 从容错直径的定义可以看出，计算图的容错直径跟宽直从容

39、错直径的定义可以看出，计算图的容错直径跟宽直径一样，非常困难，事实上，是径一样，非常困难，事实上，是NP完全问题。因此，对容完全问题。因此，对容错直径的研究，自然转移到对容错直径和宽直径之间的关错直径的研究，自然转移到对容错直径和宽直径之间的关系进行研究。系进行研究。 定理定理1 设设G是是w连通无向图连通无向图, w2,2,则有：则有：()()wwDGdG 定理定理2 设设G是直径为是直径为d的的2连通图，则：连通图，则：2221()max(1)11,12dGdDdD 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 30 定理定理3

40、 设设G是是2连通无向图连通无向图, 则有：则有：2221,2;()(1)(1),3DddGdDd若若 定理定理4 设设G是直径为是直径为2的的2连通图，则：连通图，则：d2=D2+1的充分必的充分必要条件为要条件为d2=3或或d2=4,且达到且达到d2值的任何两点必然邻接。值的任何两点必然邻接。 注：关于容错直径和宽直径的关系研究文章不是很多，注：关于容错直径和宽直径的关系研究文章不是很多，主要是徐俊明发表的文章。主要是徐俊明发表的文章。 5、 典型网络的典型网络的w宽直径宽直径 经过近经过近20年的研究，已经确定出很多著名网络的容错直年的研究，已经确定出很多著名网络的容错直径与宽直径，下面

41、做总结性介绍。径与宽直径，下面做总结性介绍。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31 (1) 超立方体网络超立方体网络Qn()nk Qn()nd Qn,1()()1,.wnwnnwndQDQnwn若若 (2) de Brujin 有向网络有向网络B (d , n) (d2, n12, n1）(,)1k B d nd(,)d B d nn( ,)( ,)1,1wwdB d nDB d nnwd若 (3) Kautz 有向网络有向网络K (d , n) (d2, n12, n1）(,)k K d nd(,)d K d nn

42、0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 321,2( ,)2,1wnwddK d nnwdd若若或1,1,2;( , )( , )2,3wwnwdwdnDK d ndK d nnwdn若或且若或 (4) de Brujin 无向网络无向网络UB (d , n) (d2, n12, n1）(,)22k UB d nd(,)d UB d nn1( ,)1ddUB d nn22(2, )(2, )D UBnd UBnn (5) 无向超环面无向超环面C (d1,d2 , dm) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3312(,)2mk C dddm 令令G = C (d1,d2 , dm)1211(,)2mmiid C dddd2132232452()1,2;2()2,2;()()2,9;()2,913;()1,wwmddd GGCCwd GGCCwdGd GGCCdd GGCCdd G若若若若其他。 (6) 有向超环面有向超环面12(,)mC ddd 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 341()(1)()1nniidCdd C 如果如果d1=d2=dn=