《几个特殊图类的二维带宽问题》由会员分享，可在线阅读，更多相关《几个特殊图类的二维带宽问题（29页珍藏版）》请在金锄头文库上搜索。
1、郑州大学硕士学位论文几个特殊图类的二维带宽问题姓名：吕红杰申请学位级别：硕士专业：运筹学与控制论指导教师：林诒勋2003.5.1中文摘要图的嵌入问题是从稀疏矩阵的计算、数据结构、V L S I 电子线路设计和分子生物学等问题中提取出来的数学模型，有着广泛的应用背景这里主要研究几个图类的二维带宽问题本文所涉及的图均为无向、简单的有限图图的二维带宽问题是S N B h a t t 和F T L e i g h t o n 在1 9 8 4 年提出的，F R KC h u n g 在【2 中作了综述我们在此基础上作了进一步的研究对一个n 顶点的图G ，V ( G ) 与E ( G ) 分别表示它的顶
2、点集与边集一个单射，：v ( v ) _ + 1 ，2 ，n ) 1 ，2 ，n ) 称为图G 的一个二维标号，即对任意u V ( G ) 标以一个有序的整数对( 1 1 ( u ) ，1 2 0 0 ) ，其中 ( u ) ，止( u ) 1 ，2 ，n 。G 在映射，下的二维带宽定义为B 2 ( G , ，) = 。m E a x ( G ) I f l ( u ) 一 0 ) I + f ，2 ( “) 一，2 扣) f ) ；G 的二维带宽定义为B 2 ( G ) = n B 2 ( G ，)、就一般情形而言，二维带宽问题是N P 一完全的这里我们主要给出分裂图、路幂图及单位区间图的结
3、果；另外对任意一个图，给出它的带宽与二维带宽之间的一个关系式引理1 【7 】设j 厶表示n 个顶点的完全图，则 B 2 ( ) = m i n 2 f 掣1 1 2 f 侮- l 方便起见，记d ( n ) = m i n 2 1 早1 ，2 1 涠一1 ) 定义2 设y ( G ) ，E C G ) 分别是简单图G 的顶点集与边集，若V ( G ) 可划分成S ，Q 两部分并且满足s 是图G 的独立集丽口是G 中的一个团，则称G 为分裂图记作G = ( 只Q ；E ) 定义3 路幂图磁是n 个顶点的简单图，其中矿( 群) = “1 ，“2 ，t n ) ，E ( 磁) = u “j 1 1
4、s I t 一引毋定义4 设J l ，也，J n 是实数轴上的n 个单位闭区间，图G 称作单位区间图，若V C G ) = J 1 ，也， ) ，1定义5 若则称n 不足于d ( n )E ( m ) = 五乃Ii 五五n 五野若d ( n ) = 2 r ；若J ( n ) = 2 r + l定理6 设n m 2 ，g = K m V 瓦。一。，那么 一 蔫?若n l ，n 分别不足于5 ( m ) ，J ( n )其他定理7 设G = ( s ，Q ；E ) 是n 个顶点的分裂图，其中s 是图G 的独立集而Q 是G 中的一个团，并且I S l = s ，l Q I = m ，如果m 2 ，
5、I t l l 么B 2 ( G ) S 场( 日)其中H = V 瓦定理8 设t 22 ，n t 2 ，记如= d O + 1 ) ，如果n 嗡) ，则岛( ) = d O + I ) ，否则剐耻溉靴不鬟其中( 南) = ( f 譬1 ) 2 + ( 【譬J + 1 ) 2 推论9 对任意图G ，我们有B 2 ( G ) 6 ( 曰( G ) + 1 ) + 1= l n i n 2 平”厚叫定理1 0 设u ( G ) 是单位区间图G 的最大团数，则占( w ( G ) ) S B 2 ( G ) J ( G ) ) + 1定理1 1 单位区间图G 的二维带宽B 2 ( G ) 等于d (
6、 u ( G ) ) + 1 当且仅当u ( G ) 一1 不是不足于6 ( u ( G ) ) 并且存在两个最大团Q l 和Q 2I I i 足_ ：I Q l n Q 2 I r + 2 ，其中r = 【业笋J 2、J1氓+扫rN21rr，f_-l，、-_IL0 ，则点集D H ( ”o ，r ) = 如V ( H ) I d H ( v O ，“ ) r )称为以”o 为中心，r 为半径的正方邻域，简称为方块( 如图1 4 所示) 为清楚起见，我们可假定”o = ( 0 ，0 ) ，那么方块D H ( v o ，r ) 就是由边界线z + Y = ：k r o Y = 士”8所围成的正方
7、形邻域，其中( X ，) 表示平面上点的坐标r = 1 ( d = 2 )r = 2 ( d = 4 )r = 3 ( d = 6 )图1 4半径为r 的方块D H ( v O ，r ) 又称作以d = 2 r 为直径的方块而由边界线o + 掣= P + 1 ，o + 掣= 一r ，o 一挈= r ，嚣一暂= - - r l围成的区域称为以d = 2 r + 1 为直径的方块( 如图1 5 所示)r = 0 ( d = 1 )掣1 ，其中D ( O ) 表示图G 的直径林诒勋教授对该下界作了很大的改进( 【5 】) ( 3 ) 二维带宽的运算性质这个课题主要研究了一些乘积图的二维带宽问题，目前
8、只有少数情形有精确结果，如f x R ，c k G ，K mxP n ，K m 岛。的二维带宽的精确值已被确定( 【6 】I 【8 m 5 】) ，其余情形尚待研究另外，由于图的加边、删边或收缩等运算而导致的二维带宽值的变化，目前还没有这方面的研究以下列出本文的常用的结论：定理1 3 1 5 】设D ( G ) 是顶点数为n 的图G 的直径，则岛( G ) 2r 器1 其中6 ( n ) 如引理1 2 3 中所定义定理1 3 2 N 对于完全图，B 2 ( ) = 6 ( n ) 定理1 3 3 f 1 5 】若H G ，则B 2 ( 日) SB 2 ( G )本篇论文的主要结果包括以下几个方
9、面：首先给出完全分裂图的二维带宽精确值，从而得到一般分裂图的一个较好的上界；其次，给出路幂图的二维带宽精确值由于任意图的带宽一旦确定，该图都可以看作一个路幂图的子图，因此我们可以得到一般图的二维带宽的一个上界，这个上界与带宽有关；最后，给出单位区间图的二维带宽值的精确刻划1 1第二章主要结果2 1分裂图的二维带宽这里我们只考虑分裂图是连通图的情形事实上，若分裂图不连通，我们只需要对每个连通分支加以研究即可设G l ，G 2 是简单图，定义G l 与G 2 的联图( f 1o ) 为G 1v G 2 = ( y ( G 1V G 2 ) ，E ( G lV G 2 ) ) ，其中y ( G lV
10、 G 2 ) = 矿( G I ) u y ( G 2 ) ；E ( G lVG 2 ) = 曰( G 1 ) UE ( G 2 ) U t 封I u y ( G 1 ) ，掣y ( G 2 ) ) 定义2 1 1 【4 】设y ( G ) ，E ( G ) 分别是简单图G 的顶点集与边集，若y ( G ) 可划分成s ，Q 两部分且满足s 是图G 的独立集而Q 是图G 中的一个团，贝称G 为分裂图记作G = ( S 口；刀) 定义2 1 2 【7 】若若J ) = 2 r ；若5 ( n ) = 2 r + 1则称n 不足于6 ( n ) 由上述定义，若n 个顶点的分裂图G = 【S ，Q
11、；E ) 满足：l s l = s ，1 Q 1 = m ，则易知G K , aV 瓦。如果分裂图G 满足m = l ，则图G 是一个星噩。一1 ，该图的二维带宽已经解决( 【7 ) ；因此我们只需要考虑m 2 的情形为了解决此类分裂图的二维带宽，我们首先证明如下的定理：定理2 1 3 设m 2 ，若G = V 瓦，其中m + 8 = n ，那么郫，= 篱27 I m 吩另警似一m k证明设，是从G 到格子图H 的一个标号，假设图G 的n 个顶点包含在平面区域R ：o z + Y b ，cSz vSd ( 这里R 尽可能地小) 上不失一般性，我们可假设Un + 打rN2l“+p，-_I，、ll
12、Ld c ，对图G 到格子图日的嵌入我们可以作如下变换；若R ，的内部有瓦中的点，我们可将它调至R ，的边界上通过这种变换有可能使得包含。的m 个顶点的区域R ，变小，但对所有从y ( j ) 到y ( 耳。) 边而言，它们在格子图H 中的最大距离不会增大因此，我们可假定R 是包含m 个格点的最小的矩形区域( 在其边界上可能会包含耳，中的点) 若b n d C + 2 ，6 ，一+ 2 d ，一c ，我们可以将R 与R 分别用R 1 和R i 替换( 如图2 1 所示) ，其中R 1 ：o S 七+ Y b 一1 ，C 一1So y d1 3R i ：n lS 茁+ Y b I ，C Isz
13、Y d 一1图2 1显然图G 的所有顶点均可嵌入R 1 中，其中蜀。的所有顶点可以嵌入到R 5 中，并且使得从y ( 墨。) 到矿( 瓦) 的边在格子图日中的最大距离不会增大设，o 是经过如上变换得到的新的标号，则岛( G ，) B 2 ( G ，o ) ( ) 如果b n = d c + 1 ，b I 一，+ 1 = d I c ，贝旷柯b n = d ( n ) ，d c = d ( n ) 1 ，一=d ( m ) 一1 ，d 一c ，= 6 ( m ) ，因此B 2 ( G ，o ) 妻( ( 6 一o ) + ( 矿一o ) )1 砉( ( 6 一口) + ( 6 ，一) )1 言(
14、 6 ( m ) + d ( n ) 一1 )注意此时的m ，n 分别不足于6 ( m ) ，6 ( n ) ( b ) 如果b n d c + 2 ，扩一o + 1 = d ，一c ，贝旷肓b - o 占( n ) 一l ，6 ，一a 6 ( m ) 一1因此B 2 ( C ，。) ；( ( b 一口f ) + ( 6 f n ) )；( p a ) + ( 6 ，一。) )；( 6 ( m ) + 跏) )( c ) 如果b n = d c + l ，6 ，一0 ，+ 1S 一c ，则上式同样成立因此我们可以得到图G 的下界：， 。篱? 一哪绷。挈情形3 ：边界线L 1U L 2 上的所有
15、点均属于y ( 墨。) 由于墨。是一个完全图，一定存在蜀。中的两点以b o J ( n ) 的距离嵌入到格子图H 中，因此B 2 ( G ，) d ( n ) 综合上述三种情形，我们可以得到图G 的二维的带宽的下界为踯， 。蔫27 一m I 吩焉邗咖L 矾咄以下我们只需给出图G 的一个正常标号达到上述的下界即可事实上，根据上述情形的讨论，我们可按如下方式进行标号：首先，分别确定d ( m ) 和d ( n ) 的值，如果它们都是偶数( 或奇数) ，那么在嵌入到格子图口对二者共用同样的中心，否则的话保证二者有一个中心重合其次，若n 对于6 ( n ) 不是不足的，那么我们可选择一个可以包含以d ( n ) 为直径的矩形的区域R ，否则我们可以通过收缩R 的一条边来得到一个更小的区域R 同样，我们依据m 对于6 ( m ) 是不是不足的来确定剧最后我们将。的所有点放入R r 中而将剩下的点放入R 爿中容易验证上述嵌入方式可以达到所示的下界我们用图2 2 所示来说明嵌入方式( 其中。代表分裂图里团中的点) ( 1 ) m = 1 0 ，n = 2 5 ，B 2 = 5 ；( 2 ) m = 6 ，n = 2 0 ，B 2 =
