（运筹学与控制论专业论文）一些图的填充和树宽.pdf

中文摘要 最优标号与最优嵌入问题是组合最优化学科非常括跃的一个研究课题，它具有很 强的应用性，并且包含一系列内容相当丰富的理论问题本文的研究与其中的两个问 题有关由以下两部分组成：( 1 ) 些图的填充问题，( 2 ) 一些图的树宽问题 1 一些图的填充问题 填充闯题具有强烈的实际背景在实际中经常要处理一个稀疏的对称正定方阵的 线性方程组a x = b 的求解问题，其中a 为稀疏的，即其中非零元较少，大部分是零在 运用g a u s s 消去法或c h o l e s k y 分解法求解时，消去过程中有的零元会变为非零元。这 称为矩阵的填充如果消元顺序不当，填充的非零元越来越多，增加了存贮量，便会 影响运算速度，降低工作效率所以在消元过程中，需要确定适当的消元顺序，使填 充的非零元较少这称为矩阵的填充优化问题由于正定对称矩阵与一个图相对应， 由此导出了图的填充问题 一般图的填充问题被证明为n p 一完全的因而对一般图的填充问题不可能有好算 法当然对丁一般图没有填充数的计算公式于是人们把精力转向具有特殊结构的 图因此产生了一系列降维局部约化和分解定理，来帮助求解一些已知结构的图的 填充数同时我们也可利用填充数的不同表达形式，如邻域表达式，弦图完备化定理 以及和填充有关的上、下界不等式来确定图的填充数我们在第二章里根据这些方法 得到了树的补图、森林的补图、格子图类等的填充数本文关于图的填充方面主要结 果如下： 定理2 6 设刊黾一个非空森林，则其补图于的填充数是 疋d 2 f 题乃f 一辫西 d ( u ) 十跋v ) 。1 ：w 耳乃 推论2 7 设丁是一棵树，则其补图亍的填充数是 尺乃= i 坎即卜_ i ，蛾 吠+ d 扣) ：w e 以乃 定理2 1 1 设庐g l + g 2 + + g n 表示”个图的联图一则 用g i + g 2 + g 。) 3m i n ( l 耳g j ) 卜以g ，) ) 定理2 ，1 8 设凡。是扇形格子图则 f ( r n ) 2 0 。m = l 2 月一3 埘= 2 0 ，n = l m ，n = 2 4 肌一5 ，n = 3 定理2 1 9 设c 。是球面经纬线图，则 ，2 ( n 一3 ) ， 只c m ，。) = j3 ( m 一1 ) ， l8 m - 6 ， l = i n = 3 ，! = 4 定理2 2 0p 。是( m ，n ) 一构形，则 只尸m m ) 嘲沏一1 ) + l 。 2 一些图的树宽问题 树宽问题是r o b e r t s o n 和s e y m o u r 在建立图的m i n o r 理论时提出的两个概念之一 6 - 7 刘振宏和王常藩从算法复杂性的估计中提出了另一参数“核密度” s 1 杨爱民 和林诒勋在文 9 】又证明核密度就是树宽，它们相应于矩阵的消去过程的波前宽度这 个问题同样是围绕着计算复杂性、算法理论、特殊图结果、运算性质等方面进 行s a r n b o r g ，dc o r n e i l 和a p r o s k u r o w s k i 于1 9 8 7 年证明了树宽问题的p 一完全性 卯文【9 】又推得确定弦图的树宽是多项式可解的关于特殊圉的结巢，图涂1 一作者曼 经涉足此领域但与其它标号问题相比，结果还不多对于一些已知结构的图，也可 以利用分解、约化定理来确定其树宽而且若知道其下界，又能构造一种标号，使其 达到下界值，则此图的树宽也能确定本文关于图的树宽方而得到的结果如下： 定理3 5 设g = g i + g 2 + + g k 表示七个图的联图，h = i h g 肌 ：圭月，那么 肼i q 。r a i n 7 1 职g ，) + n n ， 。 推论3 6 砾：，肿表示完全“都图，开= 圭r t , 斥l 刀2 2 魄，则 = 1 t w ( f i ，2 ，n 户_ ，一”1 定理3 7 r 。n ) ：2 定理3 8r 嗽c m ，。) = h ，= 3 ，4 ， 定理3 1 3 若n _ 2 k + 3 ，则对g = 砖，有 b l 。( 硝= t w ( 带- n - - k 一2 2 ( n - - 2 k 一2 ) 定理3 1 7 设g 是一虹连通 f v ( g ) l = m ，h 是肛连通的偏k 树，i 根邡尸 ，且 n m k ，则 t w ( g x 胁= 硼七 关键 司：填充，树宽，树的补图，森林的补图，扇形格子图，球面经纬线图。圈幂补 图，偏如树 a b s t r a c t t l t ep 心l e mo fg r a p hl a b e l h a ga n de m b e d d i n gi sa l la c t i v et o p o i ci nc o m b i n a t o r i a la n d o p t i m i z a t i o n 1 ti h e l 、i d e sas e r i e so fr i c ht h e o r ya n ds t r o n ga p p l i c a t i o n t h i st h e s i ss t u d y s t w oo f t h e s ep r o b l e m s t h e ya r ea sf o l l o w s 1 f i l l i np r o b l e mo fs o m es p e c i a lg r a p h s i np r a c t i c e ，w eo f t e nd e a lw i t hs o l v i n gas y s t e mo fl i n e a re q u a t i o n sa x 2 b ，w h e r eai s a l ln x ns y m m e t r i cs p a r s em a t r i x ，w h i c hc o n t a i n sm a n yz e r oe l e m e n t sa n dl i t t l en o n z e r o e l e m e n t s i nt h ec o u r s eo fs o l v i n gas y g t e mo fl i n e a re q u a t i o n sw i t ht h eg a u s se l i m i n a t i o n o rc h o l e s k yd e c o m p o s i t i o n ，s o m ee l e m e n t sw h i c hc h a n g e sf r o mz e r ot on o n t 霉r oa r ec a l l e d f i l l i no fm a t r i x i ft h eo r d e ro fe h r a i n f i o ni sn o ta p p r o p r a t e ，t h en o n z e r oe l e m e n t sw i l li n c r e a s e ，t h a tw i l la f f e c tt h ee f f i c i e n c ya n ds p e e do fw o r k ，s oi ti sn e e e n s s a r yt oc h o o s et h e o r d e ro fe l i m i n a u o n b e c a u s eag r a p hi sc o r r e s p o n d e dw i 也as y m m e t r i cm a t r i x t h ef i l l - i n p r o b l e mo fg r a p hi sc a u s e d t h en p c o m p l e t e n e s so fn 1 1 一i np r o b l e mo ng e n e r a lg r a p hi sp r o v e d b y l i t e r a t u r e 1 2 - i 4 s oi ti si m p o s s i b l et o h a v eag o o da l g o r i t h m ，a n dt h er e s e a r c h e r s c o n c e n t r a t eo nt h eg r a p hw h i c hh a ss p e c i a ls t r u c t u r e ，a n db u i l ds o m er e d u c t i o nr u l e st og e t t h ef i l l i nn u m b e ro fs p e c i a lg r a p h ，i n c l u d i n gd i m e n s i o n a lr e d u c u o na n dd e c o m p o s i t i o n t h e o r e m s m o r e o v e r , w ec a 1u s eo ft h ed i f f e r e n tp r e s e n t a t i o no ff i l l i na n ds o m eb o u n d a r y i n e q u a l i t yt og e tt h ef l u - i no fs p e c i a lg r a p h t h i sp a p e rg e t ss o m er e s u l t s0 1 1s p e c i a lg m p h s ， w h i c hi n c l u d e st h ec o m p l e m e n tg r a p ho fl l e e sa n df o r e s t s ，a n dg r i d g r a p h s t h em a i n r e s u l t so nt h ef i l l i no fg r a p h sa r e 丛f o l l o w s t h e o r e m2 6l e ttb ean o n - e m p t yf o r e s t ，t h e n 及n = i 联乃- - m a x 吠“) + v ) 一1 ：酊g d c o r o l l a r y2 7 l e ttb ean o n - e m p t yt r e e ，t h e n 曩而= i 坎dj 一埘戤( 趔“) + 吠v ) ：“v 以乃) t h e o r e m2 1 1l e to 】- g 2 + 十g nd e n o t et h ej o i no f ng r a p h s ，t h e n f ( g + g 2 + _ g 。) = m n i 耳面l + 足g ) ) l 自 t h e o r e m2 1 8 l e t 靠n b e a g r i d g r a p h o n a f a n ，t h e n 只晶。) = 0 ，m = l 2 b 一3 ，m = 2 0 ，n = l 所， 4 开卜s n = 2 n = 3 t h e o r e m2 1 9l e tc m ，nb cam e r i d i a na n di m i m d eg r i do i l as p h e r e ，t h e n r2 ( 踞o ) ， 目c m ，。) = 3 ( m 一1 ) ， l 8 珊一6 ， z = l n = 3 n ；d t h e o r e m2 2 0 融p m nb e ( m ，) 一c o n f i g u r a t i o n ，t h e n 以p m ，n ) 2 胛 一1 ) + 1 2 t h et r e e w i d t ho fs o m es p e c i a lg r a p h s t h et r e e w i d t hw a gp r e s e n t e da tf i r s tw h e nr o b e r t s o na n d s e y m o u rb u i l dt h et h e o r yo f g r a p hm i n o r s t h eo t h e rp a r a m e t e r n u c l e a rd e n s i t y ”w a sr a i s e df o r mt h ea g o r i d m l i c 。o m p l 。x i t ye v a l u a t i o nb y 8 】t h ee q u i v a l e n c eo ft h e s et w oc o n c e p t sw a sp r o v e db y 【9 】 5 ，l0，(1llllli、 c o r r e s p o n d i n gt ot h ew a v c f r o n to fm a t r i xa t h ep r o b l e mw a ss t u d i e di nt h e s ef o l l o w i n g a s p e c t s ：t h ea l g o r i t h m i ct h e o r ya n dt h ec o m p u t a t i o n a lc o m p l e x i t y ，t h er e s u l t so fs p e c i a l g r a p h se t t h en p - c o m p l e t e n e s sf o rt h et r e e w i d t ho fg e n e r a lg r a p h v c a sp r o v e db yl i t e r a t u r e 15 i n19 8 7 ，b u tt h et r e e w i d t ho fc h o r d a lg r a p hc a nb es o l v e dp o l y n o m i a lt i m e ，s ot h e r e s e a r c h e r sh a v eb e g u nt os t u d yt h er e s u l t so fs p e c i a lg r a p h s ，t h er e s u l t so nt r e e w i d t ha r e s t i l lf e w e rt h a nt h a to t h e rl a b e l i n gp r o b l e m i th a sr e d u c t i o nr u l e sa n dd e c o m p o s i t i o n t h e o r e m st o o m o r e o v e r ，i ft h el o w e rb o u n d so ft h et r e e w i d t ho fag r a p hi sk n o w n ：t h e t r e e w i d t hc a nb e o b t a i n e db yc o n s t r u c t e dar e a c h i n gl a b e l i n g t h em a i nr e s u l t so nt h e t r e e w i d t ho fg r a p h sa r ea sf o l l o w s t h e o r e m3 5l e tg = g t + g 2 十+ 瓯d e n o t et h e j o i no f kg r a p h s ，嘶= i 坎g o 月= m t h e n n 坎g ) = m i n ( t w ( g ) + h 一碣) 1 2 k + 3 ，t h e n 曰j ( 砖) = r w ( e , = 埘砌 疗一女一2 ，2 研一2 k 一2 ) ) t h 心m3 1 7l e tgb eae o n n 鳅e dg r a p h ， 坎g ) 卜掰矗b eak c o n n e c t e dp 碰a l k - t r e e 1 坎印i = n ，i f n m k , t h e n 6 ，瞰g x 挪= m 七 k e yw o r d ：f i l l - i n ，t r e e w i d t h , t h ec o m p l e m e n t a r yg r a p ho ft r e e ，t h ec o m p l e m e n t a r y g r a p ho ff o r e s t ，g r i dg r a p ho naf a n ，m c n d i a na n dl a t i t u d eg r i d0 1 1as p h e r e t h e c o m p l e m e n t a r yg r a p ho f t h ek - t hp o w e ro fac y c l eo nnv e r t i c e s ，t h ep a r i t a lk - t r e e 7 1 弓l 论 我们在这一章里，简单地回顾填充问魏与礴宽闻题的历史背景，介绍目前填充和 树宽各自的主要研究课题，还列出了本文的研究内容与主要结果 1 1 填充和辫宽的应用背景 最优标号与最恍嵌入嘲瓣题是缀合最优化学辩中非常活跃的一个研究课题，它翼 有很强的应用性。并且包禽一系列内容相当丰富的理论问题。如带宽、侧廓、路宽、 树宽、填充等因此，这个课题始终吸引着图论、组合最优化、数值分析、计算机科 学等颚域的众多工作者投身于它的研究之中，本节主要介绍填充瘸题秘旖宠闻题的起 源和背景 填充问题起源于稀疏矩阵技术从二十世纪7 0 年代，稀疏矩阵技术就开始活跃于 各个研究领域嘲：数学上，如数值代数、微分和耪分方程、数学援划、数理统计及孵 络流优化等分支；其它学科，如工程计算、计算机辅助设计、经济管理等分支在这 然分支中经常要处理一个稀疏的对称正定方阵的线性方程组a x = b 的求解问题，其中 系数矩眸a 为稀疏的：即其中菲零元较少，大部分是零。在运用g a u s s 消去法或c h o l e s k y 分解法求解时，为了保持矩阵的稀疏性，节约存贮单元及减少运算量从而在消去及 分鳃过程中要求礁定矩阵的行列顺序和消元敝序，由j 匕导宙了矩阵形式的一系列组合 最优化问题【3 。”， 在消去过程中，有的零元会交为非零元，这称为矩阵的填充如果消元顺序不当， 填充的菲零元越来越多，增加了存贮量，使会影响运薄速度，降低工作效率所| 基在 消元过程中，需要确定适当的消元顺序，使填充的非零元较少，这称为矩阵的填充优 化问题 目聪在瀵去跫程中还有一个量影噙着诗舞效率，邳就是津去矩阵鳃波前宽度设 a b 为矩阵a 的第行( 列) 直至每i 行( 列) 均已消去的矩阵，那么行i 的波前宽度 即： 消去过程的波前宽度 形( n = i u ：p f ，丐 “j 0 ) 讳”似) = m a xw i ( j ) l ! r 5 矩阵a 的行列排序可以用一个置换矩阵z 表示，设玎表示所有，z 阶置换矩阵所成 集合，于是得到了填充和树宽的矩阵形式的定义 定义i i ( 矩阵形式) 矩阵a 的填充数定义为 f 6 4 ) = 所加尼叫) x _ 1 7 其中b 研) 是矩阵a 在行列排序z 下的填充数 矩阵爿的波前宽度定义为 矽口产r a i n 胪叫) x e 打 其中阡一私) 是矩阵a 在行列排序工下的波前宽度 由于对称正定矩阵的特殊结构，人们将矩阵的问题用图论的术语来描述，从而导 出了图的填充问题5 6 1 r o b e r t s o n 和s e y m o u r 在建立图子式理论【6 7 1 中提出了树宽的 概念文【8 】从算法复杂性的估计中提出了另一参数“核密度”。文 9 】又证明核密度就 是树宽，它们相应于矩阵的消去过程的波前宽度总而言之，人们在不同的背景下赋 予了树宽不同的名字，给出了它的不同形式的表达式下面仅选择其中一种给出图论 意义下填充和树宽的定义 图g 的一个( 顶点) 标号就是一个双射，肛 1 ，2 ，n ) 其中贝v ) 称为顶点v e v 的标号f ( x i ) = i ( 】兰j 细) ，则工i ，j ? ，j 岛就是图g 的顶点在标号，下的顺序 给定图g ke ) 压( k d 称为图g 的补图对任一子集s c v , s 的邻集记为 9 ( 固= 仁e ，、s ：y e s 使伉y ) 毋特别地，顶点v 矿的邻集记为( 恻( v ) ) 在图g d = g 中进行如下的消去运算哪：( i ) 消去顶点”i ( 及其关联的边) ；( i i ) 增加 边使邻集( v 1 ) 中的顶点两两相连这样得到的图记为g ，；在图g i 中再消去v 2 如 此类推在运算( j i ) 中增加的边称为“填充边” 显然，上述消去与填充过程依赖于顶点的顺序v ，v 2 ，h 于是引出一个图的 排序( 或标号) 问题：求图g 的顶点顺序，使得按照这个顺序执行消去运算时，产 生的填充边数目为最小 定义顶点y y 的亏格( d e f i c i e n c y ) 为 d g ( v ) 2 ( 仁y ) l x , y e n ( v ) ，伍力e e 即为使( v ) 中的顶点两两相连( 成为完全予图) 所要增加的边的集合，那么上述消去 运算可表示为： g i + = g f 一而+ i + d o , ( x + ，) ，i = 0 ，l ，n - l ； 而填充边的集合为： e i = y d 6 心+ ，) 芦。 定义1 2 圈g 在标号，之下的填充数的定义为 目g ，力2 i 母| 图g 的最小填充数( 或简称填充数) 的定义为 只g ) 。哕f ( g ，力 图g 在标号，下的树宽定义为 丁瞰g ，办= m a xi g ( x t ) | s ，s 月- j 图g 的树宽则定义为 妖g ) 2 7 尹r r v ( g ，力- 0 达到此最小值豹标号，称为最优标号 因为月阶对称方阵可对应于一个无向图6 k ( y ，毋，其中顶点集净 v ，v ? ，v 用) ， 边集e = ( v 帕：a f 0 ) _ 矩阵a 的行列排序便对应图g 的顶点标号因此，定义11 中矩阵a 的填充和消去过程的波前宽度就是定义i 2 中图的填充与树宽，这样一来， 从不同的领域提出了相同的数学问题 1 2 填充和树宽的主要研究课题 这两个问题的研究方向主要围绕如下几个方面展开： 1 计算复杂性：1 9 8 1 年，m y a n n a k a k i s 证明了一般图的填充问题为p 一完全的 1 1 2 1 随后，原晋江和张和平在1 9 9 2 年证明了偶图和平方图的填充问题也是尸完全的 ，1 9 9 8 年又进一步证明了对直径不超过2 的偶补图的填充问题也是p 完全的】因 而对一般图的填充问题不可能有好算法同样对于树宽问题，sa r n b o r g 。d c o r n e i l 和 a p m s k u r o w s k i 于1 9 8 7 年证明树宽问题的p 完全性【1 5 】杨爱民和林诒勋又推得确定 弦图的树宽是多项式可解的9 1 2 算法理论：填充问题的研究中心仍在数值分析领域，目标是设计有效的实用 算法翔为了减小填充，g e o r g e 和l i u 的最小度算法及其变形实质上希望消去过程的 波前宽度i k 向f 尽量小林诒勋和原晋江基于“前沿分支，的概念，给出了填充问 题的另一近似算法 严喜祖给出了图的填充问题的动态规划模型，用动态规划的思 想来解图的填充数问题更具一般化，且便于计算机计算伫4 1 对于树宽问题主要是证明对树宽有界的图，某些难题( 如独立集，t h m i l t o n 圄， s t e i n e r 树) 存在多项式时间算法，随后的研究自然是寻找可以实现的( 阶数较低的) 构 造性算法 3 特殊图结果：图论工作者已经涉足此领域，但与带宽相比，结果仍不算多出 于一般图没有填充和树宽计算公式，所以人们把精力转向具有特殊结构的图于是产 生了一系列降维、局部约化和分解定理【1 。对于一些已知结构的图来说，它们是行 之有效的比如图具有一定的可分解结构( 如完全点割集、完全边割集等与其类似结 构) ，我们就可利用分解、约化定理进行分解求其填充数和树宽另外若已知图的连通 度、带宽、准带宽或树宽，可根据和填充有关的上、下界不等式确定图的填充数而 且若知道其下界，又能构造一种标号，使其达到下界值则此图的填充数也能确定。此 方法对树宽也适用 4 运算性质：这个课题包括两方面的内容：对图g 进行加边或收缩运算时， ，( 6 3 、 双g ) 的变化情况；已知图g 和图日的填充或树宽，对g 与厅进行和、积、 联、合成、加冠运算后，其填充、树宽与图g ，日的填充和树宽的关系”。1 。2 引 除了以上列举的填充和树宽的研究课题岁卜。它们还有许多别的问题有待于研究比 如：使消去过程的最大填充为最小，或者使消去过程的波前宽度之和为最小，都是有 意义的新问豚，等待着人们去探索和研究 1 3 特殊图的填充和树宽的一些结果 在前文中，我们已经知道，一般图的填充问题和树宽问题均为n p - 完全的，因而 对一般图不可能有好算法所以人们的主要兴趣便转化为研究某些特殊图的最小填充 数问题和树宽问题在本节，我们列出了一些与本文研究内容有关的一些结果 1 3 1 关于填充的一些结果 命题1 f ( i ) 对撑项点的圈g ，曩g ) = = n 一3 ( i i ) 对h 条辐的轮圈= k l + c n ，有 f ( g ) = l l 一3 ( i i i ) 对完全偶图k m 。只。) = m ( m 1 ) 2 ( i v ) 对圈的幂图辞( 1 蔓七蔓里三l ) ， 凡辞) = n k - k ( 2 k + 1 ) 定理1 1 【l 酊f ( k x p 。) = n ( n - - 1 ) ( m 一1 ) 2 ，f ( p 2 x p m ) = 州一l ， 其中6 尸j 虿以吩一1 ) ，2 一”j ( n ，- - 1 ) ，2 1 s 逛七_ 即x 舻 酬耐：糕t z 酬瓤幻；研i , 7 i f ( ：0 1 ，i f ( k ) t ) 特别的r 坝尸m x 尸。) = 棚m ，月) 1 4 本文的主类耕究内容及结果 本文的主要研究内磐为一些特殊图的填充或树宽。全文是这样安排的：在第二章， 我们研毵了一些特殊圈的填充问题；在第三章，我们研党了一些特殊图的树宽问题在每 章最詹一节给出了进一步妍究的建议本文的主要结果如下： ( 1 ) 关于填充商越 树、森林本身为弦图，其填充为零，但其补图却不然本文的定理2 6 、2 7 分别 给出了树帕补图、森林的补图的填充数表达式同时研究了( 川，忍) 构形、扇形格子图、 球面经纬线图等的填充表达式( 定理1 8 2 0 ) ( 2 ) 关于树宽问题 关手树宽问题，特辣图的结果还不多本文在定理3 7 - - 2 1 0 分勇0 给出了，1 ) 一 构形、扇形格子图、球面经纬圈的树宽袭选式；定理3 1 3 给出了豳幂补图的树觉表 达式；定理31 6 给出了任意连通图与偏k 树乘积的树宽表达式 4 2 一些图的填充数 本章主要讨论了一些特殊图的填充问题重点是树的补图、森林的补图的填充数 同时给出了沏功一构形，扁形格子图，球面经纬线图等的填充数本章分为三节，在 2 ，1 中给出了一些相关的基本概念，在2 。2 中给出了树的补图、森林的补图的填充数， 在2 3 中利用分解定理给出了格子图类中的一些特殊图的填充数，最后给出了进一步 研究的建议 2 1 填充数的等价刻划 早在2 0 世纪6 0 年代初，人们就知道最小填充数与弦图的密切关系在图g 的一 个圈中连接两个非相继顶点的边称为弦一个图中任意长度大于3 的圈均有弦，称为 弦图吼弦图有许多等价的刻划，例如： 定义2 1 【2 5 】下述论断等价 ( 1 ) g 是弦图 ( 2 ) 存在标号，卜( i ，2 ，n ) ，使得若m ) 埘 他) 且x y ，x z e e ，则y z e e ( 即 存在完美消去顺序) ( 3 ) 图g 的任意极小点割集都是团 ( 4 ) 设j ，_ 蜀，x 2 ，茁) 为图g 所有极大团所成之集，则存在以x 为顶点集的树 t ( 称为团树) ，使得若彪，再，氲依次出现在t 的一条路上，则x n 蕊苒 弦图的基本特征是如下两个结果( a d i r a c ，1 9 6 1 ) ： 性质2 1 【2 7 】任意弦图g 都存在一个顶点v ，其邻集( v ) 中的顶点两两相邻这 样的顶点称为单纯顶点 性质2 2 5 2 硼最小填充数以g ) 卸当且仅当g 是弦图 弦图的特例有树、缸树及区间图 对于一般图g ，如下的定义给出填充的另外一种表示形式 定义2 2 【l l j 任意图g 的最小填充数f ( g ) 就是使g 成为弦图的最小添加边数，即 f ( g ) = m i n ( e ( t 1 ) 点( g ) l ：g hh 是弦图， 从此我们却可以看出，填充问题实质上是将图g 扩张为弦图，使增添的边数为最 小，所咀最小填充问题又转化为弦图完备化问题当然，将确定最小填充数转化为弦 圈完备化问题，并不能从算法上解决我们的问题，因为它们都是p 一完全的但可以 利用此定义来确定一些图的填充数 此外，我们还可以使用填充的边界表达式对给定的标号，如前，设，0 ，) = i ( i = 1 ， 2 ，n ) ，在图g 中考虑s 的导出子图g 嗡】它不一定是连通的，可能由若干个分支 组成：其中包含最后一个顶点对的分支称为“前沿分支”，其顶点集记为则有如下 定义： 定义2 _ 3 【1 1 】 图g 在标号厂下的填充数为 t f ( g ，护i 慨) ，一i 以g ) i 同其它图的标号问题一样，这种邻域表示在确定一些图类的填充数中有重要的作用 填充数和其它图论参数之间有如下的关系： 性质2 3 对任意图g ，若占( g ) 表示其最小度。则 r g ) + i e ( g ) 1 ( 以+ 1 ) ( 占( g ) + 1 ) 2 此下界可达，如树及完全图 性质2 4 【】l j 若图g 是k 连通的，则h g ) + i e ( g ) i t ( 2 n k 一1 ) 2 此下界可达，如树、圈及完全图均使等号成立，上述两下界互不包含在连通度 h g ) 2 占( g ) 的情形，性质2 4 的估价往往优于性质2 3 的估价：在颤g ) 0 文献 n 】给出了足g ) = o 的充 要条件是g 为弦图，并由此把任一图的最小填充问题转化为弦圈完备化问题另外， 对有若干个连通分支的图其最小填充数为各分支最小填充数的和，所以我们可仅考 虑连通图的最小填充数m j 2 2 树的补图、森林的补图的填充 树、森林本身为弦图，其填充数为零，但其补图却不然下面利用前文给出的定 义和性质给出它们的填充数表达式 以g + 疗表示图g 和图的联图文 1 3 ，1 6 1 得到下述关于两个图的联图的填充 数表达式 引理2 1 m 1 只g 斗= 珊f 摊( h g ) + l 厕| ，h 叼+ 陋炳粥 上一结果的直接推论是： 引理2 2 设日是一个图而k 是一个完全图，则n 日是一个弦图当且仅当日是一 个弦图 证明由引理2 1 及只勾= o 的性质可知，( 瑚) 印，即k + h 是一个弦图当且仅当 r 印= 0 ，即日是一个弦图 口 引理2 3 设丁是一棵树，则r 是。个弦图当且仅当丁的直径3 证明设亍是一个弦图若r 的直径24 ，设p = x y u l l 是r 中的一条最长路由 于尸的长度4 ，且z t 不含圈，x ，y ，“，v 必满足： x ，y ) n “，v 且】，y u ，z 甜，y y 匹鼠7 ) 但此时x y u v x 是图于中的一个导出4 圈，这与于是弦图的假设相矛盾，从而t 的直经 必3 反过来设树r 的直径为蔓3 当r 的直经2 时，r 为一个星，从而亍的每个分 支均为完全图；此时丁显然是弦国现设树f 的直经为3 ，则2 是一个双星，即r 的 项点和边有如下形式： 坎d 2 她划，h 弘y j ，y ，) 联乃2 砂 u x a c i ：1 - 区s ) ut y 叻j 1 _ ，g ) ， 其中j ，f 1 在于中z 。和y 。的邻集分别是两个团 y ，知) 和秒，y ，) ，而坎d ( x 。m ) = z 。h ，y ，) ， 也是于中的一个团故以顺序 x qy “x | ，x 3 。y j ，。y f 在亍中对顶点进行消去运算时不会产生填充边从而f # ) - - - - - 0 ，进而亍为弦图口 引理2 4 设r 是一个非空森林，又设f + 是丁的一个边子集，且冒t 域乃则百+ 是丁的一个填充当且仅当t - - e “晗好有一个非平凡分支，且该非平凡分支是一棵直径 茎3 的树 证明 设f t 是亍的一个填充，则亍+ e + 是弦图若t e + 含有至少两个非平凡 分支，则存在x y u r g e ( t ) 日+ ，使得伍y ) 和fm v ) 处在t - - e 的不同分支但x u j r c x 是a 占，中的一个导出4 圈这与于_ + e 是弦图相矛盾因而t - - e + 恰好有一个非平 凡分支设该非平凡分支为n 则 f + e 女= k + 亍i 其中丘是h d 、h 丁- ) 为顶点集的完全图当v ( 3 = r ( t o 时，升压+ = 元由于n e t 为弦图，并结合引理2 2 可知亍，是一个弦图再由引理2 _ 3 可知t 1 是一棵直径3 的 树 反过来，设卜e * 恰好有一个非平凡分支元，且乃是一棵直径3 的树由引 理2 3 可知元是一个弦图注意到于+ 占+ 是一个完全图与岛的联图再由引理2 2 便知，升e 是一个弦圈从而f + 是f 的一个填充口 以矗( 7 ) 表示森林r 中直径s3 的子树的最大边数当r 为空图时，显然有 ( 乃= o 引理2 5 设r 是一个非空森林，则 i ，( d = m a x 哦功+ 域v ) 1 ：7 2 1 , 6 以乃， 证明设x y e 日d 使得 硪x ) 十硪y ) 一1 = - m a x 或“) + 域v ) 一1 ：“v e e ( 乃) 令p 匆= 氍一) u “协| y ) ) ，t i = 丁 】，则n 是r 的一个直径3 的子树，且瞰乃) = 鼬) 十一) 一1 从而 ( 7 ) 2 m 积 吠甜) + 硪v ) 一l ：“v e e ( d ) 反过来，设n 是丁中任直径3 的边数最大的子树由h ( 7 3 的定义，有 1 1 2 ( 力= 1 e ( t 2 ) i 当n 的直径为l 时，n 中恰有两个相邻顶点，设为z 和) ，则 ( 力= i 以哟卜_ 1 = c f r 。( “) 十d r ，( v ) - 1s ( m ) + 翻一1 当n 的直径为2 时，n 同构于石一， 其中j = j 联乃) ；，取x 为n 中度为f 的顶点，而y 为n 中的一个l 度顶点，则 ( d = i 以1 2 ) f = s = d r 舡) + d ”一1 d ( x ) + a o , ) - - 1 当乃的直径为3 时，丁，的顶点和 边有如下形式： 职乃) = x 。，x 一，如，弘，y j ，p ) ， 戤r 2 ) = x o y o u 工d ，：1 sf 蔓5 ) u 0 吐 ：1 - ，茎， 其中s ，f 1 ，此时 ( 乃= i 耳乃) fj + f + 1 = d r ，0 0 + d r 。) 一1 d ( x o ) + d ( y 。) - - 1 综上所述，必有矗( 乃sm a x 硪“) + 烈v ) 一l ：u v c e ( 7 0 ) ，结合已证不等式 ( d 棚础 武“) + 吠v ) 一1 ：u v e e ( 乃) ，便得欲证，口 定理2 6 设，是一个非空森林，则其补图r 的填充数是 只d = l 联乃1 m 蕊 硪哟+ 嵌v ) 一1 ：删e 耳幻) 证明设f + 是r 的一个最小填充，则嗣= 陋+ ：由t 非空及f + 的最小性可知， f + e ( 但e + e ( d 由引理2 4 可知，t - - e 叶台好有一个非平凡分支设为，1 ，由 坦i 的最小性并结合引理2 , 4 可知，t i 是，的一棵直径3 的边数最大的子树从而 | c ( n ) l 一 ( 乃，由引理2 5 便有 定理证毕口 只乃二= j e + 2 ie ( z ) l l 目) f = ie ( 力t 一域力 。取幻i m a x i a ( u ) + # ( o 一1 ：“v s 段7 ) ) 推论2 7 设磋一裸树，则其补图的填充数为 足7 ) 2 y ( ：o i m a x 域“) + 州：h ve 占( 乃) 证明 由i e ( z ) i 。f 啊即卜l 代入定理2 6 立得欲证口 2 3 格子图类的填充 格子图是实际中遇到最多的一类图，它包括平面格子图、环面格子图、球面格子 图它们均为稀疏图但是关于它们的填充数还没有一般的表达式；已有的结果也仪 为格子图中阶数比较低的图本节我们利用分解定理和约化准则给出扇形格子图、球 面经纬图及沏，丹) ，构形等的填充数表达式 图的最小填充问题没有统一的算法但是若图具有一定的可分解结构，那么就可 利用约化准则将图分解为结构相对简单的子图，然后再分别求萁最小填充数及最伉标 号一般地，问题的约化准则包括优势条件、降维原则及分解定理下面将给出这方 面的若干结果 定义2 4 图g 的一个点割集s 职g ) 称为完全点割集，是指它的导出子图g 啷 为完全图 引理2 8 1 1 6 设s 为图g 的完全点割集，g s 的各分支的顶点集为n ，班， ( 陇) ，并设鼠= g 【以u s ( 乒1 ，2 ，k ) ，则 其g ) = 圭民黝 定义2 s 图g 的边割集胪画；称为完全边黼如果导出子图印伪支撑 的完全偶图 引理2 9 1 鄙 设陋- 习为图g 的完全边割集若记鼠= g 阎，h 2 = g 面，则 f ( 6 3 = r a i n e ( h 2 ) + f ( h o ，厦扁) + k 岛) ) ，其中目两为图的补图的边数 推论2 1 臼f j 7 】若连通圈g 的块为b l ，岛，屏，则 只g ) 2 f ( 9 3 i = l 作为此定理的应用，这里把它推广到h 个图的联的情形 定理2 1 1 设g = g 1 fg 2 + + g k 表示i i 个图的联图，n i = i v ( g i ) i ，萨，则 f ( g 】+ g 2 + g n ) = r a i n ( 芑以g j ) + 足g 0 ) 1 9 s “1 a 证明：令出g i ，胙z6 1 i ，由引理2 1 得： 自 f ( g t + g 2 + g ) = m 加 晌f + 托，阪历f + 尺g f ) 对口类似上面分解首先把它看作两个图的联，连续运用弓! 理2 1 舻1 次，即得上述 结论口 引理2 1 2 ” 设丁是图g 的一个极小点割，ft i = c ，h 是图g 。r 的一个连通分支， 又设g i n q ；日的收缩顶点为“若存在v e t 使得丁 v 为g 的一个团且“v 是g l _ e ，的 一条b 韧边则有 曩g ) = 以6 - + 以乃h 耳乃i ，其中以印= 叫日两：x ，) ，日 定义2 6 几乎完全图是其补图的非平凡分支为k 2 的子图 引理2 1 3 t 8 】设r 为图g 的一个极小点割，若g 死为一几乎完全图，则 及g ) = 足g 堰丁) ) 十2 段丁( 及7 ) 定义同上) 引理2 1 4 【7 】设图g 的连通度为k ，且7 1 是一个点割集it i = k 若g l r 诸分支 的顶点集为v i ，坎，咖况) ，且g ( d 的补图的每一个非平凡分支均为星七1 。 则 f ( g ) = 墨以髓) + 暇r ) | 芦i 其中h , = - g 【k u ，】+ 以d ( 】 ，y l ) ，及d 定3 1 i 司上 引理2 1 5 1 9 1 设g 是2 一连通的，v 坎g ) ，d r y ) = 2 ，( v ) ：扛y ) 则 姻2 一篇仨二 下面是这个定理的一般形式 引理2 16 1 9 1 若v 是舡连通图g 的一个k 度顶点，z ( v ) ，且m v ) 扛 是g 的一个 团，则 f ( g ) = h g v + 西) 十i 玩