（应用数学专业论文）几类图的带宽问题.pdf

摘要 带宽问题是从稀疏矩阵计算，纠错码，数据结构，vl s ! 及分 子生物学等中提取出来的数学模型，有着广泛的应用背景( 吼 3 1 ) 。 矩阵的带宽问题起源于二十世纪五十年代，当时结构专家们 首次通过结构矩阵的计算来分析钢结构：为了使得象求逆以及求 特征值这样的矩阵运算花费尽量少的时间，专家们试图找到一个 等价的矩阵，在这个矩阵中，所有的非零元素皆位于以主对角线 为中心的一条窄带内，因此也就出现了。带宽”这个术语。 图的带宽同题是在1 9 6 2 年由p a s a d e n a 的j e tp r o p u ! s i o n 实验 室( 简记为j p l ) 的专家们提出的：一个6 位代码中的单个误差可 以由正立方体的边差来表示，这个正立方体的顶点是代码中的字 符。在j p i ，lh h a r p e r 和aw h a l e s 寻找能使得最大绝对误差和 平均绝对误差达到最小的代码。因此，也就产生了带宽和带宽和 问题( 至少对于立方体是这样) ( 【4 】) 。在这以后不久，r rk o r f h a g e 开始研究图的带宽问题；fh a r a r y 在p r a g u e 的一次会议上公布 了这个问题( 5 】，【6 】1 【7 】) 。从那以后，关于带宽问题就陆续有了大量 的文妙 在第一章综述之后，在已有的研究成果基础上，第二、三章 对类路树、类路图进行了研究，求出了它们的带宽和带基数。在第 四章中，求出了最大度为3 的树的二维带宽，还给出了一个求任 意树点带宽上界的算法。广f 厦列出了本文的主要结论： 1 ，类路树的带宽和带基数 图g = ( ke ) 、”v ，如果g u 的每个连通片都是路， 则称”是g 的奉原点。容易看出，路的每一个点都是本原点。如 果图g 至少有一个本原点，则称g 为类路的。易见，类路图具 i l l 有遗传性，即类路图的每一个子图均是类路的。若一个类路图c ? 是树，则称g 为类路树。 关于类路树的主要结论如下： 定理? ? 1阶不大于7 的树7 皆为类路树，其带基数b s ( r ) 满足lsb s ( t ) 3 。 定理2 22 关于类路树z 的带基数b s ( e ) ，l i 4 有 ( 1 ) 设r ，p 2 ，r 为n 中的k 条路( 包括本原点) ，f 。，l 。，f 女 为p l ，p 2 ，r 的长度( 指所含边数) ，规定f l 。“，对n 分两种情况： ( ) 当i t 1 2 一l k 时，b s ( n ) = f 扎 ( i i ) 当l t , 1 2 ，f i 不全相同时，钉b s ( 孔) k ( 2 ) 2 b s ( t 2 ) s3 ( 3 ) b s ( t 3 ) = 2 ； ( 4 ) b s ( t 4 ) = 1 定理2 3 1 关于类路树正的点带宽b 僻) ，1 i 4 有 ( 1 ) 对n 分两种情况： ( i ) 当i t = 1 2 = = i t 时，b ( n ) = 扎 ( i i ) 当i x , 1 2 ，i i 不全相同时，钉b m ) f 半1 ( 2 ) b ( t 2 ) = 3 ； ( 3 ) b ( t 3 ) = 2 ； ( 4 ) b ( t t ) = 1 定理2 4 1 设p 1 ，p 2 ，b 为孔中的k 条路，记路的长度为 f l ，1 2 ，一，f i ，且规定f 也“则当1 = 1 ，或l l = l = = 女 时，边带宽t 3 ( t t ) = k 一1 定理? 4 二若f 。二，且1 、o 一“不全相等，则边带宽i j i ( ，1 、t ) = 二 类路图的带宽和带基数 关于类路图的带宽和带基数，主要结论如下： 定理31l 若g = ( 1 r ( g ) ，e ( g ) ) 是一类路图，且卜( g ) l = n 则点带宽b t g ) 5 ；1 。 定理31 二若h 是g 的予图，则b s ( h ) b s ( g ) 。 定理31 3g 。为第一类完全类路图，则 ( i ) 当1 1 = 2 一l k 时，b s ( c 7 1 ) = 纠； ( i i ) 当1 ，1 2 ，“不全相等时，郭b s ( g 1 ) 严n + r k 。 定理31 4 g 1 为第一类类路图，则 ( i ) 当f - = f 2 - 一“时，陶b s ( g z ) 嘲； ( i i ) 当z 。，i 。，f 不全相等时，钾sb s ( g 。) 学 。 定理31 50 、为第一类完全类路图，则 ( i ) 当f 。= z 。_ = “时，b ( 0 ) = 纠； ( i i ) 当f ，f ：，? 不全相等时，b ( 0 - ) = 学1 。 定理316g l 为第一类类路图，则 ( i ) 当1 = 1 2 = = l k 时，鞠b ( c 0 訇； ( i i ) 当l t ，z ：，l k 不全相等时，陶2 b ( o ) 业2 。 定理31 7 g 。为第二类类路图，则 ( - ) 当p i ，r 、r ，t 的阶相同时，? r ( c 。) s ；1 + l ； ( i - ) 当p t ，r ，f ，r 的阶不全相等时，二b ( g ：) 字 “。 定理3l8g ，为第三类类路图。则 ( i ) 当r ，r ，b 的阶相同时，? b ( 峨) ；1 + 3 ； ( t ) 当p 。，n 2 ，p 3 的阶不全相等时，? b ( g 。) f 半 + 3 。 定理3ji 若是g 的子图，则b ( h ) sb ( g ) 。 定理3 ：g 是类路图，为去掉本原点后路的条数( 若有 多个本原点，取去掉某个本原点后余的路的条数最多的) ，则 一1 b ( g ) t i l s 最大度为3 的树的二维带宽和点带宽 g 是有n 个点的图，v ( g ) 和s ( c ) 分别表示图g 的点集和 边集。一单射 ，：1 7 ( g ) 一 l ，2 ，n l 1 ，2 ，n 】 被称为= 维带宽标号。也就是说。用一对有序的整数对( ( ”) ，2 ( ”) ) 标识”y ( g ) ，其中 ( ”) ，f 2 ( v ) 1 ，2 ，n l 。图g 的二维标号 ，的带宽定义为 口。( g ，) = 。，m 。占a ( x g ) i ，l ( u ) 一 ( ) i + i ，2 ( u ) 一，2 ( ) 1 ) g 的二维带宽定义为 岛( g ) 2 呼n b 2 ( g ，) ， 其中取遍所有的二维标号。 ，九( g ) 表示基于l 。一距离的二维带宽。兀表示最大度为 的树，于3 表示完全3 度树。主要结论如下： 定理4l i 定理412 定理41 3 定理42 1 定理422 若 为乃的高度，则 蹦元) f 业二掣_ 而，岛( 矗) ? 西， l j 吼( 乃) 2 4 一、蚕 b s ( 磊) 3 b s ( 乃) n i o x ，则m “= s ( v ) 分别对j t ，儿，j t 列按( - i i ) 中方法依次往下求，直至求 出m a x ； ( v 1 ) ( 丁) = i l l a x ，则1 3 ( l 1 ) ! t f ( g ) 一l 。 总之，在作此论文之前，只知道某些简单结论，如对毛虫树， 二层星图，完全二部图求出了带宽，对于路、圈、完金图的“卡氏 积”、复合运算及强乘积也只有一大略结果( 【卅) 歹皋文是对类路 树、类路图及最大度为3 的树的带宽问题进行讨论，井求出了精 确解。 图 关键调：点带宽 边带宽 带基致二维带宽类路树类路 a b s t r a c ti np n g l i s h 7 i h eb a n d w i d t hp r o b l e ma r i s e sf r o mt h ec i r c u l tl a y o u t ( 1 iv l s i d e s i g n s ，i n t e r o n n e c ! i o nn e t w o r k s ，s p a r s em a t r i xc o m p u t t t ti o ns ，e lr o f c o r r e c t i n gc o d ed e s i g n s ，d a t as t r u c t ur e s ，b i o l 0 9 3 ，e t c i t h a sf x t e a s i v e b a c k g r o u n d s ( ， 2 1 ， 3 】) t h em a tr i xb a n d w i d t hp r o b l e ms p e l r l st oh a v eo r i g i n a t e di nf h e 5 0 so ft h e2 0 t hc e n t u r yw h e ns t r u c t ur a ie n g i n e e r sf i r s ta n a y z e ds le e l f r a m e w o r k sb yc o m p u t e rm a n i p u l a t o no ft h e i rs t r u c t u r a lm a t r i c e si n o r d e rt ot a k et h ec o m p u t i n gt i m ea sl i t t l ea sp o s i b l ef o rf i n d i n gi nx p r s i o n sa n dd e t e r m i n a n t s ，t h ea t t e m p tw a sm a d et od i s c o v e ra ne q u i v a l e n tm a t r i xi nw h i c ha l lt h en o n z e r oe n t r i e sl a yw i t h i nan a r r o wb a n d a b o u tt h em a i nd i a g o n a l - - 一h e n c et h et e r m ”b a n d w i d t h ” t h eb a n d w i d t hp r o b l e mf o rg r a p h s ，m e a n w h i l e ，o r i g i n a t e dj u d e p e n d e n t l ya tt h ej e tp r o p u l s i o nl a b o r a t o r y ( j p l ) a tp a s a d e n ai n1 9 6 2 s i n g l ee r r o r si na6 - b i tp i c t u r ec o d ew e r er e p r e s e n t e db ye d g ed i f f e r e n c e si nah y p e r c u b ew h o s ev e r t i c e sw e r ew o r d so ft h ec o d ea tjp l ， lh h a r p e ra n daw h a l e ss o u g h tc o d e sw h i c hm i n i m i z e dt h em a x i m u ma b s o l u t ee r r o ra n dt h ea v e r a g ea b s o l u t ee r r o r t h u sw e r eb o r n t h eb a n d w i d t ha n db a n d w i d t hs u mp r o b l e m s a tl e a s tf o rc u b e s ( d 1 n o tl o n ga f t e rt h i s r r k o r t h a g eb e g a nt ow o r ko nt h eg r a p hb a n d w i d t hp r o b l e m f h a x a r yp u b l i c i z e dt h ep r o b l e ma tac o n f e r e n c ea t p r a g u e ( i s ， 6 1 ， 7 1 ) 0 nt h eb a s i so fs o m ek n o w nr e s u l t s ，a f t e ra ni n t r o d u c t i o n ，t h e f i r s tc h a p t e r ，t h es e c o n da n dt h et h i r dc h a p t e rs o l v et h eb a n d w i d t h s a n dt h eb a n d s i z e so ft h ep a t h l i k et r e e sa n dt h ep a t h l i k eg r a p h st h e f o u r t hc h a p t e rs o l v e st h et w o d i m e n s i o n a lb a n d w i d t ho ft h etr e e sw i t h d e g r e eo ft h ev e r t i c e sa tl l l o s tt hr e ea n dg i v e sa f la l g or i t h mo fs o l v i n g t h ev e r t e x b a n d w i d t h ，w h i c hi s a d a p tt oa l l lr e e si nw h a tf o l l o w s ，t h e m a i nr e s u l t si nt h et h e s i sa r el i s t e d 1 t h eb a n d 、 i d t ha n dt i r eb a n d s i z e so ft h e p a thl i k e t r e e s c a l lav e r t e xuo ft 、g r a p hg = ( f e ) a ，j r f 。j fv er t e xi fe v o l y c o n n e c t e dc o m p o n e n to fg t i sap a t ht h ep a t h sa l e p r e c i s e l yt h e c o n n e c t e dg r a p h sw h o s ee v e r yv e r t e xi sap r i n c i p a lv e r t e x s a yt h a ta g r a p hg i sp a t h h k ei fi th a sa tl e a s to n ep r i n c i p a lv e r t e x p h ep r o p e r t y o fb e i n gp a t h l i k ei sh e r e d i t a r y ：e v e r ys u b g r a p ho fap a t h l i k eg r a p h i sp a t h l i k ei fap a t h l i k eg r a p hgi st r e e ，gi s p a t h h k et r e e t h em a i nr e s u l t so ft h ep a t h l i k et r e ei sa sf o l l o w s ： t h e o r e m2 2 1t h et r e e sw h o s eo r d e ri sa tm o s ts e v e na r e a l lp a t h l i k ew h o s eb a n d s i z eb s ( t ) s a t i s f i e s1 b s ( t ) 3 。 t h e o r e m2 2 2t h eb a n d s i z e b s ( t , 1 o ft h e p a t h l i k et r e e s e ，1 i 4s a t i s f i e s ( 1 ) l e tp 1 ，p 2 ，bb et h ekp a t h si nna n dl r , 1 2 ，l ib et h e l e n g t h so ft h ep 1 ，p 2 ，一，p k ( t h en u m b e ro ft h ee d g e ) ，f l 2 f i ，t h e r ea r et w oc a s e st on ： ( i ) w h e nl r = f 2 = f i ，b 8 m ) = 嘲； ( i i ) w h e nl t , 1 2 ，l ka r en o ta l le q u a l ，陶b s ( t ds ( z ) 2su s ( 死) 3 ( 3 ) b s ( 乃) = 2 ； ( 4 ) b s ( 丑) = 1 x ( i ) t h e l ea f et w oc a s e st on ( i ) w h e nf i = 如一一k , b ( t i ) = 嘲， ( i i ) w h e nil , 1 2 ，“a l ) ta 1 1 一t t u 仙1 嘲b ( n ) 一! ( 2 ) b ( t2 ) = 3 ( 3 ) b ( t 3 ) = 二 ( 4 ) b ( t 4 ) = 1 t h e o l e l n2 4 1l e tp t ，p 2 ，rb et h e p a t h si nt ta n dt h e l e n g t ho ft h ep a t h sb ef i ，f 2 ，一，“，f l 1 2 l k w h e n l = lo f f 1 = 1 2 = = f t ，t h ee d g e b a n d w i d t hb ( t 1 1 = k 1 t h e o r e m2 4 2i fl l 2a n df l ，f 2 ，一，f ta r en o ta l le q u a l ，t h e e d g e b a n d w i d t hb ( t 1 1 = 2 t h eb a n d w i d t ha n dt h eb a n d s i z eo ft h ep a t h - l i k e g r a p h t h em a i nr e s u l t sa b o u tt h ep a t h l i k eg r a p ha r ea sf o l l o w s t h e o r e m3 1 1i f0 = ( g ) ，e ( g ) ) i sap a t h l i k eg r a p ha n d v ( a ) i = n ，t h ev e r t e x b a n w i d t hb ( a ) 嘲。 t h e o r e m3 1 2 i f 日i st h es u n g r a p ho fg ，b s ( h ) sb s ( o ) 。 t h e o r e m3 1 3l e t0 lb et h ef i r s tc o m p l e t ep a t h l i k eg r a p h ， ( i ) w h e ni i = f 2 = 一l k ，b s ( d 1 ) = f 鄂； ( i i ) w h e n l l ，f 2 ，“a r en o ta l le q u a i ，吲b s ( d 1 ) 字1 。 ei 一 a p c甜 正 b 妇dwdnaxenevenr j s ， e6 s 乩 2 4 m 一 o o 一 坨 t l sr t h e o l c 、i i l3 1 _ 1 1 ( ? l1 ) p1 h ( ，f i l s t p d , t h l i k eg r 1 tj h ( i ) w 、f - = f f = f 女，陶墨b s ( ( ：i ) r ；1 ； ( i i ) w t ”n f l ，f y 一，l ka r ( 1n 0 1 a l l “1 l l a l ，嘲b s ( g 1 ) t h e o r | ( 、n l ：1 1 5 l p f ? ，l i t ( 1 ) w h e nf i = f ! 一= “， ( i i ) w t t 1 f f 。，f i p ，f i le q u a i ，b ( d 1 ) = 1 。 t h e o i 、m3 i 6 l e tt ；1b p “1 p rs 1 p a r t 卜l i k eg r , 1 p h ， ( 0 w t t e nf - = f 。= 一“，钉b ( g 1 ) ；1 ； ( i i ) w h e n ，l ，一，f ia r en o ta l le q u a l ，r l b ( a 1 ) 半 。 t h e o i e m3 1 7 l e tg 2b et h es e c o n dp a t h l i k eg r a p h ， ( i ) w h e nt h eo r d e r so ft h ep a t hp 1 ，r ，p 3 ，p 4a r ee q u a l ，2 b ( g 2 ) 郭+ l ； ( i i ) w h e nt h eo r d e r so ft h ep a t hp l ，b ，p 3 p 4a r en o t a l le q u a l ， ? b ( ( ? 2 ) ! 笋 + l 。 t h e o r e m3 1 8 l e tg 3b et h et h o r dp a t h l i k e g r a p h ( i i ) w h e nt h eo r d e r so ft h ep a t hp l ，p 2 ，p 3a r en o ta ne q u a l ， 2 b ( g 3 ) 鼍量 + 3 。 t h e o r e m8 2 1i fhi st h es u b g r a p ho fg ，b ( 日) b ( g ) 。 t h e o r e m3 2 2 i fgi st h ep a t h l i k eg r a p ha n dki st h en u m b e r o ft h ep a t h sa f t e rt h ep r i n c i p a lv e r t i c e sa r ed e l e t e d k 一1s1 3 ( g ) 1 1 , 一l x l l ar g k la p ee ，1l= 叶皇| 2 n “ l | 虬d 叶g b m a x ，则m a x = s u m ； ( v )分别对j - ，j ”一，j t 列按( m ) 中方法依次往下求，直至求 出m a x ； ( v i )( 丁) = i i i & x ，其0b ( g ) 2 w ( c , ) 一l 。 其实，上述算法对任意树均成立。 问题。 第五章结论 在这一章中，将给出本文的主要结论及关于带宽有待解决的 5l 结论 本文主要解决了几类图的带宽问题，首先解决了类路树的点 带宽和边带宽以及带基数；其次，在类路树的基础上解决了类路 图的带宽和带基数；最后，对于最大度为3 的树，求出了其二维 带宽的上下界，并给出了求任意树的点带宽上界的一个算法。 本文对于最大度为3 的树只给出了其二维带宽的上下界，并 未给出精确解，对于边带宽和点带宽也只是给出了一上界。其精 确解还有待于进一步研究解决。希望能有同仁对此继续研究，对 最大度为3 的树的带宽问题给予解决。 致谢 首先，感谢我的恩师刘彦佩教授，在我三年的学习研究中， 他给予我极大的支持与帮助。在写论文的过程中，刘老师总是时 时鼓励我、鞭策我，并认真指导我，给我提出了非常宝贵的意见。 其次，感谢常彦勋教授、冯衍全教授、修乃华教授，他们也 给予我极大的帮助与关怀，也对我提出了宝贵的意见。 再次，感谢我的师姐魏二玲，师兄毛林繁，李赵祥，师妹贺 丹，还有郝荣霞老师，何卫力老师，他们在我作论文的过程中，给 我提出了一些有建设性的意见。在打印、排版时，他们也给了我很 大的帮助。 最后，感谢北方交通大学给予了我这个学习的机会。 f 3 】 参考文献 tl e n g a u e r ，u p p e ra n dl o w e ri ) o u d t t so nt h ec o r n p l e x i l y tj ft h e m i n c u tl i n e a ra r r a n g m e n tp r o b l e mo nt r e e s ，s i a mj a o d 。s c , 、er e m e t h o d s3 ( 1 9 8 2 ) ，9 9 1 1 3 frkc h u n g ib a b e l i n g so f g r a p h s ，i nlwb e i n e k ea n dri w i l s ( ) n e d ，s e l e c t e dt o p g c sl ng r a p ht he o r y p j ，( a c a d e m i cp r e s st n c ， l o n d o n ) 1 9 8 8 ， 5l 一1 6 8 l a iy u n g - y i n ga n dw i l l i a m sk e n n e t h ，as u r v e yo fs o l v e d p r o b l e m sa n da p p l i c a t i o n so nb a n d w i d t h ，e d g e s u m ，a n dp r o f i l eo f g r a p h s j g r a p ht h e o r y3 1 ( 1 9 9 9 ) ，7 5 - 9 4 【4 1l h h a r p e r ，o p t i m a la s s i g n m e n to fn u m b e r st ov e r t i c e s ，s a 3 z 1 2 ( 1 9 6 4 ) ，1 3 1 1 3 5 r r k o r f h a g e ，n u m b e r i n g so ft h ev e r t i c e so fg r a p h s ，c o m p u t e , 、 s c i e n c ed e p a r t m e n tt e c h m c a lr e p o r tep u t d eu n i v e r s i t y ，l a f a y e t t e i n ( 1 9 6 6 ) f h a r r y ，p r o b l e m1 6i nt h e o r yo lg r a p h sa n di t sa p p l i c a t i o n mf i e k d l e r ，e d ，c z e c h o s l o v a ka c a d e m y o f s c i e n c e p