（基础数学专业论文）图的最优标号的临界性、可分解性及有关问题.pdf

摘要 图的最优标号是图论及组合最优化中涉及顺序结构的一个专题，由于得到应用领域 的支持，并与其它理论课题发生密切联系，半个世纪以来受到众多学者的关注设g = ( y ( g ) ，e ( g ) ) 是一个图，其中y ( g ) 为顶点集，i y ( g ) i = n ，e ( g ) 为边集一个双射，： y ( g ) ， 1 ，2 ，n ) 称为图g 的一个( 顶点) 标号，它表示图中所有顶点的一个顺序；当 ，( 咙) = i0 = 1 ，2 ，n ) 时，”= ( ”1 ，t j 2 ，) 就是一个顺序这个顺序可以表示稀疏矩阵 计算中的行列顺序或消元顺序，也可以表示电路设计中的元件嵌入顺序或计算机互联网 络的布列顺序一个标号( 或顺序) 的优劣可以有不同的衡量指标；不同要求下的不同衡 量指标便引出不同的组合最优化问题，如矩阵存贮量最小引出带宽及侧廓最小化、电路设 计中的连线重叠最小引出割宽最小化，如此等等这些最优标号问题与一些图论专题有密 切关系，如最小填充及树宽与弦图扩张有关、最小侧廓及路宽与区间图扩张有关、最小扩 充侧廓及带宽与单位区间图扩张有关等；在图子式理论中起着重要作用的树宽、路宽、割 宽等都是典型的标号问题 最优标号问题的研究内容，大致可分为算法性质及结构性质两方面算法性质是指计 算复杂性、多项式算法及近似算法的设计与分析等；结构性质包括参数的上下界、极值与 极图、临界图结构、可分解性、特殊图表达式等。本学位论文主要围绕i | 缶界图结构及可分 解性展开研究，同时对特殊图类的表达式及两个新模型进行探讨在系统地掌握该领域的 前沿研究工作的基础上，本学位论文主要取得如下四个方面的创新成果 1 4 一割宽临界树 图子式理论 7 垂7 8 】的基本定理断言：任何对子式封闭的图类都存在有限的障碍集( o b - s t r u c t i o ns e t ) ，使得图g 属于此图类当且仅当不存在障碍日是g 的子式。由此可以得到这 个图类的禁用子图( 子式) 刻画。例如，平面图的障碍集为 蚝，蝎，3 ) 。文献 2 ，8 1 ，8 4 中关 于树宽和路宽临界图的结果也属于这种禁用子式刻画。文献中关于割宽临界图的研究较 少，只有【4 5 】给出了3 一割宽i | 缶界图的刻画一共5 个图，其中两个树。本文在此基础上 作出推进，解决了4 一割宽i | 缶界树的完整刻画问题对给定的标号，图g 在标号，下的 割宽是指 c ( g ，) 2 燃 u ”e ( g ) ：m ) j m ) l ； 而图g 的割宽是指 c ( g ) = 叫n c ( g ，n ， 其中的最小值取遍g 的所有标号，图g 称为一割宽临界图，是指c ( g ) ：k ，对g 的任 意真子图g 7 有c ( g 7 ) 1 若g s 存在 个点集分别为 ，u ，m 的分支且z 兰女，则 f ，( g ) = 乏：，( 皿) + i e ( s ) i ， t = 1 其中日l = g 瞰us 】+ 豆( s ) ( 1 t i ) ，豆( s ) = $ 豆：z ，s ) 由这一新的分解定理， 可以导出一系列局部消去及降维原则，并可确定出一些特殊图类的填充数，如多路图，完 全r 一部图”。p 兰2 ) 、硒，。和图g 的笛卡儿乘积图髓，。g 、凰，。和图g 的 强乘积图甄，。 g 、k 1 。和图g 的复合图k 1 ，。【g 、两个图g 和h 的联图g v 日、序 列平行图刀s p 等。 3 特殊图类的参数表达式 对图的各种标号参数，如树宽、路宽、填充、侧廓等，一般图的参数值的确定都是p 一 完全问题因此，对特殊图类建立参数值的精确表达式，成为一个重要的研究方向。文献 中这方面的研究工作的发展很不平衡，有的问题( 如带宽、割宽) 结果较多，而其它问题 ( 如填充) 结果则较少，更有个别问题( 如扩充侧廓) 尚未有人涉足本文主要对填充、树 宽、侧廓及扩充侧廓得到一些结果这些参数的定义如下：对一个图g ，令u ( 日) 表示图 日的最大团基数，则g 的填充、树宽、侧廓及扩充侧廓分别定义为 ，( g ) = m i n l e ( 日) 一1 e ( g ) l ：g 口，h 是弦图) ； t w ( g ) = m i n u ( 日) 一1 ：g 灯，日是弦图) ： p ( g ) = m i n ( 1 e ( 日) l ：gs 日，且是区间图 ； p ( g ) = m i n l e ( 日) i ：g 日，日是单位区间图) 本文在这方面的主要结果如下： 1 设g 是一个一树，s = n o ，n 1 ，一1 是g 的所有极大团之集，s 7 s 是所有 非终点团的集合。则一补树0 的填充数是 鹏h 即肛踏磊螂) + 扣十1 ) ， 其中d g ( ”) 表示点”在g 中的度数 2 设g = ( y ( g ) ，e ( g ) ) 是一个e 一树，i y ( g ) f = n ，则 t w ( 国：j n 一2 1 如果g 的所有极大团n 。均为终点团， in 一 一2否贝 3 设g 是一个弦图，s = n o ，n 1 ，一1 ) 是g 的所有极大团的集合，5 7c5 是g 的所有终点团的集合则g 的补图0 的填充数是 朋) = m i n 黥，( 盖如( ”) 一扣( 阱1 ) ) ， 其中d g ( ”) 表示点”的度 4 设t = ( y ( t ) ，e ( t ) ) 是一棵树，( t ) 表示t 的最大度。则 ( 1 ) ，( l ( t ) ) = o ，( 2 ) t t 矿( l ( t ) ) = ( t ) 一1 5 设g = ( 只，曰) 是一个分裂图， ( 1 + n 2 = i s i ) 如果d g ( 口 ) d g ( 呓) s = s lu 岛= t 毒：1 墨isn 1 ) u 暖：l t 冬n 2 ) d g ( 。：。) ，如( ” ) d g ( ”；) d g ( 壤：) ，则 n 1 1n 2 1 p ( g ) 。悲i 。i 蚤( 蠢一始( 咖+ 吾( 爵一。g ( 删+ 岬) i ， 其中爵：i “u 1 ( 。 ) i ，爵：l ”u 1 g ( 。2 ) | ，d g ( ”) 表示点”在g 中的度数其中爵= iu ( 壤) i ，爵= 1 u b ( w 2 ) | ，d g ( ”) 表示点”在g 中的度数 = l e 篡i 6 算法6 2 是计算毛虫树? 的扩充侧廓p ( t ) 的多项式时间算法，计算复杂性是 其中是丁的脊线点的个数 对完全n 部图，。，( n 1 茎n 2 n ，r 3 ) 。胁( 计 8 对格子图p m r ， 户( p m r ) = m 2 n 一詈( 2 m 2 3 m + 7 ) ( m 兰n ) 4 两个新模型 第一个新模型是m i n m “型填充问题在传统的最小填充问题中，以g a u s s 消去法 为背景，得到图g 的消去运算如下；设g 的顶点的消去顺序”= ( 1 ，啦，w 。) ，令g o = g ， 在图口。中消去顶点地后，在吼的邻集g 一( ) 添加填充边使之成为完全图。这添加 边的集合d g 一泓) = z e ( g 。_ 1 ) ：z ，” k 一她) ) 称为亏格；整个消去过程的填充边 总数，( g ，”) = l d o 一- ) l 称为消去顺序”的填充数。问题是求消去顺序”，使其填充数 ，( g ，”) 为最小。这个最小值就是填充数，( g ) 此优化问题的目标是总和形式的，即最小 和( m i n s u m ) 问题。对称地应该有一个瓶口问题，即m i n m “型填充问题，其目标函数是 d ( g ，”) = ，熙孥，| d g 一( ) l ，而最小值d ( g ) = 吨n d ( g ，”) 称为图g 的亏格数，其 中最小值取遍所有的消去顺序”本文得到了这个新参数的基本性质，如后移定理、分解 定理等。并得到一系列特殊图类的亏格数 第二个新模型是图的一个边搜索顺序问题由t d p a “o i l s 在【6 7 ，6 8 首次提出的图 搜索问题是与路宽有密切关系的著名问题，它是p 一完全的【6 7 】现在附加一个条件t 对搜索过的边立即封闭，不必再进行搜索( 我们称其为限制性图搜索问题) 。这在防疫检查 与消毒、管网的维护或检修中有应用背景在这个限制条件下，图搜索问题演变为如下的 标号问题：对标号，：矿( g ) 一 1 ，2 ，n ) ，e g ( g ，) = 四邸i u w e ( g ) ：，( “) = ，( u ) l 称为图g 在标号，下的消去割宽；并称e g ( g ) = m i n 刀c ( g ，) 为图g 的消去割宽，其中 最小值取遍所有的标号，。本文给出了确定消去割宽的多项式时间算法，建立了它与其它 参数( 如树宽、路宽等) 的关系，并得到一系列特殊图的结果。 关键词：割宽；一割宽临界树；最小填充；分解定理；侧廓；扩充侧廓；树宽；亏 格数；消去割宽 a b s t r a c t t h e 叩t i i n a l1 a b e l i l l gp r o b l e m sf o rf a p l l 8i sas p e c 瑚t o p i cd e a l i n gw i t h0 r d e r i n g8 t r u c t u r e i nf a p ht h e o r ya n dc o m b i n a t o r i a lo p t i m i z a t i o n b e c a 璐ei th a si m p o r t a n t 印p l i c a t i o n sa n d i si nc o n n e c t i o nw i t ho t h e rt h e o r e t i cp r o b l e m 8c l o s e l y ii th a sb e e ns t u d j e df o rm o r et h a h a l f o fo e n t e n a r y l e tg = ( y ( g ) ，e ( g ) ) b eag r 印hw i t hv e r t e xs e ty ( g ) a n de d g es e te ( g ) ， f y ( g ) | = 礼ab u e c t i o n ，：y ( g ) + l ，2 ，n i 8c a l l e da 6 e t 礼9o fg ，w h i c h8 t a n d sf o r a no r d e r i n g0 f 猷lv e r t i c e so f g ：i f ，慨) = 0 = l ，2 ，n ) ， t h e n 丌= ( ”l ，”2 ，) i 8a n o r d e r i g t h eo r d e r i n g7 rc a nr 印r e s 锄tn o to n l ya no r d e r i n g0 fr o w s ( o rc o l u m 璐) o re l i m i n a t i o n o r d e r i n gi nc o m p u t a t i o n 8o f 印村s em a t r i c 船，b u ta l s oa ne m b e d d i l l go r d e r i n go fe l e m e n t si n c i r c u i td e s i g n i n g ，a n da na r r a n g e m e n to r d e r i n go fi n t e r c o n n e c t i o nn e t w o r ko fc o m p u t e r s t h e r e a r ed i f f b r e n tc r i t e r i at oe 训u a t eal a b e l i n g ，；a n dd i 扛b r e n tc r i t e r i aw i t hd i f f e r e n td e m a n d si n d u c e d i 丹b r e n tc o m b i n a t i o n a jo p t i m i z a t i o np r o b l e m 8 f b re x a m p l e s ，t h em i n i m u mo ft h ea m o u n to f s t o r a g ei am a t r i ) ( i n d u c e st h em i n i m i z a t i o no f b a n d w i d t ha n dp r o 丘l e ，t h em i n i m u mo f c o n g e s t i o n o fc o n n e c t e dl i n e si nc i r c u i td e s i g n i n ge d u c e st h em i n i m i z a t i o no ft h ec u t w i d t h ，e t c t h e s eo p t i m a l l a b e l i n gp r o b l e m sa r ei nc o n n e c t i o nw i t hs o m et o p j c si ng r a p ht h e o r yi m m e d i a t e l y ) f o ri n s t a n c e s ， t h em i n i m u m 右1 1 一i na n dt r e e w i d t ha r ei nc o n n e c t i o nw i t hc h o r d a lg r a p he 】( t e n s i o n ，t h em i n i m u m p r o 丘1 ea l l dp a t h w i d t ha r ei nc o n n e c t i o nw i t hi n t e r v “g r a p he x t e n s i o n ，t h em j n i m u me x t e n d e d p r 豳k8 n db a n d w i d t ha r ei nc o n n e c t i o nw i t hp r o p e ri n t 町v a lg r a p he x t e n 8 i o n ；t h et r e e w i d t h ， p a t h w i d t ha n dc u t w i d t h ，w h i c hp l a yi m p o r t a n tr o l e si ng r 印k m i n o rt h e o r y ia r ea l lt y p i c 甜l a b e l i n g p r o b l e m s t h es t u d yo ft h el a b e l i n gp r o b l e m 8c a nb ed i v i d e di n t ot w oa s p e c t s ：o n ei st h ea l g o r i t h m i c p r o p e r t i e 8 ，t h eo t h e ri st h es t r u c t u r a lp r o p e r t i e s a i g o r i t h m i cp r 叩e r t i e sc o n t a i nt h ec o m p u t a t j o n a lc o m p l e x i t y t h ed e s i g n sa 1 1 da 1 1 a l y s e so fp o l y n o m i a lt i m ea l g o r i t h m sa n d 印p r o x i m a t i o n a j 9 0 r i t h m 8e t c ，w h i l et h es t r u c t u l a lp r 叩e r t i e si n c l u d et h eu p p e ra n di o w e rb o u n d 8o fd a r a m e _ t e r s ，e x t r e m mv a l u e sa n de x t r e m a lg r 印h s ，t h es t r u c t u r eo fc r i t i c 出g r a p h s ，t h ed e c o m p o s a b i l i t y p r o p e r t i e sa n dt h ee x p r e s s i o n so fs p e c i 出g r a p h s ，e t c t h i sd j s s e r t a t i o ni n v e s t i g a t e st h es t i - u c t u r e o fc 1 i t i c a lg 。a p h s 她dt h ed e c o m p o s 如i l i t yp r o p e r t i e sm a i n l y ，f a n dd i s c u 豁e s 怕ec x p r e s 8 i o n 8o f s p e c i 出g r a p h sa n dt 、啪n e wm o d e l s8 s 憎1 1 b a s e do nas y s t e m a t i cs u r v e y0 fr e c e n tl i t e r a t l l r e s 、 t h ed i s 8 e r t a t i o no b t a i sf o l l ra s p e c t so fc r e a t i v er e s u l t sa 8f o l l 吨，s 1 4 一c u t w i d t hc r i t i c a lt r e e s t h eb a 8 i ct h e o r e r l l si ng r a p hi n i n o rt h e o r y 【7 4 _ 7 8 】c l a i m ：觚l ym l n o 卜c l o s e dg r a p hc l a s sh a sa 矗n i t eo b s t r u c t i o ns e ts u c ht h a tag r a p hg b e l 彻g st ot h i sc i a 8 si fa n do n l yi fa n yo b s t r u c t i o n 日i s n o tam i n o ro fg n o mt h i s ，t h ec t l a r a c t e r i z a t i 0 璐o ft h ef o r b i d d e nm i n o r so ft h i sg r a p hc l a s 吕c a n b eo b t 撕n e d f 0 ra ne x a n l p l e ，t h eo b s t r u c t i o n8 e to ft h ep 1 柚a rg r 即1 1 8i s 蚝，弛3 t h er e 8 u l t s o ft h et r e e w i d t ha n dp a t h w i d t hc r i t i c a lg r a p h si nt h eh t e r a t e 8 2 ，8 l ，8 4 】b e l o n gt ot h i sf o r b i d d e n m i n o rc h 盯a c t e r i z a t i o i l s t h e r eh a v eb e e nn o t 瑚【u 出w o r ko nt h ec u t w i d t hc r i t i c 8 l 盯a p h 8i nt h e 1 i t e r a t u r e 8 ，e ) 【c 印tt h ec h a r a c t e r i z a t i o i l s0 f3 一c u t 耐d t hc r i t i c a lg r 印l l s 【4 5 】w h i c hc o n t a i nt w ot r e 猢o n g 矗v eg r a p h s b a s e do nt h i s ，t h ed i s s e r t a t i o ng i v e st h ew h o l ec h a r a c t e r i z a t i o n so f 垂c u t w i d t h c r i t i c a lt r e e s f 0 r 百v e n1 a b e l i n g ，t h ec “t 删捌 o fgw i t hr e s p e c tt o ，i sd e 6 n e d 5 1234678 n 12 4671 0 1 11 3 1 41 612456 7 1 0 1 1 1 2 1 3 1 5 1 6 吨丁3 r 7 n 0 1 2 1 1 丁1 1 f i g u r e0 垂c r i t i c a lt r e e s 1 2 13578 1 01 51 7 1 8 1 9 2 1 2 2 丁1 2 t o b e 。( g ，) = 】! ! 黑f u ”e ( g ) ：，( u ) j ，( 口) l ；t h e 叫t 训t 出 。fg i sd e 矗n e dt 。b e c ( g ) = 1 1 j n 。( g ，) ，w h 。t h em i n i m u m i st a k e n 。v e ra 1 1l a b e l i n g s ，ag r a p hgi ss a i dt 0b e 添一 森一 瓜。x 、叭 淼一 丫八兀 肛魄t 叫 d 亡hc r 甜 zi fgs a t i s 6 e st h ef o l l o w i n gt h r e ec o n d i t i o n s ：( 1 ) c ( g ) = 南；( 2 ) f o re v e r yp r o p e r s u b g r a p hg 7o fg ，c ( g ，) 1 i f g sh a s2c o m p o n e n t sw i t hv e r t e xs e t s ，( 2 七) ，t h e n f ，( g ) = ，( 峨) + l 啻( s ) l ， i = 1 w h e r e 皿= g k u 司+ e ( s ) ( 1 茎t f ) ，e ( s ) = z 可e ：z ，可s ) b y t h i s n e w d e c o m p o s i t i o n t h e o r e m as e r i e so fr u l e so fl o c a le l i m i n a t i o na n dd i m e n s i o nr e d u c t i o nc a nb eo b t 血n e d ，a n dt h e 6 l l i nn u m b e r ，( g ) 0 fs o m es p e c i a lf 印h sc a nb ed e c i d e df 0 re x a m p l e ，m l l l t i p a t h s ，l m n ， ( r 2 ) ，k 1 肌g ，1 ，mog ，而，m g j ，gv 日，s e r i e s p a r a l l c lg r a p h st t s p ，e t c 3 t h ee x p r e s s i o no fp a r a m e t e r sf o rs p e c i a lg r a p hc l a s s e s f 0 rv a r i o u sg r a p h t h e o r t i cp a r a m e t e r so ng r a p h l a b e l i n g ，s u c ha st r e e w i d t h ，p a t h w i d t ha n d 6 1 1 一i nn u l b e re t c ，t h ed e c i s i o nv e r 8 i o no fe a c ho ft h e mi s p c o m p l e t ef o rg e n e r a lg r a p h 8 t h e r e f o r e ，t oe s t a b l i 8 he x a c te x p r e s s i o n so ft h e mf o rs p e c 瑚g r a p h si so n eo fi m p o r t a n td i r e c t i o n s t oi n v e s t i g a t eh 0 w e v e r ，t h ed e v e l o p m e n to ft h i s 船p e c ti sv a r i o u sf o rd i 髓r e n tp r o b l e m si nt h e l i t e r a t u r e s ：t h er e s u l t sf o rs o m ep r o b l e m s ( f o re ) 【a m p l e s ，t h eb a r l d w i d t ha n dc u t w i d t h ) h a eb e e n r i c h ，w h i l et h a tf o ro t h e rp r o b l e m s ( f o re x a m p k ，t h ep r o 矗l e ) h a v eb e e nl e 8 s ，e v e n8 0 m e ( f o r e x 8 m p l e ，t h ee x t e n d e dp r o 矗l e ) h 可v en o tb e e ns t u d i e d i nt h i sd i s s e r t a t i o n ，、研c o n s i d e rm 撕n l y t h e 矗l l i n ，t r e e w i d t h ，p r 0 6 i ea n de x t e n d e dp r 0 6 l e t h ed e 矗n i t i o n so ft h e 8 ep a r a i l l e t e r sa r e 嬲 f o u o w s ：f o rag r a p hg ，l e tu ( 日) d e n o t e 8t h em a 撕m u mc l i q u es i z eo f 日，t h e nt h em 1 - i n ，t h e t r e e w i d t h ，t h ep r 0 6 l e ，t h ee x t 蚰d e dp r o 丘l ea r ed 曲n e d ，r e s p e c t i v e l “a s ，( g ) = m i n i e ( 日) l i e ( g ) i ：g 日a n d 日i sac l l o r d a l 伊a p h t ( g ) = m i n p ( h ) 一l ：g h ，h i sad l o r d a lg r 印h ) p ( g ) = m i n i e ( 日) f ：g 日，日i 8a ni n t e r 、枷g r 印h ) 户( g ) = m i n j e ( 日) l ：g 日，日i sap r 叩e ri n t e n 枷g r 印h ) w 毡o b t a i nt h ef 0 1 l o w i n ge x a c tr e s u l t si nt h i 8a s p e c t 1 l e tgb ea 而一t r e ew i t ht h es e ts = n o ，n 1 ，n p 一1 ) o fm a x i m 以c l i q u e sa n d1 e ts 7b et h e s u b s e to fs c o n s i s t i n go fa l ln o n e n d c l i q u e s t h e nt h em i n i m u m6 1 1 一i nn u m b e ro f 七一c o t r e e0i 8 厢h 邵肛黪磊撕) + 扣+ 1 ) ， w h e r ed g ( 口) d e n o t e st h ed e g r e eo fv e r t e x i ng 2 s u p p o s e t h a t g i sa k t r e e w i t h 几v e r t i c e s t h e t w ( g ) 礼一七一1 n 一七一2 i fa l lm a x i m a lc l i q u e sn jo fga r ee n d c h q u e s o t h e w r w i s e 3 l e t gb e c h o r d a l w i t h s = n o ) n l ，f 2 p 1 ) b e i n g t h es e to f m a x i m “c l i q u e s l e t 5 7 c s b et h es e to fa 1 1e n d c l i q u e s t h e nt h em i n i m u m6 l l i nn u m b e ro ft h ec o m p l e m e n t0 o fgi s ，( g h 即”。黥，轰撕) 一扣( 阱1 ) ) ， w h e r ed g ( 甜) d e n o t 船t h ed e g r e eo fv e r t e x 4 l e tt = ( y ( t ) ，e ( t ) ) b eat r e e ，( t ) d e n o t et h em a x j m u m d e g r e e0 fr t h e n ( 1 ) ，( 工( r ) ) = 0 ， ( 2 ) t ( l ( t ) ) = ( t ) 一1 5 l e tg = ( s ，k ，e ) b eas p l i tg r a p h ，s = s 1u 岛= 田：1s t 5 札1 ) u 嵋：1si n 2 ) ( 扎1 + n 2 = f s l ) - i fd g ( 甜 ) d g ( 削 ) 2d g ( 畦。) ，d g ( ) d g ( ；) 兰d g ( w i 。) t h e n p ( g ) 2 。! 忠蚓 蚤( 矗一d g ( 磅) ) + 蚤( 酵一4 g ( 鳓+ 雠 w h e r e 酲= j 1 g ( ) | q ? ：l ? 百1 o ( 。2 ) l ，d g ( 。) d 。t e st l l ed 。g 。o fv e ，t e x 。i 。g 6 a l g o r i t h m6 2c a nc o m p u t et h ee x t e n t e dp r o 龇户( t ) o fac a t e r p i l l 缸ti no ( 舻) t i m e ， w h e r e 七i sn u m b e ro ft h es p i n ev e r t i c e si nt 7 f 0 rac o m p l e t e 卜p 盯t i t eg r 印h 凰1 ，n 2 n ，( 礼1 兰礼2 曼曼脚， r 3 ) 8 f o rg r i dn e t w o r k s f x r 引 户( p m p n ) = m 2 n 一罟( 2 m 2 3 m + 7 ) ( m n ) 4 t 、on e wr n o d e l s t h e 丘r s tn e wm o d e l i sm i n m a x 矗u i np r o b l e m i nc l a s s i c a lm l _ i np r o b l e m ，b a s e do ng a u s s e l i m i n a t i o nm e t h o d ，t h ee l i i n i n a t i o no p e r a t i o no fgi so b t a i n e da 8f 0 1 l o w s ：l e t7 r = ( u 1 ，吨， n ) b ea ne l j m i n a t i o no r d e r i n go fg ，a n d ( 尹= g ；a f t e rv e r t e x i 8e l i m i n a t e di nt h ee l l m l n a t l o n g r a p hg t ，w ea d d t h e6 u - i ne d g e s t o m a k e 西一l h ) ac l i q u e t h ea d d c de d g es e t d g l 一1 ( 吨) = 。可隹e ( g 一1 ) ：茗，可0 t 一1 ( 忱) ) i sc 础l e dt h ed e 矗c i e n c yo f 饥；t h et o t a ln u m b e ro f6 l l i ne d g e s ，( g ，丌) = l d g t l ( 砘) ii sc a l k dt h em l - i nm l m b e ro f 丌t h em i n i h m m m l - i np r o b k mi st o6 n d a ne l i m i n a t i o no r d e r i n g7 rs ot h a t ，( g ，丌) i sm i n i m i z e d t h em i n i i n u mv d u ei st h e 矗l l i nn u m b e r ，( g ) t h eo b j e c t i v eo ft h i so p t i m a lp r o b l e mi si nt o t a l 一8 u mf o r m ，t h a ti st os a 弘t h em i n s u m p r o b l e m s y m n l e t r i c a l i y t h eb o t t l e n e c kp r o b l e mo nt h em l - i ns h o u l db ep r o p o s e d ，i e ，t h em i n - m a x6 1 l _ i np r o b l e m i nt h i sp 。o b l e m ，f o r 酉w no r d e r i n g 丌，w ec a i ld ( g ，丌) = 1 嚣：装1 上) d l ( 饥) | t h ed e 矗c i e n c yn u m b e ro fgw i t hr 朗p e c tt o 丌；d ( g ) = i i 知d ( g ，丌) t h ed e 矗c i e n c yn u m b e 。 o fg ，w h e r eps t 柚d sf o rt h cs e to fa l lo r d e r i n g s i nt h i sp a r t ，t h eb a s i cp r o p e r t i e so nt h en e w p a r a m e t e r _ d ( g ) ，f o re x a r n p l e ，t h e 丘n a lt h e o r e ma n dt h ed e c o m p o s i t i o nt h e o r e m ，a r ed i s c u 8 8 e d i na d d i t i o n ，t h ed e 矗c i e n c yn u m b e r sf o ras e r i e so fs p e c i a lg r a p h sa r eo b t a i n e d t h es e c o n dn e wm o d e li sa ne d 驴s e a r c h i n go r d e r i n gp r o b l e mf o rg r a p h s t h eg r a p h s e a r c h i n gp r o b l e m ，p r o p o s e db yt d p a r 8 0 i l s6 r s ti n 6 7 ，6 8 ，i saf a m i o u s p h a l dp r o b l e m 67 n o ww e 舀v ef 印h _ s e a r c h i n gp l o b l e mar e s t r i c t e dc o n d i t i o nw h i c l li st oc l o s et h e8 e a r c h e de d g e s i m n l e d i a t e l ys ot h a tt h e s es e a r c h e de d g e sn e e dn o tb es e a r c h e da g a i n ( w ec a l li tt h er e s t r i c t e d g r a p l l s e a r c h i n gp r o b l e m ) t h ep r o b l e ma r l s e sf r o me p i d e i n i cp r e v e n t i o na 1 1 ds t e r i l i z a t i o n ，t h e i n a i n t e n a n c ea n dr e p a i r i n go fs o m ep i p e u n en e t w o r k se t c u n d e rt h ea d d i t i o n a lc o n d i t i o n ， t h eg r a p h 一8 e a r c h i n gp r o b l e mi st r a n s f o r m e di n t ot h ef o l l o w i n gl a b e l i n gp r o b l e n l ：f o ral a b e l - i n g ，：y ( g ) 一 1 ，2 ，n - e c ( g ，) = 凇。l 1 上 e ( g ) ：，( “) = t ，( u ) ) i 8 c a l l e dt h e e ? i m i n n t e de 札t 叫d 娩o fgw i t hr e s p e c tt o ，；a n d 刀c ( g ) = m i ne g ( g ，) i sc a l l e dt h ee f i m i 礼口t e d 叫训z d 亡ho fg ，w h e r et h em i n i m u mi 8t a k e no v e ra l l l a b e l i n g s ，t h ep 0 1 y n o m ia lt i m ea 1 9 0 r i t h m t od e c i d ee g ( g ) ，i t sr e l a t i o nw i t h0 t h e rg r a p h _ t h e o r t i cp a r a m e t e r 8 ( f o re x a m p l e s 、t r e e w i d t ha n d p a t h w i d t h ) a n das e r i e so fe x a c tr 群u l t sf 撕s p e c i a lg r a p h s 盯eo b t a i n e di nt h et h e s i s 十 n “日 r n = 研啦 p k e yw b r d s ：c u t w i d t h ；七一c u t w i d t hc r i t i c a lt r e e ；f i l l - i n ；d c o m p o s i t i o nt h e o r e m ；p r 0 6 1 e ； e x 七e n t e dp r o 矗l e ；7 i h w i d t h ；d e 丘c i e n c yn u m b e “e 1 i m i i l a t e dc u t w i d t h 郑重声明 学位敝储派很却 妒沪轳9 1 第一章绪论 1 1引言 图的最优嵌入与最优标号问题是组合最优化学科中一个非常具有生机和活力的研究 课题。这主要在于它具有很强的的应用背景，并包含一系列内容丰富深刻的理论问题。因 而，数值计算、图论、计算机科学及最优化领域的众多学者投身于它的研究之中。 图的最优嵌入与最优标号问题