（运筹学与控制论专业论文）几个特殊图类的二维带宽问题.pdf

中文摘要 图的嵌入问题是从稀疏矩阵的计算、数据结构、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 ) 分别表示它的顶点集与边集一个单射，： 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 一完全的这里我们主要给出分裂图、路幂图及 单位区间图的结果；另外对任意一个图，给出它的带宽与二维带宽之间的一个关系式 引理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 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 ，i t l l 么 b 2 ( g ) s 场( 日) 其中h = v 瓦 定理8 设t 2 2 ，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 ( 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 、j 1氓+ + 扫 r n 2 1 r r ，f_-l，、-_il 0 ，则点集 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 所围成的正方形邻域，其中( 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 ) 二维带宽的运算性质这个课题主要研究了一些乘积图的二维带宽问题，目前只 有少数情形有精确结果，如f x r ，c k g ，k m x p n ，k m 岛。的二维带宽的精确值已 被确定( 【6 】i 【8 m 5 】) ，其余情形尚待研究另外，由于图的加边、删边或收缩等运算而导 致的二维带宽值的变化，目前还没有这方面的研究 以下列出本文的常用的结论： 定理1 3 1 5 】设d ( g ) 是顶点数为n 的图g 的直径，则 岛( g ) 2 r 器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 ) 本篇论文的主要结果包括以下几个方面：首先给出完全分裂图的二维带宽精确值，从 而得到一般分裂图的一个较好的上界；其次，给出路幂图的二维带宽精确值由于任意 图的带宽一旦确定，该图都可以看作一个路幂图的子图，因此我们可以得到一般图的二 维带宽的一个上界，这个上界与带宽有关；最后，给出单位区间图的二维带宽值的精确 刻划 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 g 2 ) = 矿( g i ) u y ( g 2 ) ； e ( g l v g 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 ；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 尽可能地小) 上不失一般性，我们可假设 u n + + 打 r n 2 l “+ p ，-_i，、lll 一 n b n d c ，那么b a d ( n ) 对于g 在边界线 l i ：z + y = a ，l 2 ：x + y = b 上的点，我们有如下三种情况： 情形1 ：在边界线l 1 u l 2 上，既有k m 中的点又有- e , 中的点，也就是说，存在 u v ( k m ) ， y ( - e , ) 满足妇( u ， ) = b a 因此， b 2 ( g ，) 妇( u ，”) = b a 6 ( n ) 情形2 ：边界线l t u l 2 上的所有点均属于y ( _ 5 ) 设j 的m 个顶点包含在平面区 域r ：a $ + ys6 ，c ，s $ 一y d ，( 这里r ，尽可能地小) 上那么在r ，的任意一条边界 线上至少存在一点属于y ( j ) ，并且易知n 0 6 r 6 ，c d d isd 此时，我们又 可分以下两种子情形t ( 2 1 ) ：若6 ，一o d i c ，则6 ，一a 7 2d ( m ) 那么在爿的边界线 l i ：$ + y = 一，工：x + y = b i 上，可找到两点t 1 ，u 2 使得u l 日，u 2 彩，另外，由前提条件可知：存在 1 ，也满足 v l l 1 ， 2 l 2 ，于是 b 2 ( g ，) m a x d l ( u l ，忱) ，妇( t 2 ， 1 ) ) = m a a x b a ，6 ，一d ) 去( ( 6 一o ) + ( 6 ，一o ) ) 1 妄( m ) + 6 ( n ) ) ( 2 2 ) ：若6 ，一n d 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 d 1 3 r i ：n ls 茁+ y b i ，c isz 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 言( 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 1 u l 2 上的所有点均属于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 = 4 ； ( 3 ) m = 5 ，n 2 1 5 ，b 2 = 4 图2 2 定理2 1 4设g = ( s ，q ；e ) 是n 个顶点的分裂图，其中s 是图g 的独立集而q 是 g 中的一个团，并且吲= s ，f q i = m 馥那么 鬻? 一m j n 绷紧跏( n ) 证明因为g k m v - g , ，利用定理1 3 3 及定理2 1 3 就可证明该定理 2 2 路幂图的二维带宽 在格子图h 顶点集y ) 中，如果s y ( 日) 并且s 是以d 为直径的最大的子集，那 么s 包含的顶点数为，即s 是一个方块不失一般性，我们假设s 由以下四条直 线界定： l 1 ：o + y = o l 3 ：z y = c l 2 ：z + y = b l 4 ：z y = d 其中o b ，c 2 v ( 6 0 ) ，我们考虑如下两种情形； 情形1 ：南= 2 r 若t 不足于6 ( t + 1 ) ，也就是说t 掣b 2 ( 群) 如是显然的以下我们给出路 幂图群的一个如的嵌入：首先构造一个半径为r 的方块链l d x ( 2 r ) ，以方块d h ( v l ，r ) 的边界点( 0 ，r ) 为出发点，按各点的坐标之和z + y = r + i ( i = 0 ，1 ，) 递增并且每次仅对 y 值进行增加的顺序对顶点u 1 ，u 2 ，u 。依次进行标号当。+ v = r + i “= 0 ，1 ，) 相等 时，如果t 为偶数，则按$ 递增的次序依次标定r + 1 个点；否则，以z 递减的次序对r 个点进行标号，即 t l l ：( o ，r ) ，t 上2 ：( 1 ，r 一1 ) ，一，u r 十1 ：( r ，0 ) a = 0 ，z + y = r ) u r + 2 ：( r 1 ) ，扯r + 3 ：( r 一1 ，2 ) ，u 2 r + l ：( 1 ，r )( i = 1 ，卫+ y = r + 1 ) i t 2 r + 2 ：( 1 ，r + 1 ) ，t 2 r + 3 ：( 2 ，r ) ，- 一，1 1 3 r + 2 ：( r + 1 ，1 ) ( i = 2 ，正+ y = r + 2 ) 如图2 6 所示 o 。齐、t 、o ooo 孝、量) 、量、：= ：、 、。9 。0 。0 o 、 、 oo 。苫、0 筝、j o oo oo 、 根据上述标号方式，对任意u i y ( 群) 0 = l ，2 ，n ) ，地或者属于a ( d 日( v j ，r ) ) 或 者属于1 一o u t e r ( d h ( v j ，r ) ) ，记r n ( u i ) = “f 【 + ls i + t ) 为“：的右邻集，则 i r ( 啦) i = t 虹1 2 趔以下我们只需考虑u t 与( u l r n ( u ) ) 在格子图h 中的距离即 可。 ( 1 ) 若t “是方块d h ( v j ，r ) “= 1 ，2 ，n ) 的边界点不失一般性，假设u ，是方块 d h ( ，r ) ( 童= 1 ，2 ，n ) 某条边界线上的第m 个点，则m 曼r + l ，由于ts 掣= r ( 2 r + 1 ) ，m + t r ( 2 r + 1 ) + p + 1 ) = n ( 2 r ) ，也就是说，r n ( u i ) 中的任意一点“l 属 于d h ( v j ，r ) ，因此， d h ( u i ，u f ) 如“= 1 ，2 ，n ；u f r n ( u i ) ) ( 2 ) 若u 是矩形d h ( v j ，r ) ( i = 1 ，2 ，n ) 的1 一外点，依据我们的标号方式，和u i 的 坐标之和相等的1 一外点最多有r 个，由于t r ( 2 r + 1 ) ，所以r n ( u i ) 的所有点中不存 在满足性质2 3 1 ( 3 ) 的边界点，因此 d h ( u l ，h 1 ) 6 0 ( i = 1 ，2 ，- - - ，札；u i r n ( v - i ) ) 综合上述两种情形，此时有岛( 磁) 一6 0 + 1 ) 反之，若t 不是不足于j + 1 ) ，即t r ( 2 r + 1 ) ，考虑路幂图砭的子图p ( 0 ) + l ，我 们有b 2 ( p 矗( 如t ) + 1 ) 6 0 + 1 事实上，如若不然，我们假设b 2 ( p k ( 菇) + 1 ) = 而，那么在区域 d h ( 6 0 ) 中至少可以包含) + 1 个点，这于n ( 6 0 ) 的定义矛盾，故日2 ( f l ( 菇) + 1 ) 2 j o + 1 由定理1 3 3 可以知道路幂图磁的二维带宽大于等于j 0 + 1 ) + 1 ，并且按照上述方式进 行标号时下界是可达的 情形2 ：6 0 = 2 r + 1 - 仿照情形1 ，我们首先构造一个以南为直径的方块链l d h ( 8 0 ) ，以( 0 ，r ) 为出发点， 按各点的坐标之和z 十= r + ic i = 0 ，1 ，) 递增的顺序，对顶点i s l ，u 2 ，u n 依次进行 标号但此时的标号规则不同子情形1 ，它满足以下条件； 无论i 是奇数还是偶数，坐标和。+ y 为r + i 0 = 0 ，1 ，) 的点都是r + 1 个； 若i 为偶数，则以z 递增的顺序进行标号，否则，以$ 递减的顺序标号； 若i 为偶数，则坐标和增加扛+ = r + i + 1 ) 时，对y 坐标进行增加，否则，对值 增加 用坐标形式表示，即为 1 9 ( i = 0 ，z + y = r ) “r + 2 ：( r ，1 ) ，“r - i - 3 ：( r 一1 ，2 ) ，一，t 2 r + 2 ：( 0 ，r - 1 - 1 ) 拈2 r + 3 ：( 1 ，r + 1 ) ，牲2 r + 3 ：( 2 ，r ) l ，牡3 r - i - 3 ：( r - b1 l1 ) 魏爨2 。7 联添。 “= i ，z + = r + 1 ) = 2 ，。+ 嚣= r + 2 ) 二蔷：孓墨。 o 、 oo 也、r4x90 o 、o oo 烫2 。7 根据上述嵌入方式，对任意饿y ( 磁冰= l ，2 ，n ) ，考虑u i 和它盼宣邻集删) 中的点在格子图嚣中的距离 若t 不足予d ( t + 1 ) ，即t 掣= ( r + i ) ( 2 r + 1 ) 同联可以证明依据我们的标号 方式，r 溆) 虎熬掰有点器熹啦缘落在麓个以粕为直径豹方块蠹，鼹魏 妇( “t ，) s 如( = l ，2 ，- - ，n ；u le r ( “t ) ) 故岛( 焉) 一d o 勇一方瑟，若t 不怒不足子5 0 + 1 ) ，拜t ( r - l - 1 ) ( 2 r - l - i ) ，我们丽襻考瘩子图尹( 菇) + 1 ， 可以证明鼠( 糍) = d ( t 十1 ) + i 练上所逡，定理褥证 有了上述结果，考虑到对任：鼓图g ，若g 的带宽为t ，那么g 磁，我们很容易得 到以下的接论； 推论2 2 5 任意图g ，我们有 嚣2 g ) s 参嚣( g ) - i - l + l ：卿迥雩三 。一笔马- 1 ) 2 n 2 。3 单位区阉墨的二缝带宽 设以，以，厶是炭数轴上的n 个闭区间，定义图g 的顶点集为v ( o ) 一 j 1 ，以， ) 逡嶷e g ) 一 五弓囊磊n 西g 。这襻褥蘩弱强g 黎为酝嚣露。姿y ( g ) 申黪每个 麟问均为单位区间时，称图g 为单位区阐图( f 4 】) 从矩阵的角度考虑，此时图g 的邻 接矩阵a 为对惫块锻晦也就怒说，a 楚所有非零嚣构成若予个对角盼予方阵( 研以重 藏) ，如图2 8 所示 州一 _ 一一 x + 一 对于单位区间图的刻划，图论中已经有不少结果( 【4 】，【1 1 】，【1 6 1 ) ，例如： 定理2 3 ，1 下述论断等价： f 1 ) 图g 是单位聪间图； ( 2 ) 存农标号，：v ( a ) _ l ，2 ，瓤) ，使得若， 。) f ( y ) ，( z ) 并且x z 嚣( g ) ， 则x y ，y z e ( g ) ； ( 3 ) 存程溪点疆序( ”i ，。2 ，) 捷褥辫g 魏任意极大疆都凝有形式诹，v i + i ，铅“ ( i jsn ) ； 。 f 4 瑟g 是嚣鬻鬻虽苓含k i ，3 裕鸯警蹬子蚕。 由上述刻划及前一节知道，路幂图磁是特殊的单位区间圈以下我们将路幂图的结 聚攘广銎l 零经区闼隧。先拢，嚣先弓l 进醋鹣概念； 定义2 3 2 1 0 l 若h y ( g ) 并且对任意的”甚h ，都有“ e ( g ) ，则h 称为图g 的一个匿菸记“( g 一m a x l h lf 耳是g 的个团 引理2 3 3 【1 6 lb ( g ) = m i n w ( h ) 一i lg h ，甜是单位送闻图) ，熬中u ( 嚣) 是图h 的晟大团 瑟 1flllli-liiilllfl-i-illi1叫00甜 “；x；一， 一 np p n 引理2 3 4 1 5 若u ( g ) 是图g 的最大团，则 玩( g ) j ( g ) ) 根据引理2 3 3 可以知道，对于任意最大团为u ( g ) 的单位区间图g ，b ( g ) ：u ( g ) 一1 并且g 可以扩展成一个路幂图蒯g ) 有了这个结论，不难得出以下定理； 定理2 。3 5 设u ( g ) 是单位区间图g 的最大团，则 6 ( u ( g ) ) sb 2 ( g ) 6 ( u ( g ) ) + 1 证明由引理2 3 4 ，b 2 ( g ) 6 ( u ( g ) ) 是显然的；另一方面，由引理2 3 3 可以知道， 对于任意的单位区间图g ，b ( g ) = u ( g ) 一1 利用推论2 2 5 ，b 2 ( g ) 6 ( u ( g ) ) + 1 ， 定理得证 根据定理2 3 5 我们可以知道，单位区间图g 的二维带宽或者是6 ( u ( g ) ) ，或者是 d ( u ( g ) ) + 1 ，以下我们给出单位区间图g 的二维带宽的进一步刻划 定理2 3 6 单位区间图g 的二维带宽岛( g ) 等于6 ( ( g ) ) + 1 当且仅当( g ) 一l 不是不 足于6 ( u ( g ) ) 并且存在两个最大团q l 和q 2 满足：i q l n q 2 l r + 2 ，其中r = 【坐掣j 证明方便起见，记u ( g ) = t ，j 和( g ) ) = d ( t ) = d 充分性：若t 一1 不是不足于6 ( t ) 并且存在两个最大团q 1 和q 2 满足：i 饧n q 。i = m 【2 j + 2 ，我们证明b 2 ( g ) = j ( t ) + 1 事实上，若g 是路幂图，由定理2 2 4 ， 岛( 回= 6 ( t ) + 1 是显然的；否则，对于图g 的任意标号，考虑q i u q 2 中点的标号由于 q 1 和q 2 的都是t 个顶点的完全图，并且m i g j + 2 不失一般性，必存在”q l n q 2 满足”属于q 2 所确定的方块d 的1 一外点集，又因为t 一1 不是不足于6 ( 幻，故存在方 块d 的一个边界点满足性质2 2 1 ( 3 ) ，从而b 2 ( g ) d ( t ) + 1 ，所以b 2 ( g ) = j ( ) + 1 必要性：设岛( g ) = 6 ( t ) + 1 ，我们利用反证法，若t 一1 不足于6 ( 亡) ，由于g 砭， 岛( 砭一1 ) = j ( o ) ，所以励( g ) = j ( # ) ，与假设矛盾；若对g 的任意两个最大团0 1 和q 2 满足：1 q 1n q 2 l = m 【2 j + 1 ，我们将图g 按以下方式进行嵌入；首先构造以d 为直 径的方块d 1 ，d 2 ，d 佧等于图g 中团的数日) 的并且满足任意两个方块相交于同一条 边界线将g 的顶点以团为单位，嵌入各个方块中并将楣邻两个团的公共点嵌入相应的 公共边界线上( 如图2 9 所示) ； 0 、 、 叮0 、9 q 、少、 、 3 4 5 ) 、6 、 o - 一一，7 9b k = 3 ，d = 3 图2 9 l ： 不难证明，在这种嵌入方式下，b 2 ( o ) = 6 ( t ) ，与假设矛盾 综上所述，定理得以证明 第三章结束语 本篇论文主要研究了几类特殊图类的二维带宽：首先给出完全分裂图的二维带宽的精 确值，从而给出一般分裂图的一个较好的上界；其次给出路幂图的二维带宽的精确值， 并由此推导出任意一个图的带宽与二维带宽之间的一个关系式；最后对单位区间图的二 维带宽作出了一个准确的刻划 对于一般图的二维带宽，我们还可以在以下方面进行研究： 1 路幂图的二维带宽问题本篇论文已经解决，由于圈幂图嚷是路幂图焉的子图， 而二者的结构又有相似，因此猜想圈幂图的二维带宽问题应该不难解决另外，一些典 型图，如正则图、立方体、( m ，n ) 多重踌等的二维带宽问题尚待解决 2 本篇论文所定义的二维带宽，是在矩线距离，即三l 模距离意义下的二维带宽类 似地，有l 。模距离下二维带宽的定义： 定义3 1 1 7 对一个n 顶点的图g ，v ( g ) 、e c g ) 分别表示它的顶点集与边集对于 图g 的一个二维标号，g 在，下的二维带宽定义为 岛( g ，) = 。蹄) ( 1 ，1 一) 一，1 0 ) l ，i ，2 0 ) 一克扣) 1 ) ； g 的二维带宽定义为 成( g ) = 画n 侥( g ，) 注意到按以上方法定义的距离并不代表线路设计时电缆的实际长度换句话讲，确定 岛( g ) 的值可能没有实际的应用背景，但有其优势所在首先，由于确定统( g ) 的值比确 定b 2 c g ) 的值容易，因此，达到如( g ) 的最优标号可以看成二l 模距离意义下图g 的二 维带宽的一个近似标号并且不难看出该近似解的性能比为2 事实上，对于图g 的任 意标号，依据两种距离的定义方式不难看出 & ( g ，) 玩( g ，) 2 如( g ，) 因此，恳( g ) 岛( g ) 2 ( 臼) 其次， 危( g ) 和2 陡( 研可以看成岛( g ) 的上、下界， 有利于对日2 ( g ) 的研究最后，阮( g ) 作为一个新的图论参数，具有独立的性质尽管 如此，关于该问题的研究还比较少，它的计算复杂性目前还没有解决 3 关于二维拓扑带宽的研究 图g 的剖分图是指将g 的每条边均换成一条长度至少为1 的路而得到的图；添加的 新的顶点称为剖分点图g 的拓扑带宽定义为 b + ( g ) = m i n b ( h ) ih 是g 的剖分图) 图g 的二维拓扑带宽定义为 磁( g ) = m i n b 2 ( h ) ih 是g 的剖分图) 对于任意一个图而言，它的拓扑带宽现在已经有些结果( 【1 8 i 【1 9 】j 2 0 】) ，但关于二维拓扑 带宽问题目前尚无研究 4 在考虑带宽的结构特征时，s y s l o 和z a k 首先提出了带宽临界图( 如果图g 的任意 真子图的带宽都比b ( g ) 小，则称g 是临界图) 的概念( 【2 1 】) p z c h i n n 提出了另一种 带宽临界图的概念：图g 经过任意删去一个顶点或收缩2 度顶点这两种运算后得到的图 的带宽都小于b c g ) ，则称g 是临界图( 【2 2 】) 因此，我们可类似考虑二维带宽临界图的 性质 除了以上列举的二维带宽的研究课题外，二维带宽还有许多别的问题有待于研究比 如随机图的二维带宽、二维带宽与其他图论参数的关系等方面，这里不在一一赘述，有 兴趣的读者可以考虑 参 考文献 1 】t l e n g a u e r ，u p p e ra n dl o w e rb o u n d so nt h e c o m p l e x i t yo ft h em i n - c u tl i n e a ra r r a n g e m e n t p r o b l e mo i lt r e e s ，s i a mj a l g d i s c r e t em e t h o d s 3 ( 1 9 8 2 ) 9 9 1 1 3 【2 】f r k c h u n g ，l a b e l i n g so fg r a p h s ，i n ：l w b e i n e k ea n dr j w i l s o n ，e d ，s e l e c t e dt o p i c s i ng r a p h t h e o r y ( 3 ) ( a c a d e m i cp r e s si n c ，l o n d o n ，1 9 8 8 ) 1 5 1 1 6 8 【3 y u n g l i n gl a ia n dk e n n e t hw i l l i a m s ，as u r v e yo fs o l v e dp r o b l e m sa n da p p l i c a t i o n so n b a n d w i d t h ，e d g e s u m ，a n dp r o f i l eo fg r a p h s ，j g r a p ht h e o r y i3 1 ( 1 9 9 9 ) ，7 5 9 4 【4 m c g o l u m b i c ，a l g o r i t h m i cg r a p ht h e o r ya n dp e r f e c tg r a p h s ，a c a d e m i cp r e s s ，n e w y 0 r k 1 9 8 0 5 】l i ny i x u n ，o nd e n s i t yl o w e rb o u n d so ft w od i m e n s i o n a lb a n d w i d t h j m a t h e m a t i c a l r e s e a r c h & e x p o s i t i o n 3 ( 7 0 0 6 ) 3 4 3 - 3 4 0 【6 】s n b h a t t a n df t l e 远h t o n ，af r a m e w o r kf o rs o l v i n gv l s ig r a p hl a y o u t p r o b l e m s j c o m p u t e ra n ds y s t e ms c i e n c e v 0 1 2 8 ( 1 9 8 4 ) n 0 23 0 0 - 3 4 3 【7 】l i ny i x u n ，t w o - d i m e n s i o n a lb a n d w i d t hp r o b l e m ，c o m b i n a t o r i c s ，g r a p ht h e o r y , a l g o - r i t h m sa n da p p l i c a t i o n s ( y a l a v i ，d r l i c k ，j l i u ，e d s ) ，w o r l ds c i e n t i f i c1 9 9 4 ，2 2 3 2 3 2 【8 】w a n gm i n j u a na n dl i ny i x u n ，t w o - d i m e n s i o n a lb a n d w i d t hp r o b l e mf o rg r a p hp r o d u c t s j m a t h e m a t i c a ls t u d y , 3 ( 1 9 9 6 ) 3 4 3 - 3 4 9 【9 】9 l i ny i x u na n dy u a n j i n j i a n g ，as h o tp r o o f o nt h eb a n d w i d t ho fa g r a p ha n d i t sc o m p l e - m e r i t ，j m a t h e m a t i c a lr e s e a r c h & e x p o s i t i o n ，1 1 ( 1 9 9 1 ) ( 4 ) ，6 2 7 - 6 2 8 1 0 】j a b o n d ya n du s r m u r t y , g r a p ht h e o r yw i t ha p p l i c a t i o n n e wy o r k ：m a c a m i l l a n p r e s s ，1 9 7 6 1 l 】原晋江，康丽英单位区间图的一种刻划及其应用，石家庄铁道学院学报，1 9 9 4 ， 7 ( 2 ) ：5 0 - 5 4 【1 2 】v c h v a t a l ar e m a r k o i lap r o b l e mo fh a r a r y , c z e c h o s l o v a k m a t h m a n u s c r i p t 1 9 9 6 【1 3 】林诒勋图的最优标号与最优嵌入，运筹学杂志，1 9 9 5 ( 1 4 ) 1 4 - 2 2 【1 4 】林诒勋图的带宽的h a p p e r 方法运筹学杂志，1 9 8 3 ，2 ( 2 ) 1 1 1 7 【1 5 】郝建修s t u d yo no p t i m a le m b e d d i n gp r o g r a m ，博士学位论文，2 0 0 1 1 6 】h k a p l a na n dr s h a m i r ，p a t h w i d t h ，b a n d w i d t ha n dc o m p l e t i o np r o b l e mt 0 p r 0 d e r i n t e r v a lg r a p h sw i t hs m a l lc l i q u e s ，s i a mj c o m p u t 2 5 ( 3 ) ( 1 9 9 6 ) 5 4 0 5 6 1 f l7 】l i ny i x u n ，h a oj i a n x i ua n dl ix i a n g l u ，t w o d i m e n s i