（计算机软件与理论专业论文）halin图及小树宽图若干算法的研究.pdf

论文题目 专业 博士生 指导教师 h a l i n 图及小树宽图若干算法的研究 计算机软件与理论 陆芸婷 娄定俊教授 摘要 在平面上嵌入一棵树r ，丁的每个内部顶点的度数至少为3 并且r 至少有一 个内部顶点。作一个圈c 连接r 的所有叶顶点，丁的所有叶顶点组成c 上的所 有顶点。这样得到的平面图称为h a l i n 图。树r 称为h a l i n 图的特征树，圈c 称 为h a l i n 图的伴随圈。通常用h = t k g c 表示一个h a l i n 图。 本文主要研究了h a l i n 图及小树宽图的几个相关算法。论文第一章主要介绍 相关概念和术语。对h a l i n 图和小树宽的历史和研究现状做了介绍。第二到四章 详细介绍了利用动态规划和压缩扇的方法求解h a l i n 图中的三个问题，并设计了 线性时间的算法解决这些问题。第五章研究了小树宽图上的全一问题。 本文主要研究了h a l i n 图中的以下三个算法： ( 1 ) 找最大权对集问题是著名的分派问题，并能得到最佳利益。在一个赋权一 般图上求解一个最大权完美对集的问题的算法的时间复杂度是0 ( 1 川l e i t o g l 川) 。第 二章解决了在一个赋权h a l i n 图上，寻找具有最大权的对集和完美对集、几乎完 美对集等问题，并给出线性时日j 的算法。 ( 2 ) 图g = ( 日正整数k 蔓l t 4 。g 的顶点是否能划分成k 个不相交的集合n ， 砼，“，使得对于f 1 。，厨，由”诱导的子图足一个完美对集。这个问 题是一个n p 完全问题。本文第三章首先证明出在h a l i n 图上2 s k 舛，然后给出 相关算法。算法的时间复杂度是d ( 1 i d ) 。 ( 3 ) 一个网络可以表示为无向图g = ( e e 印其中y 是顶点的集合，e 是边的 集合，d 是边的费用函数吐e r 。s 是矿的子集，2 1 l 司! i 。s t e i n e r 树问题 就是寻找g 的一棵予树t s = ( n f ，回，s o _ 矿ev , e e ，并且使花费域i 曲= 已。r 谢p ) 最小。求s t e l n e r 树问题是n p 完全问题。本文第四章中把这个问题限制到 h a l i n 图上，并给出线性时间算法。 中山大学博十学位论文 h a l i n 图厦小树宽图若1 。算法的研究 h a l i a 图实际上是一种树宽3 的图。树宽是一种测量图与树的相似度的参数。 许多图都有常数上界的树宽。例如，树和森林的树宽l ，系列平行图和外平面图 的树宽立，h a l i n 图的树宽垫。最后我们把h a l i n 图扩展到小树宽( 科) 的图上， 进行最小全一问题的求解。 全一问题可以如下描述：假定一个n xn 的棋盘的每个方格内安装有一个电 灯和一个按钮。按下某个方格内的按钮，将使这个方格内的电灯由亮变灭或者由 灭变亮，而且会使与这个方格有边相邻的方格内的电灯也同样改变。 如果初始状态所有电灯都是灭的，那么是否可以通过按下一组按钮，使得最 终棋盘上的所有电灯都处于亮的状态? 这个问题也被称为全一问题。如何求得一 组最少的按钮使得最终所有电灯都处于亮的状态? 这个问题被称为最小全一问 题。 在一般图中，最小全一问题是n p 完全问题，第五章描述在小树宽图上对其 进行求解，给出线性时间算法。 在第六章，我们总结了本文研究的几个算法，并提出了我们以后将要进行的 工作。 关键词：h a l i n 图，完美对集，s t e i n e r 树，树宽，全一问题 i i t i t l e ：r e a r c ho nt h ea l g o r i t h m so f h a l i ng r a h sa n dg r a p h sw i t hs m a l lt r e e w i d t h m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：l uy u n t i n g s u p e r v i s o r ：l o ud i n g j u n ( p r o f e s s o r ) a b s t r a c t a h a l i n g r a p h h = 1 u c i so b t a i n e db ye m b e d d i n ga t r e e t i n t h e p l a n eh a v i n gr i o v e r t i c e so fd e g r e e2 ，a n dt h e na d d i n gac y c l ect oj o i nt h el e a v e so fti ns u c haw a y t h a tt h er e s u l t i n gg r a p hi sp l a n a r i fti sas t a r , t h a ti s ，as i n g l ev e r t e xj o i n i n gt ot h e o t h e rv e r t i c e s t h e nhi sc a l l e daw h e e l i nt h i sp a p e r , w es t u d ys o m ea l g o r i t h m si nh a l i ng r a p h sa n dg r a p h sw i t hs m a l l t r e e w i d t h i nc h a p e ri ，w ei n t r o d u c es o m ec o n c e p t sa n dt e r m i n o l o g yu s e di nt h e p a p e rf i r s t ，a n dt h e nw er e c a l lt h er e l a t e dh i s t o r ya n ds o r o ek n o w nr e s u l t so nh a 5 n g r a p h sa n dg r a p h sw i t hs m a l lt r e e w i d t h f r o mc h a p t e r2t o4 ，w ed e s i g naf e w a l g o r k h m si nh a l i ng r a p h sb yd y n a m i cp r o g r a m m i n ga n ds h r i n k i n gf a n i nc h a p t e r5 ， w es t u d yt h em i n i m u ma l l o n e sp r o b l e mi n 酽叩h sw i t hs m a l lt r e e w i d t h t h i sp a p e rp r e s e n t st h r e ea l g o r i t h m si nh a l i n 笋a p l sa sf o l l o w s ： ( 1 ) f i n d i n gam a t c h i n gw i t ht h em a x i m u m t o t a lw e i g h ti st h ew e l l k o n w na s s i g n m e n t p r o b l e mo fa s s i g n i n gp e o p l et oj o h sa n dm a x i m i z i n gt h ep r o f i t s ，t h e r e i sa l l o ( il q l e l l o g l 州) a l g o r i t h mt of i n dam a x i m a lw e i g h t e dm a t c h i n gi ng e n e r a l 伊印l l s i n c h a p t e r2 ，w e f o c u so n f i n d i n g t h e m a x i m u m - w e i g h t e dm a t c h i n g ，t h e m a x i m u m - w e i g h t e dp e r f e c tm a t c h i n ga n dt h em a x i m u m - w e i g h t e d n e a rp e r f e c t m a t c h i n gi nh a l i ng r a p h sa n dg i v el i n e a ra l g o r i t h m s ( 2 ) w h e t h e rt h ev e r t i c e so f g r a p hg c a nh ep a r t i t i o n e di n t oks u b s e t sn ，圪，瞻s 0 t h a tf o re a c hi e 1 ，目，t h es u b g r a p hi n d u c e db yki sap e r f e c tm a t c h i n gw h e r e 阚h t h i si sa nn pc o m p l e t ep r o b l e m i nc h a p e r3 ，f i r s tw ep r o v et h a ti n h a l i n g r a p h s2 k g t h e na na l g o r i t h mi sg i v e n t h et i m ec o m p l e x i t yi sd ( 1 ) ( 3 ) as t e i n e rt r e ei sat r e ei nad i s t a n c eg r a p hw h i c hs p a n sag i v e ns u b s e to fv e r t i c e s ( s t e i n e rp o i n t s ) w i t ht h em i n i m a lt o t a ld i s t a n c eo ni t se d g e s t h es t e i n e rp r o b l e mi n l i i 巾山大学博士学位论文 h a l i n 图及小树宽圈若下算法的研究 掣印l l sc a l lb ef o r m u l a t e da sf o l l o w s ：l e tg = ( ke 力b e a l lu n d i r e c t e dn e t w o r k w h e r evi st h es e to fv e r t i c e si ng ei st h es e to fe d g e si nga n de d g ef i m c t i o n 砘 e 胄l e t s b eas u b s e to f i i , 2 阍i 川f i n das u b n e t w o r k t s = ( 矿，f ，曲，s 量p t k f ea n dt h et o t a lc o g 诫7 p = e e f 战p ) i sam i n i m u m i ti sk n o w nt ob e n p c o m p l e t e w er e s t r i c tt h ep r o b l e mi nh a l i nn e t w o r k sa n dg i v eal i n e a ra l g o r i t h mi n c h a p t e r4 h a l i ng r a p hi sag r a p hw i t ht r e e w i d t h 当t h et r e e w i d t ho fag r a p hm e a s u r e st h e r e s e m b l a n c eo f t h eg r a p ht oat r e e s e v e r a lc l a s s e so f g r a p h sh a v eb e e ns h o w nt oh a v e c o n s t a n tb o u n d e dt r e e w i d t h f o re x a m p l e ，t r e e s f o r e s t s ! l ，s e r i e sp a r a l l e lg r a p h s 立， o u t e r p l a n a rg r a p h s 立，h a l i ng r a p h s9 3 i nt h ee n d ，w ee x t e n dh a l i ng r a p h st og r a p h s w i t ht r e e w i d t h 纠t os t u d yt h em i n i m u ma l l - o n e sp r o b l e ma n dg i v eal i n e a rt i m e a l g o r i t h m t h em i n i m u ma l l - o n e sp r o b l e mi sc i t e da sf o l l o w s ：s u p p o s ee a c ho ft h es q u a r eo f a nn x nc h e s s b o a r di se q u i p p e dw i t ha l li n d i c a t o rl i g h ta n dab u t t o n i f t h eb u t t o no f a s q u a r ei sp r e s s e d , t h el i g h to f t h a ts q u a r ew i l lc h a n g ef i r o mo f f t oo na n dv i c ev e r s a ； t h es a m eh a p p e n st ot h el i g h t so fa l lt h ee d g e a d j a c e n ts q u a r e s i n i t i a l l ya l ll i g h t sa r e o f f n o w , c o n s i d e rt h ef o l l o w i n gq u e s t i o n s ：i si tp o s s i b l et op r e s sas e q u e n c eo f b u t t o n si ns u c haw a yt h a ti nt h ee n da l ll i g h t sa r eo n ? t h i si sr e f e r r e da st h ea l l o n e s p r o b l e m i st h e r es u c haw a y t h a ti nt h ee n da l ll i g h t sa r eo n ? a n df i n a l l y , h o wt of i n d s u c haw a yt h a tp r e s s e s f e wb u t t o n sa sp o s s i b l e ? t h i si sr e f e r r e da st h em i n m u m a l l o n e sp r o b l e m i th a s a p p l i c a t i o n si nl i n e a rc e l l u l a ra u t o m a t a mm i n i m u ma l l - o n e sp r o b l e mi sn p c o m p l e t ei i lg e n e r a l i nt h e 严c h a p t e r , w e r e s t r i c tt h ep r o l e mi ng r a p h sw i t hs m a l lt r e e w i d t h ( t g ) i nc h u p e r6 ，w eg i v eas u m m a r yt ot h e s ea l g o r i t h m sa n dp o i n to u tt h ew o r kw e w 1 】d o i n t h e f u t u r e k e y w o r d s ：h a l i ng r a p h , p e r f e c tm a t c h i n g ，s t e i n e rt r e e ，t r e e w i d t l ha l l - o n e sp r o b l e m 1 1 引言 第1 章绪论 i 蛩论是近年来发展迅速而又应用广泛的- - f 新兴学科。它最早起源于一些数 学游戏的难题研究，如1 7 3 6 年欧拉皿e u l e r ) 所解决的哥尼斯堡( kn i g s h e r g ) q ：桥 问题，以及在民间广泛流传的一些游戏难题。如迷宫问题，匿门博奕问题，棋盘 上马的行走路线问题等。 这些古老的难题，当时吸引了很多学者的注意，在这些问题研究的基础上又 继续提出了著名的四色猜想，汉密尔顿( 环游世界) 数学难题。 1 8 4 7 年，克希霍夫( k i r c h h o 用图论分析电路网络，这是图论最早应用于工 程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论， 博奕论以及计算机科学等各个领域的问题时，显示出越来越太的效果。图论在各 种物理学科，工程领域，社会科学和经济问题的广泛应用使它受到数学和工程界 的特别重视。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数 学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1 7 3 6 年的论著中， 他所考虑的原始问题有很强的实际背景。 图论的研究对象相当于一维的拓扑学。图论( g r a p ht h e o r y ) 是数学的一个 分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成 的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物， 用连接两点的线表示相应两个事物间具有这种关系。图论起源于著名的哥尼斯堡 七桥问题。在哥尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起 来，如下图所示，a 、b 、c ，d 表示陆地。问题是要从这四块陆地中任何一块开 始，通过每一座桥正好一次再回到起点。然而无数次的尝试都没有成功。欧拉 在1 7 3 6 年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问题： 即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代 替，从而相当于得到一个图( 如下图) 。 中山大学博十学位论文 h a l i n 圈及小树宽图若干算法的研究 佃， c ” 欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的 图可以某种方式走遍的判定法则。这项工作使欧拉成为图论( 及拓扑学) 的创始 人。 图论的广泛应用促进了它自身的发展。2 0 世纪4 0 6 0 年代，拟阵理论、超 图理论、极图理论，以及代数图论、拓扑图论等都有很大的发展。随着计算机的 出现和发展，近三十年来，图论作为计算机理论和应用的工具，迅速地发展起来。 本文所提出的关于h a l i n 图和小树宽图的若干算法的表述与论证正是基于 对图论领域中目前尚未解决的问题展开研究所得到的结论。 1 2 基本术语与概念 一个图g 是指一个有序三元组( 坎g ) ，耳g ) ，) ，其中h g ) 是非空的顶点 集，觑g ) 是不与h g ) 相交的边集，而是关联函数，它使g 的每条边对应于g 的无序顶点对( 不必相异) 。若p 是一条边，而“和v 是使得( e ) = u v 的顶点， 则称e 连接和v ；顶点“和v 称为p 的端点。顶点集和边集都有限的图称为有 限图：否则称为无限图。 在有限图中，我们通常用v = y ( 6 3 i 表示顶点数，p i 耳g ) 障示边数。为了方便， 在不至于引起混淆的情况下，我们用v 表示h g ) ，e 表示e ( 回。有时我们也只 使用( 巧d 二元组来表示一个图。 一条边的端点称为与这条边关联，反之办然。与同一条边关联的两个顶点称 为相邻的，与同一个顶点关联的两条边也称为相邻的。端点重合为一点的边称为 环，端点不相同的边称为连杆。 如果一个图的顶点集和边集都有限，称这个图为有限图。只有一个顶点的图 称为平凡图，其他所有的图都称为非平凡图。一个图如果既没有环也没有两条连 杆连接同一对顶点，则称这个图为简单图。 与无序顶点对( “，v ) 相关联的边称为无向边；与有序顶点对v 相关联的边称 为有向边。每条边都是无向边的图称为无向图；每条边都是有向边的图，称为有 向图。同时拥有有向边，无向边的图称为混合图。 本文只研究有限的简单无向图。 若h 四坎g ) ，觑肋e 耳g ) ，并且是在毋加上的限制，则称图汀是g 的子图( 记为h g g ) ，同时我们称g 是的母图。当g ，但h g 时，h 为g 的真子图( 日c g ) 。g 的生成子图( 或生成母图) 是指满足h 邡；h g ) 的子 图( 或母图) h 。 若矿是矿的一个非空子集，以矿为顶点集，以两端点均在矿中的边的全体 为边集所组成的子图，称为g 的由旷导出的子图，记为g r 1 ，简称为g 的导 出子图。导出子图g 【n 明记为g - v 。若f 是的一个非空子集，以f 为边集， 以f 中边的端点全体为顶点集所组成的子图，称为g 的由e 导出的子图，记为 g f 】，简称为g 的边导出子图。边集为三的生成子图简记为g f ；它是从g 中删去e 中的边所得到的子图。设g l 和 是g 的子图，若g l 和g 2 没有公共 顶点。则称它们是不相交的。g l 和g 2 的并图g , w g 2 是指g 的一个子图，其顶 点集为h g l ) u h g 2 ) ，其边集为以g 1 ) u e ( g 2 ) 类似地可以定义g l 和g 2 的交图 g 1 n 国。不相交的两个图g l 和g 2 的联图g l + g 2 是指在g l u g 2 中，把g l 的每个 顶点和g 2 的每个顶点连接起来得到的图。 图g 的顶点v 的度如( 是指g 中与v 关联的边的数目，每个环算作两条边。 用j ( g ) 和4 ( g ) 分别表示g 的顶点的最小度和最大度。 g 的一条途径是指一个有限非空序列w = v o e l v l e 2 v 2 e k v k ，它的项交替地为顶 中山大学婢士学位论文 h a l i n 幽发小树宽闰若千算法的研究 点和边，使得对l s f i m ，则称m 为g 的最大对集， 显然每个完美对集都是最大对集。 如果使用n 种颜色把图g 的每个顶点部分配一种颜色，且使得邻点异色，则 称此为对图g 的顶点的正常月着色。图g 的顶点的正常着色中所需颜色数的最 小值称为g 的顶点色数，简称色数，记之为瓜g ) 。 如果使用”种颜色把图g 的每条边都分配一种颜色，且使得邻边异色，则称 此为对图g 的边的正常n 着色。图g 的边的正常着色中所需颜色数的最小值称 为g 的边色数，简称边色数，记之为z ( g ) 。 如果使用”种颜色把图g 的每个顶点和每条边都分配一种颜色，且使得邻边 异色，邻点异色，并且每一个顶点和与之相关联的边也异色，则称此为对图g 的正常h 全着色。图g 的正常全着色中所需颜色数的最小值称为g 的( 点边) 全色数，记之为肋( g ) 。 1 3 算法复杂性介绍 算法是指令的有限序列，其中每条指令都有明确的含义，每条指令表示一个 或多个操作；序列的执行会在有限的时问内停止下来并给出问题的任何实例的 中山大学博士学位论文 h a l i n 圈及小树宽翻若午算法的研究 解答。一个要解答的一般性题目称为问题。一般来说，解决一个问题的算法往往 不是唯一的。衡量一个算法的好坏，人们常常从其复杂性、正确性、简单性、最 优性、可读性等方面加以考虑，算法复杂性包括时间复杂性和空间复杂性。我们 在此只考虑时自j 复杂性，即算法运行所需要的时间。在算法分析中，人们常用初 等运算( 算术运算、比较运算和转移指令等) 的次数，表示一个算法在假设的计 算机上执行时所需要的时间。即假设每做一次初等运算，需要一个单位时间。 一个算法所需要的运算次数与两个因素有关：1 问题实例的太小；2 如果 问题实例的大小相同，算法运行的时间与实例的具体情况有关。这样，如果用” 表示问题实例的大小，则算法a 运行所需的时间不仅与n 有关。用i 和1 1 分别表 示实例和实例的大小，定义算法a 的时间复杂度( 简称为复杂度) 疗( 哟为 ( n ) = m a x m l 存在实例，使得t l l = n ，且a 对，运行所需的运算次数为m 设a n ) 是定义在非负整数集上的一个函数，如果存在正实数c 及正整数 使得当一时，有正( ) s 0 ( h ) 成立，则称办( 功的阶小于或等于且n ) 的阶，记为 ( h ) = 0 惯月) ) 。如果加，) 是一个多项式函数，则称算法a 为一个多项式算法a 否则的 话，称算法a 为指数算法。 对一个问题的每一个实例，如果只要求回答“是”或“否”，则称这个问题 为判定问题。通常，任何一个有限的最优化问题都可以转化为一系列的判定问题。 一个判定问题，如果可以在多项式时阃内得到解决，则称它为p 问题，所有 p 问题组成的集合称为p 类，记为p 。一个判定问题，如果给出它的解的一个猜 测后存在多项式算法验证这个猜测是否为问题的解，则称这个问题为n p 问题 所有n p 问题组成的集合称为n p 类，记为n p 。不难看出，每个p 问题均为n p 问题。是否所有的n p 问题都是p 问题，即是否有p = n p ，是理论计算机科学问 题中的核心问题之一。 给定两个判定问题兀i 和丌：，如果存在一个多项式算法，能够将问题兀1 变换 成为问题兀：的一个特例，并且使得兀t 的答案为“是”当且仅当n z 的这个特例的 答案也是“是”，则称兀1 可以多项式地归约为r l ，记为兀i * 兀2 。如果q 是一个 n p 问题，并且对任意的兀e n p ，均有n o c q ，则称q 为n p 完全问题，所有的n p 完全问题组成的集合称为n p 完全类，记为n p c 。n p 完全问题是n p 类中最困 难的问题。如果一个n p 完全问题能够用多项式算法解决，则n f 中所有的问题 都可用多项式算法解决；反之，如果n p 类中有一个问题不能用多项式算法解决， 则所有的n p 完全问题都是难的。判别一个问题是否n p 完全问题有重要的意义。 如果不是n p 完全问题，且该问题在多项式时间可验证解，则可以试着找到多项 式算法，否则的话，人们一般转向求其近似算法。 不难证明：如果n l 和r i z 都属于n p ，兀l h 2 且兀l 是n p 完全的，则n 2 也是 n p 完全的。所以，要证明一个问题兀是n p 完全的，其步骤如下： 1 兀e n p ； 2 存在一个n p 完全问题兀，使得兀m - i 。 1 4h a l i n 图的定义及相关研究结果与进展 h a l i n 图是一类特殊的平面图，它以其自身的特殊结构成为众多数学家们和 数学爱好者所研究的对象。它是德国汉堡大学r h a l i n 博士于1 9 6 9 在( s t u d i e s o l l m i n i m a l l y n - c o n n e c t e d g r a p h s ) ) 这篇学术报告中作为极小3 一连通图而提出的。 如今，h a l i n 图有很多种提法，但实质都一样，本文采用如下定义。 定义1 4 1 1 1 1 在平面上嵌入一棵树nr 的每个内部顶点的度数至少为3 并且， 至少有一个内部顶点。作一个圈c 连接r 的所有叶顶点，r 的所有叶顶点组成c 上的所有顶点。这样得到的平面图称为h a l i n 图。树r 称为h a l i n 图的特征树， 圈c 称为h a l i n 图的伴随圈。通常用h = t u c 表示一个h a l i n 图。 定义1 4 2 2 】p ( 矿3 ) 个顶点的轮图( 简称p 阶轮) 是由p 一1 个顶点构成的圈和 另一个与这p 一1 个顶点都相邻的顶点组成的简单图，记为。 定义1 4 3h a l i n 图日1 7 l , c ，设w 是一个只与一个非叶点相邻的非叶结点。那 么与w 相邻的叶顶点和w 构成的导出子图我们称为扇。w 是扇的中心。 定义1 4 4h a l i n 图h = i i d c ，考虑h 中的扇，连接h d 和啊砰n 的三条边构 成了一个h 的3 边割集，记为e c 3 ( 一。 定义1 4 5 设f 是一个扇，h x f 表示把圩中的扇f 压缩成一个点 后的图。 v ( t t d = 岍u 坎邡、h d ，目服毋被定义为下： 1 如果一条边的两个端点都在，中，那么删除该边。 中山大学博士学位论文l - l a l i n 幽及小树宽| 垄| 若干算法的研究 2 如果一条边的两个端点都在肛f 中，那么这条边保持不变。 3 如果一条边的一个端点在h - f 中，另一个端点在f 中，那么现在这条边在 h - f 中的端点不变，另一端点为点 。 压缩扇的方法是由c o r n u e j o l s ，n a d d e f 和p u l l e y b l a n k 在文 3 】中提出的。 显然，轮是特殊的h a l i n 图。由h a l i n 图的定义有下列性质 定理1 4 1 4 】设g 是h a l i n 图，则 ( 1 ) g 的所有叶点度数是3 ( 2 ) g 的任何两个内面至多有i 条公共边界，并且每个内面与外面有且仅有1 条公共边界 ( 3 ) 如果g ，那么g 至少存在2 个内点，并且至少存在这样的1 个内点， 它只与1 个内点相邻，而其余与它相邻接的点都是叶点 ( 4 ) 如果g 降0w 是符合( 3 ) 的点，令( 。= “，v 1 ，也， r 这里，7 , 是与w 邻接的唯一内点。设z 是邻接到v 一的外点，y 是邻接到v k 的外点。令 g _ g - v 1 ，v 2 ，v k u x w , y w ， 则g 也是h a l i n 例，并且若w 不是最大度点，则有( g ) = ( g ) 。 定理1 4 2 3 1 非轮的h a l i n 图伽z u c 至少有两个扇。 定理1 4 3 3 如果f 是h a l i n 图h 中的一个扇，那么h x f 仍然是一个h a l i n 图。 定理1 4 4 1 5 设为h a l i n 图，则日是h a m i l t o n 连通的。 定理1 4 6 6 】设g 是h a l i n 图，则( g ) = ( g ) 定理1 - 4 s 7 对于p 5 的轮，有肋( 蚴印 定理1 4 7 6 】设g 为一h a l i n 图，( 6 3 = 4 ，r 为g 的特征树，则船( 回= 5 定理1 4 s 6 1 设g ( 坤) 是一h a l i n 图则存在一个内点w ，它仅与g 的另一 个内点相邻 定理1 4 9 6 】设g ( ) 是一h a l i n 图，g a ( 6 3 = 4 。贝1 1 x r ( 6 3 = 5 定理1 4 1 0 8 】若图g 是h a l l n 图，且( g ) 5 ，则州g ) = ( g ) + l 定理1 4 1 1 1 9 若图g 是h a l i n 图，且( q - - - - 4 ，则z “g ) = 6 ( 6 3 + l 定理l 4 a 2 1 0 1 若图g 是h a l i n 图，且( g ) = 3 ，则4 麒g ) 签 h a l i n 图是作为极小3 一连通平面图被引入的【1 1 】。它可以作为有较好的可靠 性( 3 一连通) 的最节省的网络模型，因而有较强的实际应用背景。文【5 】证明了 h a l i n 图是h a m i l t o n 连通的。通常的n p 完全问题在h m i n 图上可能不是n p 完全 的，文 3 】就是一个例子，它在线性时间内解决了h a l i n 图上的旅行售货员问题。 但在h a l i n 图上并不是所有的n p 完全问题都有多项式时间的解法。例如文 1 2 1 提到的有关子图同构和超图同构的问题在h a l 缸图上仍然是n p 完全的。文 6 - 1 0 1 1 1 3 1 7 较为完整的解决了h a l i n 图的各类着色问题。 1 5s t o i n e r 树问题的相关结果与进展 1 5 1s t e i n e r 树问题简介 1 7 世纪初，法国数学家f e r m a t 提出一个问题：平面上给定爿，口，c 三点， 试求第四点j p ，使之到三点距离之和晟小。1 6 4 0 年之前意大利数学家t o “i c e l l i 指出；以6 a b c 的三边为边长在a a b c 的外面各作一个正三角形，则三个正三角 形的外接圆交于一点p ，即为所求。该点称为t o r r i c e l l i 点。1 7 5 0 年，s i m p s o n 证明；对a a b c 所作的这个三角形a c a b ，凹“c ，鲋四c ，连接删，丑日，c c ， 则三线交于一点。1 8 3 4 年，e h e i n e n 证明了若z b e _ 1 2 0 0 ，则b = p 。1 9 4 1 年c o u r a n t 和r o b b i n s 在w h a t i s m a t h e m a t i c s 1 8 1 一书中指出平面上s t e i n e r 树问题是1 9 世纪 初由著名几何学家s t e i n e r 在对f e r m a t 的问题进行推广时提出的，s t e i n e r 树问题 的名称也由此而来。但事实上这是一个误会，问题其实是由j a m i k 和k o s s l e r 于 1 9 3 4 年提出能j 1 9 1 。 随着理论的发展和实际应用的需要，上个世纪出现了图上的s t e i n e r 树问题， 直线s t o n e r 树问题和其他形式的s l e i n e r 树问题，使得s t e i n e r 树问题成为组合优 化领域中一个十分热门的课题。 1 5 2 图上s t e i n e r 树问题简介 给定赋权连通图g = ( k 丘力，其中矿是顶点的集合e 是边的集合，d 是 9 中山大学博士学位论文h a l i n 图及小树宽图若i ：算法的研究 边的费用函数吐正- r 。5 是v 的子集，2 s l 司s i h 。s t e i n e r 树问题就是寻找g 的一棵子树t s = ( 矿，f ，曲，s o _ 矿ne e ，并且使花费吠r s ) = ，e r a ( e ) 最小 该问题在集成电路布局设计，通信网络设计与优化等方面有着较为广泛的应 用，尤其是在近年来日益兴起的网络多播业务中，s t e i n e r 树能使总耗费降低，大 大节省了对网络带宽的需求。 图论中对s t e i n e r 问题的研究可以追踪到1 9 6 1 年，k a r p 等在1 9 7 2 年证明了 最小s t e i n e r 树问题是n p 完全问题 2 0 1 。在平面图中它仍然是n p 完全问题。一 般图中，通常用启发式算法进行求解。如k m b 2 i i ，m p h 2 2 1 和a d h 2 3 。精确 算法主要有支撑树穷举法，拓扑枚举法等这些算法复杂性都是指数的： h a k i m i 2 4 ，d r e y f u s 和w a g n e r 2 5 ，l a w l e r 2 6 ，a n e j a 2 7 和s h o r e 2 8 都给出过 精确算法。对某些特殊的图类，例如系列平行图( s e r i e s - p a r a l l e lg r a p h ) 、强弦图 ( s t r o n g l yc h o r d a lg a r p h ) 等有多项式时问精确算法 2 9 】。w a l d 和c o l b o u m 3 0 把 s t e i n e r 树问题限制到外平面图上并给出了线性时间算法。文献3 1 1 1 3 2 对s t e i n e r 树的最优算法和启发式算法作了综述，其中有许多解决s t i n e r 问题的精确算法， 但精确算法的计算量部是随着网络节点的增加而指数增加，并不适应于网络多播 应用。， w i n t e r 3 3 给出了h a l i n 图上求s t e l n e r 树问题的线性时问算法。本文提出一 种不同于w i n t e r 的线性时自j 算法，但是谈算法明显1 七 3 3 1 简单并且更容易实现。 1 6 最大对集问题相关结果与进展 人员分派问题：某公司准备分派个工人x l 地，而傲n 件工作) ，l 以，枷， 已知这些工人中每个人都胜任一件或几件工作。试问能不能把所有的工人都分派 做一件他所胜任的工作? 这就是人员分派问题。 构作一个具有二分类的的偶图g ，这里j ，- m m 。而 ，y - 抄1 以，帅 ，并且研 与* 相连当且仅当工人而胜任工作咖于是问题转化为确定g 是否有完美对集 的问题。 最优分派问题：在上述问题中，还可以把工人们对各种工 乍的效率考虑进去 ( 也许这种效率可以用公司的收益来衡量) ，以便使得工人们的总效率达到最大。 寻找这种分派的问题名为最优分派问题。 考察一个具有二分类仪”的赋权完全偶图，这里 。净 j l 地而，y _ 沙i 以，帕 r 边珊有权”圹“x 。蝴，表示工人而做工作”时的 效率。最优分派问题显然等价于在这个赋权图中寻找一个有最大权的完美对集。 我们不妨称这种对集为最优对集。 这个问题可以扩展成在一个赋权一般图上求解一个最大权完美对集的问题。 e d m o n d s 3 4 给出了o ( 1 印) 的算法。文【3 5 g 面l 、m i e a l i 、g a b o w 设计了o ( 1 h f l t o g l 川) 的算法。本文中，我们把这个问题限制到h a l i n 图中，求解一个赋权h a l i n 图的 晟大权对集和最大权完美对集等。 1 7 树宽问题的相关结果与进展 十多年前r o b e r t s o n 和s e y m o u r 3 6 在建立图的m i n o r 理论时提出了树宽 ( t r e e w i d t h ) 及路宽( p a t h w i d t h ) 的概念，近来它们非常受重视，是研究的热点 问题。尔后从不同的应用背景也提出同样的参数，这说明树宽在应用上的广泛 性。如专家系统 3 7 1 ，电信网络设计【3 8 】，v l s i 设计【3 9 】等等。 树宽是一种测量图与树的相似度的参数。许多图都有常数上界的树宽。例如， 树和森林的树宽1 ，系列平行图和外平面图的树宽立，h a l i n 图的树宽玛。 一般来说，求图的树宽是n p 难题问题 4 0 】。在特定图上求树宽已经有大量 的研究了 4 1 4 5 】。对树宽= l ，2 ，3 ，存在线性时间算法 4 6 】。s a n d e r s 4 7 给出了 一个算法判断图g 的树宽是否最多为4 ，如果是，同时输出树分解。 定义1 7 i 图g = ( k d 的一个树分解m = ( 硝) ，j ，_ x , l i e z 及以，为顶点集的树丁， 满足：( 1 ) u j n ( 2 ) 对每一条边w 以g ) ，都存在i e l 使 u ，v 瑶m ( 3 ) 对任意i j , k e i , 若，处于树t 中从，到k 的唯一路中，则所1 忍竭 那么，图g 的树宽定义为t w ( g ) = m i nm a x i l 。 为了和图中的顶点区分开来，树分解中的树的顶点通常被称为节点。 定理1 7 1 1 4 8 】( i ) 当且仅当g 为树时，t w ( g ) = i ；( i i ) 若g 为k 树，则t w ( g ) = i ；( i i i ) 对圈有r 职c , ) - - 2 ；( i v ) 对轮有磁墨+ c = 3 ；( v ) 对完全图有r 职助 = n - - l ；( v i ) 对于完全偶图有t w ( k 。) = 州，月 定理1 7 2 4 9 给定图g 。 中山大学博十学位论文 h a nl 芏i 小树宽闰若下算法的研究 1 。图g 的任何子图的树宽最多是g 的树宽 2 g 的树宽是g 的所有分支中的最大树宽。 定理1 7 3 5 0 】简单图g ( k d ，令硷1 ，假设t r r ：( g 3 = k a 那么旧驯h - ( h “i ) ) 2 第2 章赋权h a l i n 图中的最大权对集问题 2 1 算法分析 图g ；( k 日，对任何s 坎g ) ，令j 表示一个端点在量另一个端点在h g ) - s 的所有边的集合。即o ( s ) = u v c e ：sv 毋。对于v gn 记j ( v ) 为j ( v ) 图 g 中，两个端点都在s 矿中的所有边的