（应用数学专业论文）qt图中的最小路覆盖问题.pdf

摘要 在一般霞中，最小路覆盖河题是n p - c 问题，即没有多项式算法。本文主要研究 q t 一图的最小路覆盖问题。通过研究q t 一图的特殊结构及其两种树代表系，本文分别 推出了两种多项式算法。 在第一章中我们对盯一图也构造一裸q t 一树作为它的树的表达。本章将从q t 一图 的姐一树入手寻找最小路覆盖，首先给出了嚣一图的嚣一檐的算法，得到鳃一树后，将 此树二分，根据二分凹一树的特殊性质，得到了凹一图的一棵路树，该路树经证明一 定不是伪路树，从而得到了q t 一图的最小路覆盖的一个多项式算法。 在第二章中我们对q t 一图构造一棵中心树作为它的树的表达。在中心树上，根 据每个节点的修币后的哈密尔顿标号，进行顶点移动。这罩我们将给出有用哑点树 即乙簸 的构造算法。最后在这操有用哑点树上应用d f s 方法进行搜索，从而德到 了q t 一图的个最小路覆盖。这里我们只考虑连通的q t - 图( 不连通的q t - 图可以看 作连通的q t - 图的并) 。则该算法同样也是一个好的算法。 关键词：q t - 图；最小路覆盖；q t 一树；路树；中心树 a b s t r a c t o ng e n e r a lg r a p h s ，t h em i n i m u mp a t hc o v e rp r o b l e mi sn p c o m p l e t e t h i st h e s i s m a i n l ya n a l y z e st h ep r o b l e mo nq t - g r a p h s w eu s et w om e t h o d st os o l v et h em i n i m u m p a t hc o v e rp r o b l e mo nq t - g r a p h sa n dg e tt w op o l y n o m i a la l g o r i t h m s i nt h ef i r s tc h a p t e r , w ec o n s t r u c taq t - t r e eo nt h eq t - g r a p ha si t st r e er e p r e s e n t a t i o n w eb e g i nt h i sr e s e a r c ho nt h eq t - t r e e s of i r s t l yw ew i l ls h o wt h ea l g o r i t h mt oo b t a i nt h e q t - t r e e a n dt h e nb i n a r i z et h i st r e e a c c o r d i n gt ot h es p e c i a lp r o p e r t yo ft h eb i n a r i z e d q t - t r e e ，w eg e tt h ep a t ht r e ew h i c hc a n tb eap a s e d o t r e e f i n a l l y , w eg e tap o l y n o m i a l a l g o r i t h mt os o l v et h em i n i m u mp a t hc o v e r o nq t - g r a p h s i nt h es e c o n dc h a p t e r , w ec o n s t r u c tac e n t - t r e eo nt h eq t - g r a p ha si t st r e e r e p r e s e n t a t i o n o nt h ec e n t t r e e ，w ew i l la p p l yv e r t i c e s m o v eo p e r a t i o nb e t w e e nt w o n o d e so ft h et r e ea c c o r d i n gt ot h em o d i f i e dh a m i l t o n i a nl a b e l h e r ew ew i l lp r e s e n tt h e a l g o r i t h mt of i n dt h ea v a i l a b l e d u m m yt r e e 乙( g ) o ft h eq t - g r a p h f i n a l l y , s e a r c hf o r t h em i n i m u mp a t hc o v e rp r o b l e mo nt h eq t - g r a p hw i t had e p t h - f i r s ts e a r c ht r a v e r s a l s t r a t e g y h e r ew eo n l yc o n s i d e rt h ec o n n e c t e dq t - g r a p h s ( t h eu n c o n n e c t e dq t - g r a p hi s t h ec o n j u n c t i o no ft h ec o n n e c t e ds u b g r a p h sw h i c ha r ea l s oq t - g r a p h s ) t h i sa l g o r i t h mc a n b ep e r f o r m e di np o l y n o m i a lt i m e 。 k e y w o r d s ：q t - g r a p h ；t h em i n i m u mp a t hc o v e r ；q t - t r e e ；p a t ht r e e ；c e n t - t r e 青冬大学硕士学位论文 学位论文独创性声明 本人声明，所里交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法弓| 用他入成果，均嚣作出明确标注或得到许可。论文内容未包含法律意义上己 属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。 本人如违反上述声明，愿承担由此引发的一切责任和后果。 论文作者签名： 享胖 f 露期：媚群多月妒甚 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅、以及申请专利等权利。本人离 校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然 为青岛大学。 本学位论文属子： 保密口，在年解密艨适用于本声明。 不保密函。 ( - i , l 在以上方框内打“弹) 论文作者签名： 导师签名： 害牌 l、l 许议 i ：t 期：知呱净 日期：智年 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个入不得擅自使用) 弓l 言 引言 图论的产生和发展历经了二酉多年的历史，现阶段由于生产管理、军事、交通 运输、计算机和通讯网络等方面许多离散性问题的出现，大大促进了图论的发展。 进入上世纪七十年代以后，特别是大型电子计算机的出现，使大规模问题的求解成 为可能。图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控 制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面应用的研究都 得到“爆炸性发展 ，主要有以下三个原因： 童圈论提供了一个裔然的结构，由此丽产生的数学模型几乎适合于任何科学( 自 然科学和社会科学) 领域，只要这个领域研究的主题是“对象”与“对象”之间的 关系。 2 图论已经形成自己的丰富词汇语言，它能简洁地表示出各个领域中“对象关 系”结构复杂丽又难懂的概念。 3 图论提供了大量令人跃跃欲试的智力挑战性问题。 而本文中所要讨论的最小路覆盖问题是图论中优化问题的一个分支。它是指在 一个图g 中找出基数最小且点不相交的路的集合，使其覆盖g 的所有顶点。该类问 题在数据库设计、网络问题、v i s l 设计即超大规模集成电路设计、环协议、代码优 化等闻题中都有广泛应用。众所周知，最小覆盖阀题和它的许多变形问题在一般图 中都是n p - c 问题，见r l i n t 引。实际上，当最小路覆盖的基数是1 时，该类问题就 转化为寻求图g 的哈密尔顿路的问题。在一般图中哈密尔顿问题就是n p c 问题，因 此最小路覆盖问题对于一般图自然也是n p c 的，但在q t 一图中，我们经过研究发现 它的最小路覆盖问题却有多项式时闽算法。 q t 一图是键珏8 s 主一t h r e s h o 羔dg r a p h 的简称，它是完美图中广为人知的一类图，圊 时也是有着重要研究意义的一类图。它的重要性体现在：一般图中的n p c 问题在 q t 一图中却可以在多项式时间内求出解。马绍汉1 9 1 就给出了一些优化问题的多项式算 法，包括它的辨认问题的o ( m n ) 时间内的算法、哈密尔顿圈问题的多项式时间算法 和带宽闻题。颜经和1 4 1 中指骥了该类图的重要性质及辨认它的线性算法。 o t - 图中的哈密尔顿问题在并行程序环境下的研究并不多，但是余图中该类问题 已经可以通过一系列序列和并行算法得到它们的算法解。这也使我们对它的予类图 叫t 一图的优化问题的算法的研究充满期待。 余毽( c o g r a p h ) 是圭l e r c h s t 8 l 予七十年代初期弓| 入的一类图，并给出了它的结构 和算法性质，其中有两个很好的性质： 1 青岛大学硕士学位论文 ( 1 ) 余图中不含鼽( 即假定每条边长都为1 ，胁就是长为4 的路) ； ( 2 )同构意义下每个余图都有唯一的树代表系一余树。 透过余树的建立，e 。d a h l h a u s o o l 给出了辨认一个余图的线性时闽内的序列算 法。我们也知道在多项式时间内用多项式个处理器霹以用并行算法有效( 但不是最 优) 地辨认一个余图见e d a h l h a u s ( 旧l ，x h e ( 1 ，r 。l i n 5 1 。丽实际上h ec 1 进一步 给出了一个几乎是最优的并行算法来解决余图辨认和余树的构造问题，该算法复杂 性是o ( 1 0 9 2 丹) ，其中n 是顶点个数，m 是边的条数( 以下也如此表示) 。d a h l h a u s f m 】 也给出了一个接近最优并行辨认算法，该算法复杂性与 e 翻中的算法复杂性一样。 本文的主要工作是要从两个角度对q t 一图的最小路覆盖问题进行研究，并推出 两种多项式算法。 1 我们根据q t 一图的定义及其构造方式，可以对q t 一图构造一棵q t 一树，将此q t 一 撵二分，根据二分姐一树的特殊性质，得到了婀一黉的一棵路树，该路树我们可以证 明其一定不是伪路树，蔼路树经欧拉迹技巧可以生成原图中的一个路覆盖，从丽得 到了q t 一图的最小路覆盖的一个多项式算法。 2 我们对q t 一图构造一棵中心树，根据每个节点的修正后的哈密尔顿标号构造 一棵有用哑点树，在这棵树上应用d f s 方法进行搜索，从而得到了它的一个最小路 覆盖。这里我们只考虑连通的甜一圈( 不连通的酊一图可以看作连通的盯一图的并) 。 该算法也是一个多项式算法。 2 第鬻臻甜一树求娜甜一黼熬最，j 、潞覆攘润鼷 第一耄用o t - 树求解o t - 圈的最小路覆盖问题 本章中我们用凹一图的一种树的表达法啜l 一树对冀最小路覆盖进稽求解。 。1q t ：4 树的知识背景 酋先在引入o t - 树的概念之前要介绍下q t - 蹦的概念及性质。 定义1 1 1q t 一图霹以如下递烟地定义为： ( 1 ) 个单点图是q t - 图； ( 2 ) 在原圈中加入一个耩点，使之与原图中所有点都捆邻； ( 3 ) 不榴交熊两个嚣一圈的并也是艘一图。 定理1 薹薹( j i n - h o y a n1 4 】) 一个图是簖一圈巍且仅当它不包含鸯鼓蠛q 瀚 构的导嫩予图。其中，疋表示4 个顶点的长为3 的秃弦路，q 表示唾个顶点的长失 4 的无弦圈。 根据q t 一图的定义及其构造方法，我们可以构造它的一个0 1 树的表达滋，这 里我们就称这耪0 - 1 树的表达为鲫一树，记俸( g ) 。在树中0 节点表示它的几予之 闻是不连通的，丽鑫ll 节煮所表示的j 毛子之瓣是连道的。因此整檬辩实际上就是姆 图中顶点之蚓的连通关系的表示。因此每个o t - 圈在同构意义下都对应鏊唯的 棵q t 一树t ( g ) 。q t 一树r ( g ) 拥有如下基本性质： 性震1 1 。lr ( g ) 的每个中间点都至少有一个j k 予； 性质1 1 2r ( 爵) 的中闽点都标记为0 绒l ，从根节点开始的每条路都是0 和 l 交错出现； 性质童。1 3r ( g 的每一个叶子都对照羲顶点集v 中憋个顶点，藤盛 ( x , y ) 毯e 当且仅警对戚着x 和y 的两个叶予的最低共同前辈是l 。 为了更清楚地理解q t - 图的r ( g ) 的定义，我们用下图来表示： 3 青岛大学硕七学位论文 鬈 q t - 圈 b d g a b q t - 图对威豹q t - 树 图1 1 上图中，左图是一个船一圈，右圈是它的q t - 树。 对于连通的毁一图，它的啦一树的根节点一定为l ；不连通的凹一图，它麴甜一 树的根节点一定为o ，即它的q t 一树实际上是它的连通分支的q t 一树的并。因此以下 我们只对连通的q 1 一图求q t 一树。根据定义1 1 ，我们知道对于连通的q t 一图，至少 存在一个顶点的度为r i - - l ，设为h ，屹，一，其中1 ，栉。当f = n 时该图就是一个 完全圈，簖一树的根节点l 的儿子是全体顶点；当i 雾捍时，它的q t 一树根节点1 的儿 子是一个0 节点和技，码，麓所表示的叶子，其中l f 嚣。根据嚣一图的定义可知， 在q t 一图中去掉k ，屹，剩下的图是不连通的凹一图的并。若这些连通分支是个 孤立点和p 。个连通分支，则o 一节点的儿子也确定下了，就是p ；个卜节点和f 1 个孤立 点所表示的叶子。在p 1 个连通分支中分别应用以上方法分别搜索它们的儿子，依次 类推直到最后一个节点的儿子都是町一图的顶点，从而得到整棵酊一树。 下面对予连通的鳃一图g ，我们给出鲫一圈的西一树r ( g ) 的算法： 算法1 1 1 求q t - 树的算法 1 确定q t - 树根节点为1 ： 2 求出q t 一图g 的所有顶点的度，删掉度为封一1 的顶点，设为嵋，屹，k ，其 中l i 嚣，得到圈g 1 = g l lu 6 , 2u u a , nu v l lu v l 2u u v , ： 3 在凹树中加边l g ，l 毽，i v , ： 4 确定0 节点的儿子为p 1 个l 和毡l ，k 2 ，h 。，在q t 一树中加边：崩条o l 和 o h i ，0 v 1 2 ，0 h l ； 5 下边l 节点的后代的确定实际是各个连通分支再分别进行第二步到第四步， 直至凹一图的所有顶点都转换为鳃一树的叶子为止。 4 第一章用q t - 树求解q t 一图的最小路覆盖问题 该算法的复杂性为用o ( ( n + m ) l o g n ) 个处理器在o ( 1 0 9 2 n ) 时间内在戤嚣矽模 型上求出。参见文献r l i n t 5 1 1 。2o t - ：- 树的二分及约化 路树是在二分树结构下求出的，因此在求路树之前要将上节所得到的q t 一树进 行二分，二分树的算法参见文献k o j in a k a n o 1 3 1 。- f 面我们将t ( g ) - - 分，刘图量。2 中q t 一图的q t 一树t ( g ) 就变为t b ( g ) ： a g 图王。2 对于瓦( g ) 的中间节点甜我们将它的左儿子和右儿子们分别记作v 和w 。瓦( g ) 中 醒点的后代在g 中的导出子图记为g ( u ) 。且用l ( u ) 记瓦( g ) 中毅点的后代的数量， 郎g ( u ) 中的顶点个数。相应缝，用l ( v ) 和联砷分别记为g 妒) 和g ( w ) 中的顶点个数， 如果三( 1 ，) l ( w ) 就说5 ( g ) 是左的，记作瓦，( g ) 。 引理1 2 。l ( k o j in a k a n o 旧1 ) 对( g ) 的每一个中间节点嚣，最小路覆盖的路 的数叠p ( u ) 可以在o ( 1 0 9 n ) 时闻内求渤。 现在我们对1 ( g ) 进行进一步修m 。q t 一图的顶点即瓦，( g ) 的叶子可以分为如下 三类： ( 1 ) 桥顶点：在l 一节点将两条路连接起来的顶点； ( 2 ) 插入顶点：在卜节点插在路中的顶点； ( 3 ) - 基本顶点：除了桥顶点和插入顶点的其他顶点。 注意到每一个桥顶点和插入顶点都在一棵以卜节点的右a 子为根节点的子树 上，丽其他顶点显然没有这种特征。瓶对于蠢，( g ) 的每一个l 节点“来说，以右儿 5 青岛大学硕士学能论文 子w 为根节点的子树的结构是不重要的，这是因为g ( w ) 中的顶点都被用来做桥点或 插入点，使得g ( w ) 中的边不能出现在路覆盖中。因此瓦，( g ) 可以被约化为瓦，( g ) 。 原先的瓦，( g ) w 、， 圈1 3 修正后的( g ) 3 有关路树的知识背景 这一节中我们就要引入路树这一概念以使寻找最小路覆盖问题有最优时间算 法。 首先，介绍一下深度优先搜索中的三种搜索方法：先序遍历、中序遍历、后序 遍历。例如给出如下一棵用数字表示其节点的带根生成树： 图l 。凄 先序遍历的搜索顺序是：l ，2 ，3 ，5 ，8 ，9 ，6 ，l o ，4 ，7 中序遍历的搜索顺序是：2 ，l ，8 ，s ，9 ，3 ，l o ，6 ，7 ，4 后序遍历的搜索顺序是：2 ，8 ，9 ，5 ，1 0 ，6 ，3 ，7 ，4 ，i 下面简单介绍一下欧拉迹技巧的具体方法。开始之前，我们把有a ( u ) 个儿子的 6 第一章用妪一树求解飒一型静最小潞覆燕闷题 节点材用( 据) + 1 个龆的拷贝来代替，标记为拉1 ，列2 ，豁d 轴m ，接下来，令_ ，鹄，w a 代表f 中u 的儿子们，其中w , o 筵i 矗辑羚宥令儿子，则对于所有的i _ l ，2 ，露 ) ： 辑( ) 拦w t l 杼( 毽碡) = u 鲥 假设r 的裰有f 个j 毛予，那么经过欧糍技巧变换惹我稍就褥到了这样一个链接起 来的序列：超始子根f ) l ，终止子掇( f 一，且的每一条边在每个方向上都经过 次。因此，褥到的链接序列总长为p ( 娌) 。下图就给出了树，用该方法得到的欧拉迹 l ( t ) 的演示： 、 树r 豳l ，5 e f 9 1 h i 欧搬迹五( r ) 对于树f ，上述方法在o ( 1 0 9 n ) 时间内就可以求如它的欧挝迹l ( t ) 。 定义羔3 1设g 是个簖一图，路树是一棵带搬的二分树且它的每个节点都对 应着匿g 的菜条路霈上的颟点，其中路帮是由路楗经过中序遍历搜索得到盼。 如下图就绘出了路树秘中序遍历得到路的演示： 7 青岛犬学硕士学位论文 a g 路树 h 图1 6 路树对应的游历 根据上述欧拉迹技巧，我们可以将已经得到的路树转化为一条确定的路，脬棵 点不相交的路树对应着胛条点不相交的路。设瓦，( g ) 的中问节点的左儿子和右儿子 分别是v 和w 。下面我们就用得到的v 和w 的导出子图g ( 1 ，) 和g ( w ) 求出g ( u ) 的一棵 路树。 算法l 。3 。l 求路树的算法 1 判断u 是o 一节点还是卜节点； 2 假如u 是一个0 一节点，且g ( v ) 和g ( w ) 的路树都已经得到了。由于g ( v ) 和 g ( 叻之间在图g 无边相连，则g ( ，) 和g ( 奶的路树的并就是g ( u ) 的路树； 3 假如u 是一个卜节点，且g ( 驴) 和g 哟的路树都已经得到了。我们需要考虑 以下两种情况： 第一种情况：p ( v ) 三( 忉。g ( 们中的( w ) 个顶点都作为桥点连接起( w ) + l 条 路，生成的g ( u ) 的最小路覆盖中含有p ( v ) 一三( w ) 条路； 第二种情况：p ( v ) 五( w ) 。如图1 8 所示，g ( 叻中p ( v ) - 1 个桥顶点按照第一 种情况的方法连接g ( y ) 路树的根。 对于第一种情况，下面我们来具体描述一下这个过程：首先，用g ( w ) 中互( 奶个 顶点建立一棵二分树，然后，将g ( 1 ，) 的( w ) + 1 棵树的根连接到刚得到的二分树的 叶子部位。这一过程我们用图来表示如图： 8 a b c d e f g h 第一章用舔一树求解甜一圈的最小路覆盖问题 a c b a 4 a 图1 7 c bcde 图1 7 中用口，b ，c 建立一棵二分树，然后将b ，c ，d ，e 的根分别作为a ，b ，c 的儿子。 则中序遍历路树得到路：艿_ c c b 专d aoe ；对予第二种情况，在下图 l 。8 中，两个顶点a 和b 连接了3 棵路树。三( 计一p ( v ) 1 个撬入点中的每个顶点在薪 路树中都作为叶子出现。 蠢 4 坞 遐 红 羁 q g b 图i 8 g f e 注意到在第二种情况中，如果将g ( w ) 中剩余的顶点无序的插入到路树中时，就 有可能使g ( 奶中原先不相邻的硒个顶点有边相邻，这样德到的路树我们就称之为伪 路树。如上图路树中若将g ，f ，e 按上图中路树放置，就会导致与掰相邻，a 与g 相 9 4 g b f e a d c 青鑫大学硕士学位论文 邻。而实际上出现这种状况的原因是我们在建立，( g ) 时以忽略了g ( w ) 中的顶点之 间的关系。而实际上g ，f ，e ，d ，c 应该如图1 9 放置： 以 4 驾 琏 岛 g g b 图1 9 c 1 。4 寻找最小路覆盖 透过观察解一颦的龃一树，我嚣j 不难发现： 定理羔。4 。圭不，( g ) 的任何l 一节点的右歹l 子都是叶子。 证明：设图g 为酊一图，霸( g ) 为g 的左二分酊一树。自嚣，( g ) 的构造可知以它 的每个中间节点为根的子树所代表的子图也是q t - 图。 不妨设瓦( g ) 有一个卜节点的左子树代表的图是q t 一图，而它的右儿子不是叶 子，则卜节点必有一个o 一节点为根的子树作为它的右儿予。这说明至少有两个连通 分支与卜节点的左儿子中的每个连通分支都有边相连。而根据q t 一图的定义可知： 两个不相交的艘一圈的并是酊一图，如果是连通的酊一图，则必须加入新点使其与原 先所有点都有边相连。因此l 一节点的右儿子只能是一个叶子或者一个团。团在龌一 树中的表示就是以l - 节点为根而其它节点都是叶子的子树。口 因此我们可以省掉将瓦，( g ) 进一步约化为( g ) 这一步骤，即算法1 3 1 中的 第二种情况可以不考虑。这是因为假若既约的左二分树中，卜节点的右儿子w 中的 顶点之闻结构不明确，酃它们之间的关系是极可能相邻也可能不相邻，这是由一般 图的结构性质决定的。面对于那些不相邻的作为插入点的顶点无序地连接到路树中 时就有可能相邻，从而成为非法儿子。 1 0 b g f a e d c 第一章雳酊一树求解毂一圈豹最小路覆盏问题 定义1 4 王菲法歹乙子是有下列特点的顶点： ( 1 ) z 的最右边顶点的右夕l 予； ( 2 ) l 的最左边顶点的左儿子。( 1 i p ( v ) ) 其中夏，互，乙，记作路树中从左到右 顺序排列的子路树，且它们的根由p ( v ) 一1 个桥点连接起来。 这里最右边顶点也就是出现在中序遍历的最后面的顶点，见r l i n 6 i 。 这些非法儿子的无序插入，打乱了原先的顶点之间的连通关系，从而造成伪路 树的产生，即该路树不能表示原先的图。而在o t - 图中情况就大不一样了，这是因 为嚣f ( g ) 的任何l 一节点的右j l 子都是叶子，而卜节点决定了这些叶子所代表的顶点 之间是团结构，郎任何两个顶点都栩邻。这点就使生成伪路楗的条件完全不存在了。 下面我们用图来表示q t - 图中用q t - 树来寻找最小路覆盖问题的过程。 a b 图1 1 0 ：q t 一图 g 图1 1 h 丁( g ) 根节点1 一节点的g ( v ) 的路树及g ( 叻中的顶点如下图1 1 2 所示： 青岛大学硕士学位论文 g ( v ) df h 图1 1 2 g ( 协 i o l0 如图1 1 0 l 。1 2 所示，该凹一图得到的路树只有一棵，说明路覆盖的基数为l ， 即此q t - 图是哈密尔顿q t 一图。下面我们给出用q t - 树求q t 一图的最小路覆盖问题的 算法： 算法圭+ 4 。l 用鲣一树求最小路覆盖的算法 输入：q t - 图g 的一棵q t - 树 输出：g 的一个最小路覆盖 l 寻找二分酊一树五( g ) ； 2 慰互( g ) 的每一个中间节点豁，计算如g ( u ) 中顶点酶个数毛( 豁) 和左二分树 z b l ( g ) ； 3 对毛( g ) 的每一个中间节点l l ，计算出g ( u ) 的最小路覆盖的基数p ( 默) ； 4 生成g 的路树： 5 翔欧拉迹技巧扶路树褥到一个最小路覆盖。 1 5 算法的复杂性分析 引理1 5 1 ( g u o j i nc o n g1 1 5 i ) 给出一棵树丁的邻接矩阵和一个根节点足，下面 的各项都可以用n l o gn 个处理器在o ( 1 0 9 n ) 时间内在e r e w 模型上求出： l 计算z 的欧拉迹； 2 给出? 中每个顶点豁先序、中序和后序的数露； 3r 的每个中间顶点u 的后代数目和后代中叶子数目。 定理1 5 1 一个q t 一图g 的最小路覆盖问题可以用o ( n l o g n ) 个处理器在 o ( 1 0 9 n ) 时间内在e r e w 模型上求出。 证明假定q t 一图g 的顶点数为n ，边数必m 。? ( g ) 的邻接矩阵给定，由 1 2 第一章用q t 一树求解q t 一图的最小路覆盖问题 k a b r a h a m s o n1 1 5 中的证明可知算法中二分t ( g ) 可以用o ( n l o g n ) 个处理器在 o ( 1 0 9 n ) 时间内在e r e w 模型上求出。由引理1 2 1 ，第二步中计算t ( u ) 中的节点 在g ( “) 中的救目和计算出左二分树瓦，( g ) 也可以被最优求解。第四步可知是路的收 f 缩和树收缩的一个特殊例子，可以由算法1 3 1 用o ( n l o g n ) 个处理器在o ( 1 0 9 n ) 时 间内在e r e w 模型上求出。最后第五步实际上是计算欧拉迹，由引理1 5 1 可知在 用o ( n l o g n ) 个处理器在o ( 1 0 9 n ) 时间内在e r e w 模型上求出。口 1 3 青岛大学硕学位论文 第二章用中心树来求解0 t - 图的最小路覆盖问题 本章中我们用另外一种树的表达法即n i k o l o p o u l o s 嘲中创立的中心糖来探索 q t 一图最小路覆盖问题。在此我们只考虑凹一图g 是连通的情况( 不连通的g 的最小 路覆盖是各个连通部分最小路覆盖的并) 。 2 。1 基础理论引入 图g 的顶点集合用矿( g ) 表示，边集合用e ( g ) 表示。燹| j 一个顶点x v ( g ) 的邻 集( x ) 即为与x 相邻的所有顶点的集合，x 的闭邻集定义为【x 】= x 1 j n ( x ) ，图g 的中，bc e n t ( g ) ：= x v ( g ) ln x 】= y ( g ) ) 。 引理2 1 1 ( n i k o l o p o u l o s1 6 1 )图g 是无向图 ( 1 ) g 是q t 一图当且仅当它的每个连通的导出的子图g s 】，s v ( g ) 满足 c e n t ( g s ) 彩； ( 2 ) g 是盯一图当且仅当g v ( g ) - c e n t ( g ) 】是一个町一图； ( 3 ) 对予连通的篮一图g 来说，如果矿( g ) 一c e n t ( g s ) 彩，燹a j g v ( g ) 一c e n t ( g ) 】至 少包含两个连通部分。 假定g 是连通的q t 一图。由引理2 1 可知k ：= c e n t ( g ) 非空，定义g l ：- g ，且 g v ( g ) - v ，】_ g 2ug 3 u ug ，其中每一个q 是g v ( g ) 一“】的连通分支，并且 r 3 。由于每一个g f 都是g 的一个导出子图，因此q 也是一个解一图，则 警c e n t ( g j ) 警彩，2 ；r 。由于g 【y ( q ) 一c e n t ( g i ) 】的每一个连通分支也是一个鳃一 图，因此我们可以不断重复这个过程直至撂到一个空图为止。经过以上步骤我们最 后得出了v ( g ) 的划分：v ( g ) = k + 以+ + 圪其中形= c e n t ( g i ) 。 我们还可以在 k ，吒，圪) 定义一个顺序 ：当k 兰c e n t ( g ，) ，若_ 矿( q ) 时 巧巧。 设g 是一个连遵的q l 一图，v ( g ) = k + 坞+ + k 是上述定义下的划分；其中 k = c e n t ( g ) 。则这种划分顺序集合( i ，_ ) 有如下 生质： 性质2 1 1 如果巧 屹，则的每个顶点和屹的每一个顶点在g 中都有边相 恁： 1 4 第二章焉中心树隶解舔一图静最夺路覆盏问题 性质2 1 2 对每个巧，c e n t ( g u v , i 杉 巧) 】) 巧； 性质2 1 3 对满足k 形的每个k 和k ，g u kl 圪_ 形qk ) 】是一个完全图。 而且集合( k ，一 ) 中的最大元素k ，g 【 u kik i 8 1 ，则此q t 一图必有一条哈密尔顿路。以下我们只考虑根节 点中的顶点数小于等于其余节点中顶点之和的情况。下面我们就开始用新方法搜索 凹一图的最小路覆盖。 令g 是一个q t 一图，令巧，致是中心树7 0 ( c ) 的各个节点，根节点墨= k 。 考虑疋( g ) 的一个节点形，令k 。，k 2 ，( 1 f j | ) 是它的儿子，其中i v , 是节点l 的 儿子的数目；注意到如果不是一个叶子，则n 2 ；否则历= 0 。我们给节点k 设 1 6 第二章用中心瓣求瓣鲫一图的最，l 、路覆盖闷题 置一个哈密尔顿标号，简记为h l a b e l ( v ，) ，1 i k 。它的计算方法如下： f| v , - p ，如果形是树的根 h - l a b e l ( e ) = i z , l - p , + l ，如果k 是树的中间节点 i0 ，如果k 是树的叶予 圈2 3 如上图所示：图为中心树的一个节点和它妻鼋儿子k 。，：，和鬈。；若是 树的搬， 则h l a b e l ( v , ) = 5 - 4 = 1 ，若是树的中间节点则 h - l a b e l ( v j ) = 5 - 4 + 1 = 2 。其他点的哈密尔顿标号为h - l a b e l ( v i i i ) = 2 - 2 + 1 = 1 ， h - l a b e l ( k 2 ) = 1 - 3 + 1 = - 1 ，h - l a b e l ( v f ，) = 0 ，h l a b e l ( v ，4 ) = 1 - 2 + 1 = 0 。 下面我们就将证明如果对每个k 都有日一肠6 p z ( k ) o 成立，则g 是一个哈密尔 顿图，即g 含有一条哈密尔顿路。 设k 是中心树r a g ) 的一个中间节点，且h - l a b e l ( k ) 0 ，有儿子 巧l ，形2 ，其中b 2 。由于k 是中间节点，且h - l a b e t ( v , ) ：l w , i p i + 1 o ， 则k 中至少含有只一1 个顶点；令序列( ) = ( ，魄露_ l ，) 为节点的顶点 序列，其中臻只一1 。我们定义k 的有用顶点序列( ) 警( ，k 拜+ 1 ) ，) ：如果形 是中心楗的掇节点，则的有用顶点序列( ) 海( 辫+ 1 ) ，k 厢+ 2 ) ，) 。在图2 3 墨中 间节点的有用顶点序列( ) 嚣 豁，v ) 。 设中心树i ( g ) 的叶子按从左到右顺序排列依次为( i ) 巧( 2 ) 一，巧( ，) 。令( f ) 是 节点巧( 订和( ) 的最低共同前辈，其中1 f f 一1 。 1 7 青岛大学联七学袋论文 定义2 2 。熏中心树霉够) 翡节点序鳓霹： h - r 葶y , j ( r o ) - ( v ：( 1 ) ，屹( 1 ) ，_ ( 2 ) ，圪( 2 ) ，匕i f ) ，圪( f ) 篇k ) ，其中k 是t ( g ) 的根，是疋( g ) 的时子数罄；殿霉够) 的蠢一序列长势2 。 i 由定义2 。2 1 可知， 一序列( 艺) 中的任何耀个霓素学妒喾歹t 另外，存 在妒圪逸”，圪钿使樽。娑鬻钿= 成立，其孛鬈是乏籍鹃个孛 f b - j 节点r p 是辑的j l 予数糕设) 耱嚷钿，分剃是蠢一序列辑) 懿形中窭现蛉最发迭 下标帮最右边下标显，岛镶钿，烈说甓匕i l ，蹩第一个纛魏在髟的元素， 艺 如) 是第二个，按诧颥痔依次往下摊，圪铀) 是最爝一个豳琥的元豢。搬据率心树 l ( g ) 的每个中间节点在螽一序列( ) 中至少出现次。我们得出以下结论： 定理2 2 20 t 一图的中心树乏( 卿韵所有节点都出现在磊一序列识) 中。蒜凰， l 一序列( 笑) 的任何蹲个节点都是团相邻的。 证明：设纛一序戮( 1 ) 篇撵，妒辫，：，吩瓣，= 嚣，昂，聪是孛 心树疋g ) 的带点e 出定义可知，节点巧，l ，淄，吩瓣是t a g ) 蜂予献左到骞的摊裂， 繁点磅是节点嵇黧匕麓最羝共溺纛辈。粼r a g ) 魏所有繁点都出现在 纛一序列( 瓦) 串。 蟊一序捌瓯酌两个连续节点，略 砖翔围或者琢和巧矧是豳搁邻的，这也因 为圪( i ) 的节点是( f ) 和吩) 的前辈，即圪，) _ _ ( j ，圪( i 叫吩训l 口 令，k ，礁是娥一图g 熬中心树嚣( g ) 鲮繁点n 下面我们餍d f s 方法( 郎深 度优先搽索方法) 来研究豳g 的顶点期杉的每个琰点，并建立一棵深探法褥到躲 树。根据壳一序烈乏( g 势我镌可| 良选爨还岽经过的顶点，因此裁构造港了啥密尔顿深 探法，祷谴鸯舞一殛。其体攘索方法翔下： 1 8 第二章用中心树求解q t 一图的最小路覆盖问题 算法2 。2 。圭晗嚣尔顿深探法的算法 1 找出中心树咒( g ) 的办一序列( 瓦) = ( 吩( 1 ) ，屹( 1 ) ，( ：) ，虼【：，v f ( o , 圪= 巧) ； 2 从吩1 ) 中任选一个顶点v 作为搜索起始点，并作上搜索过的标记； 3 依次搜索2 ) 的未搜索的顶点_ ，1 f ，并作上搜索过的标记； 4 ( f ) 的所有顶点都搜索完毕之后，再对圪( f 进行如下操作： 如果在圪 ) = 中的顶点毡未被搜索，则选出，并做标记；如果屹1 ) = 是 厅一序列( 瓦( g ) ) 中出现的最右边的元素，则依次搜索它的所有未搜索的顶点，并作上 标记； 若圪一中的所有点都已被搜索，则完成。 5 继续上述过程，直至根节点圪= k 中的最后一个节点豁也被搜索完毕；如 果i = = 圪o ； = k ，l f 惫。 由于日- l a b e l ( v i ) 0 ，说明节点k 至少含有只一1 个顶点；若i = l ，则k 中至少 含有b 个顶点。令伟为k ( g ) 的顶点数目，则杉的顶点序列为 娥，溉州，_ 辫，、) 。 从m 中选择一个顶点v ，我们完成了麸v 开始昭一个磊一够搜索。出于每一个 节点k 包含至少a 1 个顶点( 如果= 残，则包含只个顶点) ，这表明搜索完节点国 的顶点后，在，) 中至少存在一个没有搜索的顶点，因此| f l 一够可以再从屹( i ) 的这个 顶点开始继续搜索，1 f f l 。当然在( ) 和k ( ，) = k 中也是这样。 又由定理2 2 2 可知圪( 力和( i + 1 ) 是团相邻的，舭h - d f s 是树中的每一个节点 都至多有一个儿子，郎g 包含了一条哈密尔顿路，因此它的最小路覆盖基数为1 。 由于k 是i ( 回的辗节点，焉且k 一i ) ，则，与k 是透相邻的。因此g 包含了一 个晗密尔顿圈。口 下面我们考虑另一种情况：对乏瓣) 中的节点z 和l ，虽 0 且岸一l a b e l ( ) 0 。设材是节点的一个有用顶点，当我们说要把 有用顶点u 从k 顶点移动到以中，即表示我们要进行以下两步操作： ( 1 ) 从巧中删除顶点u ； ( 2 ) 将掰添加在节点中。 用图表示就是： 。 2 0 第二章用中心树求解q t 一图的最小路覆盖问题 图2 5 从q t 一图g 的中心树t ( g ) 的构造来看，容易看出，如果我们在和吒之间应用 顶点移动操作，则得到的树将会有以下性质：对每两个满足k k 的节点圪和， g 【 u | 以杉) 】是一个完全图。显然，如果是( 巧 ，一) 中的最大元素，剩应用 顶点移动之后，图g u ik 形 】就可能不是一个最大完全图。 定义2 2 。2 舔一图g 的中心树嚣( g ) 的适当节点运用顶点移动后使得树的每个 节点h - l a b e l ( v 。) 0 ，我们把这样的树称为哈密尔顿树，简记为瓦( g ) 。 首先，我们在诧将s t a v r o so n i k o l o p o u l o s1 6 l 中的嚣一l a b l e 修正为 f 0 ，如果v i 是叶子 h - l a b l e , 一肠6 抬= l l v , 1 + l ：如果y 是藻孬享五夕l 卜晶其他节点 定义2 2 3 在寻找船一图中啥密尔顿路时应用d f s 方法时，当遇到h + 一f a b l e 小 于0 的节点时，可以向它的前辈借节点下来补充，所借到的点就是可用点，而需要补 充的点就是哑点。经过这样的操作厝得到的中心树的变形我们称之为有用哑点树， 记作( g ) 。 2 l 毒岛太学颈士学愆论文 图2 6q t - 图的中心树 图2 7 q t 一闰的( g ) 图2 6 就是一棵中心树，露图2 。? 就是一棵有用哑点树。墅2 + s 第二层中左起 第一个节点的烈一l a b l e 小予0 ，其余点的h 一l a b l e 都大予等于0 ，它就可以向它的 父辈借点下来补充，图2 6 中的黑点就是根节点中的有用点。豳2 ? 中的黑点就是 它的哑点，即哑点。 假设中心树i ( g ) 已知，下面给密乙( g ) 的构造算法： 算法2 2 2 1 计算乏( g ) 的每一令节点酶修正薏的哈密尔顿标号，并标出嚣- l a b l e d 0 的节点； 2 若量 - l a b l e ( v ；) o ，刚在孛翔入| h - i a b l e ( v , ) | 个顶点，使其 第二章溺中心树求辩蕊一图酶最小路覆盖闻瑟 h - l a b l e ( v j ) = 0 ； 3 在k 的父辈节点中删除1 日+ 一肠6 胞( k ) 1 个顶点，不够的用空心顶点表示，在计 算它的新的修_ 正后的哈密尔顿编号时，空心顶点的值为一l ； 4 重新计算所有节点的h 一l a b l e ，继续第一步和第二步的操作，盔至所有节 点的h 一l a b l e ( v ，) 0 或者不能再向其父辈借点为止。 中心树t ( g ) 已知，该算法用d ( ”+ 删) 个处理器在o ( 1 0 9 n ) 时间内在e r e w 模型 上求出乙( g ) ，参见n i k o l o p o u l o s 6 1 。 2 3 新算法介绍 我们建立的这种新算法的大体思路就是在乙( g ) 上用d f s 方法( 即深度优先搜 索方法) 进行搜索。 算法2 3 王 对有 7 个顶点的q l 一蓬g ，给蹴g 的有用哑点树郎毛g ) ，具体的搜索步骤如 下： 1 用d f s 方法在建立的乙( g ) 上进行搜索，直至不能进行为止，得到p l ： 2 删除p 中所有点后剩余的部分必是( g ) 中的叶子或者子树，若有子树 五，夏，霉，则r a n k ( t j ) 勋羚露乙( g ) ) ，l s ，： 3 在剩余的各个连通分支晕继续从第一步开始重复上述过程，直至图g 中所有 点都被搜索完毕，得到的所有路的集合即为o t - 图g 的最小路覆盖。 如图2 8 中的搜索方法见下图： 2 3 毒袅大学鞭学使论文 匿2 8 t 拼( g 上的d f s 搜索方法 用方框圈起的部分就是剩下的予树l ，这墨剩余子树只有一棵。即： 馨2 9 主鳃淤搜索方法 再用d f s 方法搜索见图2 9 ，得到一条路协，则该图g 的最小路覆盏就是 p 兰 a ，p 2 j 。 2 4 算法的正确性及复杂性 为了研究这种方法的正确性，我们不妨将此过程倒溅回去，馁若此过程共分k 步