（应用数学专业论文）组合网络理论中一些问题的研究.pdf

摘要 本文讨论互连网络拓扑结构分析中的几个问题全文共分三部分，第一部分 主要介绍一些图论以及互连网络理论的基础知识，为后面两个部分的叙述和证明 中所涉及的内容的相关背景以及名词、符号做出必要的说明 第二部分介绍我的主要工作，即强乘积图的一些基本性质和强乘积图的连通 度强乘积是一种重要的构图方法，本文先给出了一些强乘积图的基本性质，给 出了强乘积图的连通图的主要结果和证明 尤( g l 囟g 2 ) m i n k 1 ( 如+ 1 ) ，k 2 ( 西+ 1 ) ) 第三部分是我协助徐敏师姐做的一些工作，主要是对循环网络中的路由转发 指数的研究循环网络是一种非常常见的网络结构，其中的路由转发指数是非常 _ _ _ _ - _ _ 一 重要的一个性能参数 a b s t r a c t t h ed i s s e r t a t i o ns h o w ss o n l es t u d i e so nt o p o l o g i c a ls tr u c t u r ea n da n a l y s i s o fi n t e r c o n n e c t i o nn e t w o r k s i tc o n t a i nt h r e ep a r t sa sf o l l o w ： t h ef i r s tp a r tg i v e ss o m eb a s i cb a c k g r o u n d ，d i f i n a t i o n sa n ds y m b o l so ft h e f o l l o w i n gp r o o f t h es e c o n dp a r ti n t r o d u c e sm ym a i nw o r ko nt h ec o n n e c t i v i t yo fs t r o n gp r o d u c tg r a p ha n dg i v et h er e s u l ta sf o l l o w ： 一( g l 园g 2 ) m i n k l ( 如+ 1 ) ，( 巧l + 1 ) ) t h et h i r dp a r ti sa b o u ts o m ew o r kw i t hd r x um i no nt h er o u t i n gf o r w a r d i n g i n d e xo fc i r c u l a n tn e t w o r k s c i r c u l a n tn e t w o r k s ev e r yf a m o u sn e t w o r k sa n d r o u t i n gf o r w a r d i n gi n d e xi sav e r yi m p o r t a n tp r o p e r t yi nn e t w o r k s ， 第一章图论和互连网络概念介绍 1 1 图论 图论是一新的数学分支，也是一门很有实际价值的学科，它在自然科学、社 会科学等各领域均有很多应用近年来它受计算机科学蓬勃发展的刺激，发展极 其迅速应用范围不断拓广，已渗透到诸如语言学、逻辑学、物理学、化学、电讯 工程、计算机科学以及数学的其他分支中特别在计算机科学中。如形式语言、 数据结构、分布式系统、操作系统等方面军扮演着重要的角色f 15 现实世界的很多事伪用图形来描写可能是方便的，这种图形是由一个点集以 及这个点集中的某些点对的连线构成的例如，点可以表示人，连线表示一对朋 友；或者，用点表示通讯站，而连线表示通讯线路，注意，在这类图形中，人们主 要感兴趣的是给定两点是否有一根线连接，而连接的方式则无关紧要这类事例 的数学抽象就产生了图的概念 4 】 1 1 1 图的定义 一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，抛) ，其中v ( g ) 是非空的顶点 集，e ( c ) 是不与v ( g ) 相交的边集，而4 是关联函数，它使g 中每条边对应 于g 的无序点对( 不必相异) 若e 是条边，而“和v 是使得币g ( e ) = u u 的 顶点，则称e 连接u 和”；顶点“和”称为e 的端点【4 】 下面是一个图的例子这个图就是1 7 3 6 年欧拉发表的第一篇讨论图论的论 文中所研究的著名的哥尼斯堡七桥问题的图【1 0 】，其中 g = ( 、，( g ) ，e ( g ) ，惦) v ( c ) = l ，啦，啦，w 4 ) e ( g ) = ( e 1 ，d 2 ，e 3 ，e 4 ，e 5 ，e 6 ，e 7 ) 妒g 定义为 1 2中国科学技术大学硕士学位论文 妒g ( e 1 ) = 0 1 u 2 ，母g ( e 2 ) = u i u 2 砂g ( e a ) = v 2 7 ) 3 ，妒g ( e 4 ) = v 2 y 3 砂g ( e 5 ) = y 17 j 4 ，妒g ( e 6 ) = v 2 v 4 妒g ( 8 7 ) = u 3 l 4 图1 h 哥尼斯堡七桥问题的图 设图g 是无向图x v ( a ) 的顶点度定义为g 中与z 关联的边的数目( 一 条环要计算两次) ，记为d g ( z ) 来表示图g 中顶点z 的顶点度，使用d ( g ) 来表 示图g 中顶点度最小的点的度数，使用a ( a ) 来表示图g 中顶点度最大的点的 度数 例如在上图中，我们有d g ( 1 ) = 3 ，d e ( v 2 ) = 5 ，6 ( g ) = 3 ，( g ) = 5 1 2 互连网络 我们这里所说的互连网络是泛指各种组件，如计算机、计算机内部的处理器、 存储器、通信设备、其它元件或设备等的集合以及通讯信道的集合按一定的点对 点方式相互连接所形成的系统网络中组件和组件之间的连接方式称为该网络的 拓扑结构在分析网络拓扑结构时，人们通常把网络中组件抽象成一个点，把通 信信道抽象成两点之间的连线，那么该网络的拓扑结构就被抽象成一个图研究 l2 互连阿络 3 网络的拓扑结构问题就归结为研究图的结构问题换句话说，图是网络结构的数 学模型，我们可以通过图论方法来研究网络的拓扑结构，如不加特殊说明，本文 所涉及的图均为有限简单图 互连网络理论在实际科学研究和生活中应用非常广泛，从目前如火如茶的i n t e r n e t 到各种电子芯片和超级计算机，从全国铁路公路建设到列车班次的安排， 都和互连网络理论有着密不可分的关系 互连网络理论研究的内容非常多，包括网络的连通度、边连通度、网络的直 径、网络的宽直径、网络的转发指数、网络的限制连通度、网络的限制边连通度、 如何通过一些较小的网络构造一个较大的网络，在网络中一些节点或者边出现故 障的时候幸存网络的性质等等 l 2 1 连通度的定义 如果对于一个图的每一对不同的顶点 墨f ) ，都存在从z 到y 的路，则称该 图是连通的，否则就是不连通的f 5 j 设z 和y 是图d 中不同的两顶点，p 是d 中从z 到y 的有向路集若 p 中任意两条只和b 均有y ( 只) ny ( b ) = z ，订，则称p 是d 中内部点不 交的( i n t e r n a lv e r t e x - d i s j o i n t ) ( z ，y ) 路集；若p 中任意两条只和b 均有 e ( 只) ne ( b ) = d ，则称尸是d 中边不交的( i n t e r n a le d g e - d i s j o i n t ) ( z ，y ) 路 集我们用( d ( z ，y ) 和加( z ，y ) 分别来表示d 中内部点不交和边不交的( x ，y ) 路 的最大条数f 1 8 】 上述定义是针对有向图的情况，对于无向图的情况可以完全一样定义 设g 是连通图，非空集scy ( g ) 若g s 是非连通的，则称s 是g 的 分离集显然，若g 中不含支撑子图托、，则g 必有分离集我们定义 们，屯凇黝。器季詈麓 中国科学技术大学硕士学位论文 为g 的连通度若一( g ) 女，则称g 为k 连通的 1 8 j 设g 是连通图，非空集bce ( g ) 若g b 是非连通的，则称b 是g 的 截边集我们定义 一k 伸黝，o ；冀嚣域利隧黜； 为g 的边连通度若x ( c ) 女，则称g 为k 边连通的【1 8 若图的连通度为，则表明对应的互联网络可以容许一1 个结点同时发生故 障而不会导致剩余子网络中各结点之间的通信同样地，若图的边连通度为k ，则 表明对应的互联阿络可以容许一1 条信息传输信道同时发生故障而不会导致剩 余子网络中各结点之间的通信因此，连通度被视为互联网络可靠性和容错性的 重要度量 关于有向的强连通图和连通的无向图的连通度、边连通度、内点不交的路的 最大条数、边不交的路的最大条数以及最小点度的关系，在图论历史上很早就有 研究，早在上个世纪二三十年代，m e n g e r 和w h i t n e y 就已经得到了如下几个非 常重要的定理 定理( w h i t n e y1 19 1 ) 对任何图g ，k ( d ) sn 功墨6 ( d ) 定理( m e n g e r 1 9 1 ) 设图g 是一个连通的无向图或者强连通的有向图，。和 是g 中不同两顶点，则 ( 1 ) ( g ；z ，y ) = a ( g ；z ，y ) ； ( 2 ) e ( g ；z ，) = k ( g ；z ，) 如果( z ，y ) 隹e ( g ) 定理( w h i t n e y 1 9 ) 设w 1 ，并设g 是至少k + 1 阶的图，则 ( 1 ) k ( d ) w 甘( ( g ；茁，y ) 三，v z ，y v ( c ) ； ( 2 ) a ( g ) w 甘叩( g ；z ，y ) w ，v z ，y y ( g ) 上述三个定理，无论其中的图是无向图还是有向图，都是适用的，只需将相 应地方的记号换成有向图或者无向图即可 12 互连网络 5 三个定理是互连网络理论对连通度和刚络流理论的研究中，最为基口钗口 镜亩这些定理揭示了连通度、边连通度、内点不交的路的最大条数、边不交的 路的最大条数以及最小点度的关系，从根本上刻画了连通度的实际含义这三个 定理频繁的出现在关于连通度和网络流等相关定理证明中 1 2 2点转发指数和边转发指数 路由选择是互连网络的最主要功能，路由选择是否合适深刻影响网络的性能 和效率因此，路由选择是网络设计时要考虑的重要问题在点对点的互连网络 中，每个结点都装有路由选择器在目前的以t c p i p 为基础的i n t e r n e t 中，也 存在着大量的路由器，将信息从一个结点传向另一个结点一个信息从源结点到 目的结点，要经过若干中间结点以形成传输路径，该信息每到一个结点都要经过 存储、排队等待，然后经过路由选择器进行路由选择再转发到下一个结点通常 去往目的结点的路径不止一条，如何选择最优路径；当最优路径负载过重造成拥 塞甚至发生故障时，又如何从其他备用路径中选择一条，这些都是互连网络中很 重要的问题，也是目前i n t e r n e t 中路由器面临的非常实际的问题下面我们将给 出路由选择的图论的定义 设g 是强连通有向图或者连通的无向图，v = y ( g ) 令 a = v y ( z ，z ) ：z y ) 设z 和y 是g 中不同两顶点，p g ( y ) 是g 中( z ，y ) 路r ( z ，y ) 的集合令 尸( g ) = u p g ( 置) ，v e v ( c ) ，z 图g 中路由选择定义为映射 r ：a ( z ，y ) 一p ( g ) ， 一r ( x ，y ) 既然路由选择是互连网络的主要功能，路由选择的优劣直接影响网络的性能， 在设计计算机互连网络的同时要在不增加硬件和软件支持的条件下设计一个供信 6中国科学技术大学硕士学位论文 息传输的最佳或最优的路由选择是非常重要的，那什么才叫最佳或最优，评估路 由选择最佳或最优的参数是什么? 当然，影响路由选择的优劣的因素有很多，除 了要有一个有效的路由选择算法外，人们根据网络应用的实际背景提出许多度量 路由选择优劣的参数这些参数导致许多值得深入研究的图论概念 设g 是一个n 阶的连通无向图或强连通有向图r 是g 的一个路由选择 若_ r 中每条路径r ( x ，y ) 都是g 中最短( z ，y ) 路，则称r 为最小路由选择或最短 路由选择，记为一般地，r ( y ，z ) 冗( 毛们，即使是无向图也可能是这样如 果r 中每条路径均有r ( u ，z ) = r ( z 口) ，则称r 为双向由路选择同样，对于每 个兄( z ，y ) 中的内点：，r ( z ，y ) 也不一定是冠( z ，z ) 十n ( z ，酊如果对每对顶点， 上式都成立的话，则称r 是一致的 对于一个给定的路由选择r ，它的路径r ( x ，y ) 承担着将结点z 的信患直接 传输到结点y 的任务如果凡( $ ，y ) 不是边( z ，) ，则结点z 的信息传输到结点y 要经过r ( z ，y ) 的一系列中间结点的转发才到结点y 一个给定了路由选择j r 的 网络或图g 记为( g ，r ) 由路由选择r 确定的网络g 中n ( n 一1 ) 条路径都要 承担数据传输任务，如果这些路径经过某个结点的条数过多，即经过该结点转发 的数据量过大，势必影响网络的通讯效率；或者超过该点的控制容量造成信息拥 塞，甚至导致整个网络的瘫痪 很显然，一个好的路由不应该过多次地经过某个结点，于是c h u n g 、c o f f - m a i l 、r e i m a n 和s i m o n 于1 9 8 7 年在文献 6 】中提出一个度量路由选择优劣的 参数t 点转发指数， 设g 是一个图，凡是给定的路由选择对于g 中的点z 关于j r 的点转发 指数( g ，r ，。) 定义为由r 确定的路径经过x ( 即点2 7 作为中间点) 的条数具 体如下 ( g ，r ) = m a x ( a ，r ，z ) ：x y ( g ) ) 为路由选择r 在图g 中的点转发指数；分别定义 ( g ) = m i n ( g ，r ) ：v r ) 和矗( g ) = m i n ( g ，h ) ：vr m ) 1 1 2 互连网络 7 为g 的点转发指数和最小路由选择点转发指数 类似地，h e y d e m a n n 、m e y e r 和s o t t , e a u 于1 9 8 9 年在文献 1 2 中提出了路 由选择兄的边转发指数的概念 设g 是一个图，r 是给定的路由选择对于g 中的边e 关于r 的边转发指 数( g ，r ，e ) 定义为由r 确定的路径经过边e 的条数具体如下 7 r ( g ，r ) = m a x ”( g ，r ，e ) ：e e ( g ) ) 为路由选择兄在图g 中的边转发指数；分别定义 ( g ) = m i n l r ( g ，r ) ：vr ) 和。( g ) = m i n n ( g ，凡。) ：vr r 。) 为g 的边转发指数和最小路由选择边转发指数 显然，( g ) 矗( g ) ，”( g ) ”。( g ) 然而，等号不是一直成立的 与点转发指数一样，一个好的路由选择和好的网络也都应具有小的边转发指 数，或者边转发指数不超过网络各条边的负载量路由选择的边转发指数是受网 络负载量控割，因此边转发指数也是度量路由选择优劣的一个重要参数 1 2 2 1 点转发指数 关于点转发指数的一般性结论并不多，对于一般的图，已经有下述结果： 定理( c h u n g 等f 6 1 ) 设g 是n 阶连通图，v = 矿( g ) ，则 ：( d c ( x ，v ) 一1 ) s ( g ) 岛( g ) ( n 1 ) ( n 一2 ) g e vz ( y 等式( g ) 2 岛( g ) 2 i 蚱矿。( ”) e y ( d g ( z ，”) 一1 ) 成立铮存在最小路由选择 r 。使得它对任何点的转发指数都相等， 在文献 1 6 1 中m a n o u s s a k i s 和t u z a 证明了上述结论对于强连通的有向图也 是成立的 上面定理中给出的上界是可以达到的，例如星图k l 。_ i 事实上，星图是唯 一使得上面定理中上界可以达到的图 8 中国科学技术大学硕士学位论文 在上面定理中上界等号成立的充分必要条件已经很清楚而h e y d e r n a n n 等也 已经证明，对于一类特殊的图一c a y l e y 图，下界等号也是成立的 定理( h e y d e m a n n 等 1 1 ( 1 2 ) 设g 是n 阶( 强) 连通c a y l e y 图，则对任意 z y ( g ) ，有 ( g ) = 。( g ) = d a ( x ，) 一( n 1 ) y e v ( g ) 1 2 2 2 边转发指数 相应于点转发指数，关于边转发指数也有同样的讨论 l i 嗍( h e y d e m a n n 等 1 2 1 ) 设g 是n 阶连通无向图，v = y ( g ) ，e = e ( g ) ，e = 俐，则等式”( g ) = ( g ) = ；。y d g ( z ，9 ) 成立甘存在最小路 由选择尼。使得它对任何边的转发指数都相等 对于有向图也有类似的结论 定1 e ( m a n o u s s a k i s 和r i 、l z a 1 6 1 ) 设d 是n 阶强连通有向图，v = y ( d ) ，e = e ( d ) ，= i e i ，则 i 1 d d ( z ，) ”( d ) s ( d ) ( n 1 ) ( n 一2 ) 十l - y e v 等式n ( d ) = ( d ) = ；。v d d ( z ，掣) 成立甘存在最小路由选择使得它 对任何有向边的转发指数都相等 结果 很可惜，对于c a y l e y 图的边转发指数，文献中没有得到类似于点转发指数的 第二章强乘积图的一些基本性质 随着计算机和网络的飞速发展，超级计算机的处理器数量越来越多，网络上 的计算机数也越来越大，如何使得超级计算机在处理器数量增加的时候保持其性 能的良好增长以及如何使得网络在规模增大的时候性能也更好，成为当前网络拓 扑结构研究热点内容图的乘积这种构图法正是在这种背景下产生的一种用于构 造较。大”的图的方法，专门构造具有各种优良基本性质的、性能优异的网络 2 1 乘积图的介绍 在实际网络设计当中，为了得到更大的图，我们通常会使用几个较小的图的乘 积来得到一个较大的图这种构图方法这些乘积方法包括笛卡儿乘积( 0 a r t e s i a n p r o d u c t ) 、直接乘移酲c a t e g o r i c a lp r o d u c t ) 、字典乘积( l e x i c o g r a p h i cp r o d u c t ) 、 强乘积( s t r o n gp r o d u c t ) 等等使用各种不同的乘积方式得到的不同的新的网 络具有各自的特点，本文所要讨论的强乘积正是其中一种构图法 我们先介绍一下这几种不同的乘积构图法 2 1 1 笛卡儿乘积囝 笛卡儿乘积图g = g 1 口g 2 ，图g 的点集是g 1 的点集和g 2 的点集的 笛卡儿乘积u ，图g 中两点“= ( n ，? 2 ) 和1 1 = ( ，也) 在图g 中相邻， 当且仅当u 1 = 1 1 l 并且”2 和1 1 2 相邻，或者l 和1 1 1 相邻并且u 2 = 其中 ? 1 ，u l g 1 ，u 2 ， 2 g 2 【1 0 2 1 2 直接乘积图 直接乘积图g = g lx 岛，图g 的点集是g 1 的点集m 和g j 的点集m 的 笛卡尔乘积u 埏，图g 中两点i s = 托，u z ) 和”= ( 2 j 1 ，”z ) 在图g 中相邻，当 且仅当u l 和 l 相邻并且u 2 和 2 相邻，其中? 1 ，1 1 1 g 1 ，u 2 ， 2 g 2 7 】 9 中国科学技术大学硕士学位论文 2 1 3 字典乘积图 字典乘积图g = g 1 g 2 ，图g 的点集是g 。的点集和g 2 的点集k 的笛 卡尔乘积u v 2 ，图g 中两点u = ( u l ，u 2 ) 和u = ( 地v 2 ) 在图g 中相邻，当且 仅当札1 和u 1 相邻或者“l = u 1 并且“2 和”2 相邻，其中u 1 ， 1 g 1 ，2 ，y 2 g 2 【1 4 卜 2 1 4 强乘积图 强乘积图g g 1 囟g 2 ，图g 的点集是g 1 的点集和g 2 的点集也的 笛卡尔乘积，图g 中两点u = ( u ，“2 ) 和”= ( u - ，u 2 ) 在图g 中相邻， 当且仅当如= ”1 并且也和地相邻，或者l 和v 1 相邻并且地= 啦，其中 u 1 ，v l g l ，u 2 ，v 2 g 2 1 7 ， 强乘积是一种常见的构图方法，特别适合用来构造边数非常多的、具备有其 他良好陛质的图在通过强乘积这种构图法构造新的图的过程中，我们称作为“乘 数”和“被乘数5 的两个图为“原图”，“积9 这个图为“强乘积图” 强乘积的运用和研究非常广泛 1 3 【3 1 3 【1 】【2 】，例如在通讯网络中著名的香农 容量( s h a n n o nc a p a c i t y ) ，图的独立数的研究，图的色数的研究等等，对于强乘 积图的连通j 陛的研究以前并没有很好的结果，仅能通过两个图的笛卡儿图是这两 个图强乘积图的子图，我们才得以通过笛卡儿乘积图的一些性质来确定强乘积图 的一些上下界，但这样得结果显然是很不能令人满意的由于连通度和独立数、 色数等都存在一定的关系。丽强乘积图在这些方面又是应用很广，因此对强乘积 图的连通度的研究非常有意义，也很有价值 2 2 强乘积图的一些基本性质 在研究强乘积图的连通性之前，首先，我们对强乘积图的一些基本性质做一 些研究，这些研究结果将作为研究强乘积图连通度的基础 2 2 强乘积图的一些基本性质 ( a ) 强乘积图的顶点个数为原来两个图顶点个数的乘积 ( g 】因g 2 ) = u ( g 1 ) 十v ( g 2 ) ( a ) 强乘积图的顶点的度 d g 6 妇：( z 可) = d v ，( z ) d c ：( 刭) + d a ，扛) 十d g ：0 ) ( c ) 强乘积图的最大点度 a c l 日吼( 茁v ) = a c 。( z ) a e 2 ( y ) 十g ，( 动十g 2 ( 掣) ( d ) 强乘积图的最小点度 如。a j ( 毛( z p ) = 6 口。( z ) 6 g 2 ( y ) + 6 g ，( z ) + 如( g ) ( e ) 强乘积图的直径强乘积图的直径为原来两个图直径的较大值 d ( g 1 园g 2 ) = m a x ( d ( g 1 ) ，d ( g 2 ) ) 证明： 我们证明个更强的引理比1 ，y l g 1 ；x 2 ，轨g 2 d ( g 1 园g 2 ；z l z 2 ，y x y 2 ) = m a x ( d ( g a ；z l ，u 1 ) ，d ( g 2 ；x 2 ；啦) ) 首先，我们证明强乘积图中，任何两点的距离，不小于原图中作为乘数和被 乘数的对应两点距离的较大值，即忱1 ，y i g l ；z 2 ，y 2 g 2 d ( g 1 因g 2 ；工l z 2 ，v 1 现) m a x ( d ( g 1 ；x l ，备1 ) ，d ( g 2 ；x 2 ；阮) ) 设d ( g 1 因g 2 ；t i x 2 ，y l y 2 ) = n ，则在图g 1 园g 2 中存在一条从连接点x l z 2 和 们抛的长为n 的路，记为 r = ( x l ：z 2 。s o o ，8 1 t 1 1 ，s n t n = y l y 2 ) 1 2 中国科学技术大学硕士学位论文 考虑强乘积图中关于两点是否相邻的基本性质，即图g = g - 因g 2 中两点 = ( 虮、地) 和u = ( 虮，u 2 ) 在图g 中相邻，当且仅当n l 和w 1 相邻并且“2 = f 或者u l = u 1 并且让2 和y 2 相邻，其中u h u l g 1 ，u 2 ，u 2 g 2 因此我们可以知道对于点序列( s o ，蜘，s 。) 具有= s ：+ 或者5 ，和s ：+ ， 相邻这样的性质，其中j = 1 ，2 ，一，n 一1 因此，我们可以在点序列( s o ，3 圹，) 中找到一条连接点z l = 8 0 和点y = s 。的路，p m = ( s 。s 。，s 。) ，其中序 列中连续的两点在图g 1 中相邻，序列( e 1 ，e 2 ，e 。) 是序列( 1 ，2 ，n ) 的一 个子序列，因此易知m 要t l ，也就是说，d ( g 1 函g 西奶铂，轨v 2 ) d ( g 1 ；q ，饥) 同理，我们可以通过点序列( t o ，t l ，k ) ，在图g 2 中找到一条长度不大于 的，连接点z 2 = t d 和点y 2 = 。的路，从而得到d ( g l 囟g 2 ；孔现，y l y 2 ) 2 d ( g 2 ；x 2 ，驰) 这样，我们结合两个不等式，就有 d ( c l 因g 2 ；z l z 2 ，g l 擘2 ) m a x ( d ( g t ；七l ，可1 ) ，d ( g 2 ；茁2 ；9 2 ) ) 然后我们再来证明 d ( g 1 囟g 2 ；3 ：1 2 ；2 ，执抛) m a x ( d ( c 1 ；z l ，舶) ，d ( c 2 ；z 2 ；啦) ) 假设 d ( g l ；z l ，y t ) = m d ( g z ；z 2 ，妇) = n 并且 m “ 那么，我们可以分男假设t 在点z z 和9 1 之间存在一条长为m 的路，记为 p m = ( x l = s o ，8 1 ，s t n = 们) 在点z 2 和2 之闻存在一条长为m 的路，记为 p n = ( x 2 = t o ，h - ，t 。= 妇) 5 2 2 强乘积图的一些基本性质 1 3 在图g ，园g 2 中考虑点对 以及点对 s 山 和 s l t j + 1 2 = i ，2 ， 1 ；j = l ，2 ，r，n 一1 s 2 “和s i + lg j + li = 1 2 ，m 一1 订= 1 ，2 ，n l 由于根据强乘积图的定义，由于点s ：和点s 在图g 。中是相邻的，以及点 t j 和点t j + l 在图g 2 中是相邻的，易知点s i t j 和5 ，什1 以及点s 而和5 + l 在 图g 1 囟g 2 中都是相邻的 我们使用这些点对在图g 。因g 2 中构造一个点对的序列，这个序列的首尾顶 点是点x l y l 和点z 2 讹，如下： p n = ( s o t o ，s l 1 ，一，s m t m t s m m + 1 ，s m t n ) 显然这是一条连接点。1 y 1 和点x 2 y 2 的路，且长度为n ，因此我们有 d ( g l 囟g 2 ；x l x 2 ，玑伽) m a x ( d ( g l ；x l ，y i ) ，d ( c 2 ；z 2 ；) ) 综上所述，结合两个不等式，我们得到 因此 d ( g 1 因g 2 ；。1 2 2 ，口l 协) = m a x ( d ( g 1 ；z 1 ，y 1 ) ，d ( g 2 ；x 2 ；y 2 ) ) d ( g l 因g 2 ) = 。廖，g r f l ，m a x ，妇g ：( d ( g l 因c 2 ；z l z 2 ，y 1 啦) ) 2 g f f m l a , x ：g 。( “( d ( g 1 ；奶，y 1 ) ，d ( g 2 ；x 2 i y 2 ) ) ) 2 “删：器，( 8 ( g ，m ，) x 。嬲( d ( g 2 ；口t ) ) )、。l ，m g 1 。、“z 2 ，! ，2 e 岛、“7 = m “( d ( g 1 ) ，d ( g 2 ) ) ( f ) 强乘积图的边数和原来两个图边数的关系如下 e ( g 1 因g 2 ) = 2 e ( c 1 ) e ( c 2 ) + e ( c 1 ) v ( a 2 ) + e ( g 2 ) ( g 1 ) 中国科学技术大学硕士学位论文 由于任何一条边都连接两个顶点，我们有 d ( z ) = 2 e ( g ) z g 因此 2 e ( g 1 园c 2 ) = d c ，园g 2 ( z ) z 0 g l g 2 = d 。，园g 2 ) z g 1w e g j = ( d g 。( z ) + d a ：( ) + d g ，( z ) + d g 2 ( y ) ) z e g lv g 2 = ( d o ，( z ) t d e 2 ( y ) ) m g 1y 6 g 2 + d g ，( 茁) + 屯( ) z 6 g 1y e g 2z 6 g , y e g s = d g 。( z ) + d g 。( y ) z e g l”g 2 + d c 。( z ) + d g 2 ( y ) 口g 2 e g lz 6 g iy e g 2 = ( 2 e ( g 1 ) ) + ( 2 e ( g 2 ) ) + ( 2 + e ( g ) ) + ( 2 + e ( g 2 ) ) w 6 g 2 z 6 g l = 4 e ( g 1 ) e ( g 2 ) + 2 e ( g 1 ) 1 + 2 e ( g 2 ) 1 y e g 2x 6 g l = 4 e ( c 1 ) e ( g 2 ) + 2 e ( c 1 ) ( g 2 ) + 2 e ( 0 2 ) u ( g 1 ) 所以我们得到 e ( g l 囟g 2 ) = 2 e ( a 1 ) e ( g z ) + e ( g 1 ) v ( g 2 ) 十e ( g 2 ) v ( g 1 ) 2 3 强乘积图的连通度 乘积图的连通度是乘积图的一个重要参数，在我们使用两个图来构造一个更 5 2 3 强乘积图的连通度 1 5 “大”的图的时候，乘积图连通度通常是我们最先要考虑的参数之一目前对于 乘积图连通度的研究主要集中在笛卡儿乘积图，其他乘积图几乎没有什么结果 2 3 1乘积图的连通度 到目前为止，对乘积图研究最为深入的是对于笛卡尔乘积图对于笛卡尔乘 积图的连通度。目前为止最好的结果是 对于无向图 k ( g 1 g 2 ) r a i n a 1 + 如，k 2 + 6 1 ) ( g 1 c 2 ) = r a i n 6 + 岛，a 1 t 乜， 2 v 1 ) 其中g 1 和g 2 都是连通的无向图 对于有向图 斥( g lxg 2 ) m i n a l + 如，k 2 + 6 l ，2 k l + n 2 ，2 a 2 + k 1 ) 其中g t 和g ：都是强连通的有向图。 这个结果对笛卡儿乘积图而言已经是一个相当不错的结果，已经比较接近笛 卡儿乘积图的连通图的可能上界即笛卡儿乘积图的最小点度 2 3 2 强乘积圉的连通度 两个图的笛卡儿乘积图是这两个图的强乘积图的子图，因此我们很容易知道， 强乘积图的连通度，显然是不小于对应的笛卡儿乘积图的连通度考虑到强乘积 图比对应的笛卡儿乘积图还要多很多边，因此我们希望能够得到一个在数量级上 优于笛卡儿乘积图的结果 设g = ( ve ) 是一个有限的、无向的简单图( 不含环和平行边) ，顶点集合 v = y ( g ) ，边集e = e ( a ) 符号z g 表示一个顶点和图g 强乘积的结果z 因g 我们得出如下定理： 1 6 中国科学技术大学硕士学位论文 定理设g 。= ( v ，蜀) 是连通的简单无向图，对于i = 12 ，h = 一( g ) 和 6 ( g 。) 分别表示对应图的连通度和最小顶点度，则我们有 k ( g l 囟g 2 ) r a i n n 1 ( 5 2 + 1 ) ，k 2 ( 6 1 + 1 ) ) 我们先来证明一个引理 引理1 设g 。= ( k ，五) 是连通的简单无向图，对于i = 1 ，2 ，心= 一( g 。) 和 瓯= 6 ( g ；) 分别表示对应图的连通度和最小顶点度，并且g = g 1 因g 2 则我们有 i ) k ( g ；x a ，x b ) k 2 ( 6 1 + 1 ) 对于任意的z y ( g 1 ) 并且n ，b y ( g 2 ) ，a 6 】 i i ) ( g ；：r a ，y a ) k 1 ( 5 2 + 1 ) 对于任意的z ，y y ( g 1 ) ，z y 并且n v ( c 2 ) 证明我们先证明引理的第一部分为了证明这个引理的第一部分，我们只 需要证明： 对于图g 的任意满足s v ( a ) z o ，曲) 并且1 s i = k 2 ( 6 1 + 1 ) 一1 的分离 集s ，在图g s 中存在一条( x a ，z 6 ) 路 我们考虑图g 中任意一点z ，以及在图g l 中所有和点z 相邻的点的集合 n a ，( 。) 假设点集日由点以及点z 的邻集g 。( z ) 组成，h = z ) u g 。( z ) 很显然，n g 。( z ) 5 1 ，所以我们有l h i 5 t + 1 考虑对于点集h 中的任意一点 y h ，图y g 2 是图g 的一个子图，并且对于日中任意不同两点y 1 y 2 h ，图 y l g 2 和图y 2 g 2 没有公共点由于h i 5 l 十1 并且分离集i s i = k 2 ( 5 1 + 1 ) 一l ， 因此在点集h 中至少存在一个点y h ，使得图y g 2 和分离集s 的交集至多有 一2 1 个元素由于图y g 2 同构于图g 2 ，而图g 2 的连通度是k 2 ，因此图y g 2 也 是“2 连通的，这就表明，在图g s 中，子图y g 2 的剩余图是连通的如果点y 就是点t ，则显然，我们马上就得到点x a 和点曲是连通的；如果点y 不同于点 z ，考虑点x a 和点曲在图y g 2 中的邻点由于点y 和点z 相邻，考虑点a 和点6 在图g 2 中的邻点的个数，显然我们有g 。( o ) 如k 2 和g a 。( o ) 如k 2 因 此点x a 和点曲和图y g 2 在图g s 中的剩余图是连通的，而上面我们已经证 明了图y g 2 在图g s 中的剩余图是连通的，这样就有点z n 和点z 6 在图g s 5 23 强乘积图的连通度 中是连通的也就是说 k ( g ；x a ，x b ) 2l z 2 ( 6 1 + 1 ) 对于任意的z v ( c 1 ) 并且n ，b v ( c 2 ) ，n b 同理，我们可以证明 ( g ；x a ，y a ) k 1 ( 如十1 ) 对于任意的z ，y v ( a 1 ) ，z g 并且aev ( a 2 ) 定理的证明要证明定理，我们只需要证明对于图g 1 囟g 2 的任意满足s y ( 0 1 园g 2 ) 并且l s = m t n k 1 ( 如+ 1 ) ，m ( 5 1 + 1 ) 卜1 的分离集s ，图g 1 囟g 2 一s 是连通的即可 我们始终假设点t = z l 地和点y = g l 是图g l 园g 2 一s 中两个不同的顶 点，并且吼，y l v ( c 1 ) 以及i 2 ，1 2 y ( g 2 ) 由于在图g 1 因g 2 中的每个顶点，都至少有晒+ 1 ) ( 5 2 + 1 ) 一1 个相邻的顶 点，为了简单起见，我们在图g 中任意从n a 。( x 1 ) 取6 - 个顶点，再连同点，我 们得到一个新的点集a 名，( z ) ，在图岛中任意从j v g 。( z 2 ) 取如个顶点，再连同点 x 2 我们得到个新的点集 侵( z ：) ，很明显，我们有 r 占1 ( z 1 ) v 色( z 2 ) z l z 2 ) 是 点i 7 1 x 2 的( 以+ 1 ) ( 5 2 + 1 ) 一1 个邻点类似的，我们可以定义心! 。( y 1 ) 和_ 邑( 珈) ， 并且有7 v 占，( y 1 ) 7 v 邑( 9 2 ) 1 驰 是点y l y 2 的( 5 1 + 1 ) ( 5 2 + 1 ) 一1 个邻点另 外，根据这些点的取法，我们也知道 占。扛1 ) j j n b ，( 9 1 ) i 一以+ 1 n 5 ：( 搬) i = l 占。( 2 ) l ；而+ 1 由于这些点集中， 占。( 奶) 和邑( 1 ) 都是y ( g 1 ) 的子集， ，占。( _ 2 ) 和 n 5 ，) 都是v ( g 2 ) 的子集这样，点集9 5 ，( 2 ：1 ) 和j 占。( ，) 中就可能有一些公 共点，同理点集心，( 口2 ) 和| v 6 ：( p 2 ) 中也可能有一些公共点。为了构造一些没有 公共点的点对，我们把这些点集中的公共点提取出来，这样原来的两个可能有公 中国科学技术大学硕士学位论文 共点的点集就变成三个互不相交的点集( 可能有空集) 我们做如下的假设 c 1 = x l m = q = x2= 蚝 = 占。( z ) n 占。( 9 - ) 心，( z ) g ， 睨，( f ) g ， n 5 ，( x 2 ) n 占：( 抛) 占：( z z ) 岛， ) 岛 显然，根据定义，我们知道点集g 、墨和k 是互不相交的，点集q 、 尥和k 是互不相交的，由于i 占。( z - ) i = i ，占。) l 以及j 侵( 9 2 ) l = i 占：( 啦) 我们有i 咒j = m a n d 阢j = i k i ，设 于是我们得到 设 x ，i = i m i = m ，i 也i ；i y 2 i = n c i i = 6 1 一m ，i c t | = 而一n c 1 = c l l ，c 1 2 ， = c 2 1 ，c 2 2 ， x l = z l l ，x 1 2 扔= ( z 2 1 z 2 2 m = y l l ，1 2 ， k = 垅1 ，驷2 ， c 1 ( 5 l m ) j c 2 ( 如一n ) ， ，z l m 】 ，z 卧) ， 可l m ，l 可加) 于是我们可以知道( x 1u g ) ( j e u 岛) 是点z 的邻集以及点z ，( mu q ) 23 强乘积匿的连通度 1 9 一一 ( ku 岛) 是点口的邻集以及点y 设 s 1 = c 1 c 2 = c 1 。c 2 j 1 2 = 12 ， 岛= c l x 2 = c “z 2 ，i z = 12 ， s 3 = e 1 k = c l i y 2 j l i = 1 ，2 ， & = x 1 c 2 = z u c 2 j i = 1 ，2 ， s s = m 岛= y l i c 2 j t = 1 ，2 ， = x l x j = z l ；z l t = 1 ，2 岛= m 蚝= y u y 2 1 l i = 1 ，2 ， 是= x l k = 扛1 ，锄辖= l ，2 ， 6 j m ；j = 1 ，2 ，6 2 一n ) ，以一r n ；j = 12 ，如一n ) 6 i r n ；j = 1 ，2 一，如一n ) ，m ；j = 1 ，2 ，一，如一n ) m ；j = t ，2 ，一，如一n ) ，m ；j = 1 ，2 ，一，n m ；j = 1 ，2 ，一，n ) ，r n ；j = l ，2 ，t - ， 很容易看出来最是两两互不相交的，对于i = 1 ，2 ，8 ，并且 ( x l u c l ) ( u 岛) = s 1 u 岛u 岛u 昆 ( k u a ) ( k u c 2 ) = s 1 u s 3 u s 5 us 7 为了证明定理。我们接下来构造一些点对的集合，寻找一条点z 和点y 之间 的路 很显然，集合s 1 由( 6 。一m ) 慨一n ) 个 c t ；c 2 ，点组成，这些点都是点z 和 y 的公共邻点，如下 5 1 m 如一“ s ，= uu c n 乒l j = 1 集合岛u 岛是由( 6 1 一m ) n 个 c l 。，c l i y 2 j ) 点对组成，如下 5 1 s 2 u s s = uu ，“口) t = l j ；l 集合& u 是由m ( 如一t t ) 个 奶。2 j ，9 l ：) 点对组成，如下 , 5 2 & u 昆= uu c 巧，y z ) i = l ，= l 2 0 中国科学技术大学硕士学位论文 集合s 6 u 岛u s s 是由m f t 个 j ： i x 2 j 虮，目卸，j ly 2