（计算机软件与理论专业论文）连通图中的可去边及其算法分析.pdf

摘要 摘要 图中可缩边与町去边是探讨图的结构，寻求使用归纳法证明图的某些性质 的个有利工具w t t u t 2 2 1 在1 9 6 1 年给出3 连通网的结构特征定理 时，实际上用到了可去边与可缩边的存在性，l u t t e 给出了极为出色的：j 连 通图的结构为：g 时3 连通图当且仅当g 是一个轮，或是从一个轮蓖复使 用以下而种运算推得的图： ( 1 ) 加边；( 2 ) 拆点。证明了每个阶大于或等于 5 的3 一连通图必有可缩边，这是有关可去边与町缩边的最早的结果h o l t o n ， 1 a c k s c m 、f i ) i m a i d 等在f 3 1 中对3 连通图中可去边的分布及数目进行了探讨 券健基在4 中得出了3 连通图中可去边的下界，并描述r r 达到这一下界的图 的结构特征f o u q u e t ，t h u i l l e r 和m c c u a i g 在【5 1 7 1 中对3 连通3 正则圈 中的可去边进行了研究。 尹建华在f 2 1 中证明了4 连通图g ( 阶数为5 和6 的2 循环图除外) 中总 存在可去边，并且利用4 连通图存在可去边与可收缩边的事实，证明了一个 4 连通图总可以从一个2 循环图经过以下步骤得到： ( 1 ) 加边；( 2 ) 拆点； ( 3 ) 加点去边；( 4 ) 扩点。 近二十多年来，有关可去边和町收缩边的研究已经有了很大进展，许多文 献重点研究了一个图中可缩边与可去边的数目 本论文主要研究了图论及其应用中连通度方而的问题，重点放在了3 连 通图与4 连通图方面：其主要研究成果如下： ( 1 )在论文的第一部分( 第二章) ，我们研究了3 连通图的可去边在生 成树上的分布g 是3 一连通图，e 是g 中的一条边。若g p 足3 连通图 的一个剖分，则称p 是3 连通图的可去边。否则，e 是g 中不可去边。我们 在前人研究的基础上，对3 连通图的可去边作了进步的研究，得到r 以下 结论：( 1 ) 3 连通3 正则图的生成树上至少有两条可去边；( 2 ) 设( ；是最小 度至少为4 的3 连通图，则任一生成树上至少有两条可去边。( 3 ) 设g 匙围 长至少为4 的3 连通图，则任一生成树上至少有两条可去边。 ( 2 )在论文的第二部分( 第三章一一第六章) ，我们主要对4 连通图中 的可去边作了一些研究。- l 连通图g 中的可去边定义如下：( 1 ) 从( ? 中去掉 边r 得图g f ( 2 ) 如果r 的某个端点在c r 中度数为3 则去掉此端点， 再两两联结此端点在g p 中的3 个邻点( 3 ) 如果通过运算( 2 ) 后有多重边 摘要 出现，则用单边代替它们，使此图成为简单图最后得到的图记为ger 如 果g e f 仍旧为4 连通图，则称e 为g 的可去边；否则称为g 的不可去边 在第三章中对4 连通图的可去边的性质作了研究，我们记g 的所有不町去边 记为e ( g ) g 的所有可去边记为e n ( g ) ，得到r 以下结果：( 1 ) ( ? 为4 连 通图，且i g l27 ( r ”，s ：t 1 b ) 是g 的分离组，其中r 4 ，b 若1 足 g 的边点割原子， 1 4 f 3 ，且n s ，：a ：“ee ( g ) ，则：“e “( g ) 。 ( 2 ) 没( ? 是 连通图，且l g l 三7 j e ( g ) ，( j 1 ，s ；4 ，b ) 是( j 的分离 组，其中f 。a ，b ，若j 是一边一点割原子，且e ( ) r e , a ( g ) ( ) ，则 | = 2 ( 3 ) 设g 是阶数至少为8 且最小度至少为5 的4 连通图，则对于 g 中任意边则有一是町去边或e 是可收缩边。( j ) g 是4 连通图，没 c 是g 中的5 一圈，若g 不同构于阶数为1 0 的环带或阶数为7 的双轮( 具体 定义见正文) ，则c 上至少有两条可去边。在第四章，我们得到了以下结果： 对于每一个阶数大于或等于6 的t i 连通图( 阶数为6 的2 循环图除外) 至少 有( 4 1 g j + 1 6 ) 7 条可去边，并且刻划了达到这一下界的图的结构特征，在 沦文的第五章和第六章，我们对4 连通图中某些子图的可去边的分布进行了 研究，得到了如下结果：( 1 ) g 是围长至少是4 的4 连通图，则g 中的最 长圈上至少有两条可去边。( 2 ) g 是4 连通图，其点的最小度为5 ，则g 中 每一个最跃圈上至少有两条可去边。( 3 ) g 是4 连通图，( 是g 中的圈， 若p 不通过某些指定的特殊结构，( 具体定义见正文) ，则( 上垒少有两条 可去边。 ( 3 )在论文的第三部分( 第七章) ，我们对本论文的结果加以总结，并 且对进一步的研究给予展望。 关键词：连通图，可去边，可收缩边，分离组，边点割断片，边点割端片，边 点割原子。 a b s t r a c t a b s t r a c t 7 f h e ( 。) i l ( e p to fc o n t r a c t i b l ee d g e sa n dr e m o v a b l ee d g e so fg r a p h si sap e w e r f u lt o o lt os t u d yt h es t r u t t u r e so fg r a p h sa n dt op r o v es o i l l ( 、p r o p 、r t i e so f g r a p k sb yi n d u c t i ( ) 1 1 i n1 9 6 1 ，t n t t e 6 g a v et h es t r n l 、t i l l a l t h a i a c t e r i z a t i o n f i n 3 - 。o t l u e ： ( 、d g t a p h sb yu s i n gt h ee x i s t e n c eo fc o n t r a c t i b l ee d g ( 、sa n dr e t n o v a l l ec i g e s h ep r o v e dt h a te v e t l y3 - c o n n e c t e dg r a p hw i t he l d e ra tl e a s t5 ( ( ) t “a i n sc ) n t r a c t i b l ee d g e st h i si st h ee a r l i e s tle s u l tc m c e r n i n gt , h e 【m c e p t o fe ( t i l t l 。a r t i b l ee d g e sa n dr e n o v a b l ee d g e s h o l t o n i a c k s o n ，w o r m a l te t ci nf 3 l s n m i dt h 、u n t n b e ra n di t sd i s t r i b u t i o no ft h er e m o v a b l ee d g e si n3 - e o n t n w t 、d g t a p h s u ，7 it 1h g e tt h es h a r ph t w e rt o u n do fr e i n o v a t ) l ee d g e si n3 - ：o n i l 、t t c ( i g i a p ha n da l s og i v et h es t r u c t m a lc h a r a c t er i z a t i o no f3 - c o a t l e e t e dg t a p h sf o r w h i c ht h e1 0 、e rb o u n di ss h a r p f o u q u e t ，t h u i l l e ra n dm 【c u a i gi n 1 7 ，5 s t u d i e dt h er e n l o v a b l ee d g e si n3 - e u b i kg r a p h 、，i 1 1i n 2 】t ) r o v c dt h a tt h e r ea l w a y se x i s tr e m o v a b l ee d g e si n4 - c o n n ( ! 。t e d g r a p h sg n n l ( 、s sgi sa2 - c y c l i cg r a p hw i t ho r d e r5o r6t h e r e ，t i ea l s os h o w e l t h a ta4 - c o n n e ( 1 t e dg r a p hc a nb eo b t a i n e df r o n la2 - c y c l i cg t 。a p hb yt h et b l l o w i n gf o u ro p e r a t i o n s ：( i ) a d d i n ge d g e s ，( i i ) s p l i t t i n gv e l r i c e s ( i i i ja d d i n gv n t ，i c e s a n dr e m o v i n ge d g e s ，a n d ( i v ) e x t e n d i n gv e r t i c e s t h i st h e s i sd e a l sw i t ht h ef o l l o w i n gt h i e et o p i c so i lg r a p ht , h e o r ya n di t s a p p l i c a ti o n s ：( 1 ) t h er e m o v a b l ee l g e so i ls t n i ts u b g t a p h s0 1 73 - c o t u l e c | e d g r a p h ；( 2 ) t h en l l l n b e r o fr e m o v a l ) l ee d g e sa n di t sd i s t r i b u t i o n o ns o t n l 、 s u b g r a p hi n4 - c o i l i l e c i b e dg i a p h ；( 3 ) t h ea r i t h m e t i co fr e m o v a l ) l ee d g e si n 3 - c o n u i ) c t e dg r a p ha i l ( 14 - c o n n e c t e d9 1 1 a p ha n di t sa n a l y s i s t h et e l m i n o l o g ya n dn o t a t i o n so fg r a p ht h e o r y - a n dt h eb a s i ck n o w l e d g e o fa l g o r i t h n lc o m p l e x i t yc a l lb ef i l u n di nt h ef i r s t c h a p t e r a tt i l es a m et i m e w eg i v eab r i e fi n t r o d u c t i o n ( ) ft h em a i nr e s u l t so ft i l et , h e s i s 1 i tt h ef i r s tt a t to f h et h e s i s ( c h a p t e r2 ) ，t i l ed i s t r i b u t u o no fr e t n o v a l l e e d g e so ns p a n n i n gt r e ei n3 - c o n n e c t e dg r a p ha r es t u d i e d i nth i sp a r t gi s 3 - ( o u n e c | ，e dg r a p h ，fi sa ne d g eo f3 - ：o l l i l e l ：t ! dg r a p h i fge 1i sas u b d i v i s i o n i f ) f3 - c o u n e e t e dg r a p h fh e nfi sc a l l e da l lr e m o v a b l ee eo fg o t h e r w i s e c i s 、a 1 i e du n r e m o v a b l ee d g e , so fg i nt h i sc h a p t e r t h er e m o v a h l ee d g ( 、hi l l 3 - c o i t l t e ( t e dg r a p hw e r es t u ( t i e do i lt i l eb a s e m e n to f ；q t ) o v f 、( o i l ( + h l s o h l s a 1 1 d w pg e tt h et b t l o w i n gc o n c l u s i o n ：1 r i h p r ea r ea tl e a s tt w ( ) r e i l l h h 、e ( 1 9 ( 、so il t h es p a n n i n gt r e eo f3 - c o n u e c t e d3 - e e g u l a rg r a p h ：2 7 f h m e ( a t1 i a s tt w e r e m o v a l ) i t 、e d g e so nt h es p a n n i n gt r e eo f3 - c o n n e c t e dg t a p hw i t ht | i t 、i i t i i t i t 1 l t t t i d e g n 、cp tl e a s tf o u r ；3 t h e r ea r ea 1 1 e a s tt w or m n o v a h l ee d g e so i lt h es p a l t a h l g tr p po f3 - c o l l l t ( ! c t e ( 1g r a p hw i t ht h eg i itt ta t , l e a s tf o u r i nt h es e c o n dp a r to ft h et h e s i s ( ( ：h a p t e r3 c h a i ) t e r 6 ) ，t h er e l l t o v a b l ee d g e s o ft l u 、4 - c ( ) i l n e c f e dg r a p ha r es t u ( 1 i e d l e tgt ) ea4 - ( ：o n n c e t , e dg r a p h ，f m a l l e d g eco fg w ed ot h ef o l l o w i n go i ) e r a t ，i o n so i lg ：f i r s t d e l e t et h ee d g erf r o m g ，r e s u l t i n gt h eg l 。a p hg p ：s e e o l l d ，f 【) ra l lt h ev e r t i c e szo fd ”g tt 、p3i i lg 一“ ( 1 e l e t etf i o mg ea n dt h e ne o m p l e t ，e l ye o n u e c tt h e3n e i g h b o l so f 。b ya t r i a n g l e i fl n u k i p ee d g e so c c t l i ， u s es i n g l ee d g e st or e p l a c et h e m t h e f i n a lr e s u l t a n tg r a p hi sd e n o t e db y g e e i f g e ei ss t i l l4 - c o n n e c l e d t h e ne i sc a l l e dar e m o v a b l ee d g eo fg o t h erw i s ( 、，pi sc a l l e da nu n r e m o v a b l ee d g e 8o f g ， i nc h a p t e r3 ，t h ep r o p e r t i e so ft h er e m o v a b l ee d g e si n4 - c o n n e c t e dg ta p h a r es t u d i ( 、( 1 t h es e to fa l lr e i n o v a b l ee d g e so fgi sd e n o t e db ye r ( g 1 ：w h e e a h t h es o to l l l i l l f l m o v a b l e e d g e so fg i sd e n o t e db ye ( g ) eg e tt h ef o l l o w i t ) g c o n c h l s i o n ：( 1 ) l e tg b ez l - c o n n e c t e dg r a p hw i t hi g l 7 ，l e t ( 1 ，s ；。4 b ) b es e t ) a r a t i n gg r o u po fgs u c ht h a tx a ，b i fai sae d g e v e r t e x 一( ：i l l a t o l ns u c ht h a tl - 4 i 三3 a n do s ，：a ，：n e g o ，t h e nz a e 扎( g ) ( 2 ) l e tg 1 ) e4 - ( 1 0 l l i l e c t e dg r a p hw i t hi g i 7 ，x y f ( g ) ，( j ，s i 。4 ，b ) b ea s e l t a r a t i n gg t o u po fg s u c ht h a t f a ，y b i fai sae d g e v e r t e x t i l t a t o m o fga n de ( a ) ne n ( c , ) o ，t h e ni 4 l = 2 ( 3 ) l e tgb e l - c o l l t t e ( t e dg r a p h s l l c ht h a tl g i 三8a n dt h em i t t i l l l l l i i ld e g r e ea tl e a s t5 ，t h e nf o ra r t y ( f ( ( 孔 w ch a v et h a tfi sae o l l t r a ( ：1 i b l ee d g ee lpi xar e m o v a b l ee d g e f 4 1l e t gb e 4 - c o l l i i e ( ：t e dg r a p hs u c ht h a t gi sl l o t b i 一川p fo rb e l t ci sa5 - ( y ( 。ho fg t h e nl l l e r ea r ea tl e a s t ( h i er e n i o 、a b l ee d g e0 1 1c i nc h a p t e l4 w ep r o v et h a te v e r y4 一( o n n e c t e dg t a p ho fo r d e ra tl e a s ts i x ( ( x d u d i n gt h e2 - c y e l i cg r a p h ( i fe l d e rs i x ) h a sa tl e a s t , ( 4 t a l + t o j wr e u l o v a l ) h 、 e d g e s w ea l s og i v et h es t r n c t u ta lc h a r a c t e r i z a t i o no fr l - e o u l i q ( 。“、dg r a p h st b l a h 8 t r a c w h i c ht h el o w e rb o u n di ss h a r p i nc h a p t e r5a n dc h a p t e r6 ，t h ed i s t r i b u t u o no fr e m o v a b l ee d g e so ns o n i c s u b g r a p h si n4 - c o n n e c t e dg r a p ha r es t u d i e d w eg e tt h et b l l o w i n gc o n c l u s i o n s ： ( 1 ) l e tgb e4 - c o n n e c t e dg r a p hw i t ht h eg i r t ha tl e a s tf o u r ，a n dc b et h ec y ( ：l e ) fg ，t h e nt h e r ea r et w or e m o v a b l ee d g e so nc ( 2 ) l e tgb e4 - e o t i n e e t e dg r a p h w i t h t h em i n i m u md e g r e ea tl e a s tf i v e ，a n dcb et h ec y c l eo fg ，t h e nt h e l e a r et w or e m o v a b l ee d g e so nc ( 3 ) l e tgb e4 - c o n n e c t e dg r a p h a n d ( ? b e t h ec y c l eo fgw h i c hs a t i s f y i n gs o m ec o n d i t i o n s ，t h e nt h e r ea r et w or e m o v a b l e e d g e so nc ( 4 ) l e tg b e4 - c o n n e c t e dg r a p h ，a n dcb et h el o n g e s tc y c l eo fg w h i c hs a t i s f y i n gs o l n ec o n d i t i o n s ，t h e nt h e r ea r et w or e m o v a b l ee d g e so i lc i nt h et h i r dp a r t ( c h a p t e r s7 ) ，w e 舀wao v e r v i e wo ft h ew h o l ec o n t p n t s ( ) f t h et h e s i sa n da l s op r o p o s es o m ef u r t h e rr e s e a r c hp r o b l e m s k e y w o r d s ：c o n n e c t e dg r a p h ，r e m o v a b l ee d g e ，c o n t r a c t i b l ee d g e s e p a r a t i n g g r o u p ，e d g e v e r t e x - c u tf r a g m e n t ，e d g e v e r t e x c u te n df r a g m e n t e d g e v e r t e x e 1 1 ta t o n l 第一章绪论 1 1 引言 第一章绪论 豳论是一个古老的数学分支，其历史可以追溯到1 7 3 6 牛瑞士著名的数学家 e u l e r 解决k s n i g s t - m r g 七桥问题。但是在随后的两百年里，罔论的发展极为缓 慢。这一时期，图论的研究主要集中在两个方面：一足如四色问题和i - i a l h i l t o n 问题等难题；二是以图作为工具去解决其它领域的一蝗问题，其中最具代表性 的成果是k i r c h h o f f ( 1 8 = l i 年) 和c a y l e y ( 1 8 5 7 年) 分别用树的概念去研究电网 络方程组和有机化合物的分子结构。进入2 0 世纪3 ( ) 年代，出现了一一峰精彩 的结果，如m e n g e r 定理( 1 9 2 7 年) ，k u r a t o w s k i 定理( 1 9 3 0 年) 和r a m s o y 定理( 1 9 3 0 年) 等。这些结果为图论的发展奠定了基础。t 9 3 6 年，匈牙利数 学家k 6 n i g 出版r 第一本图论专著，标志图论作为数学的一个新的分支已经 基本形成。 上世纪3 0 年代以后，由于生产管理、军事、交通运输、计算机和通讯网络 等领域中许多离欹陲问题的出现，大大促进了图论的发展。待别是进入7 ( 1 年 代以来，大型计算机的出现，使得大规模问题的求解成为可能，图论本身及其 在物理学、化学、生物学、地理学、运筹学、计算机科学、信息论、系统论、 控制论、网络理论、社会科学以及经济管理等方面的应用研究都取得了突猛 进的发展。今天，图沦及其应用受到全世界从事理论研究的科学工作者和从事 应用研究的工程技术人员以及经营管理者越来越多的关注。 图沦和计贸：机科学的关系尤为密切目前，几乎所有的计算机系本科生都 把图论作为离散数学或组合数学的一个重要组成部分来学习，一些计算机系 还为高年级本科生和研究生开设了专门的图论课程。在国外，许多计算机系都 有专门从事图论及其应用的教学和研究人员。国际上一些从事汁算机软硬件 开发的驰名公司也吸收一些图论专业的研究人员，如贝尔实验室就网罗了一 批图论专家从事通讯技术研究，而著名的匈牙利籍图论专家l o v a z 目前则供 职于微软公司。 图论和汁算机科学的关系可以概括为以下几个方断。第一，计算机科学的 研究和发展为图论学科提供了大量的研究问题，计算机科学已成为图论发展 的最主要的原动力之一。我们经常会遇到计算机科学研究中的一些问题，很 ) 连通图中的可去边及其算法分析 容易建立起其图论模型，探讨这些问题的求解方法，往往会推动图论自身的 发展。第二，图论是计算机科学赖以发展的重要数学基础之一，图论的方法在 计算机科学的研究中起到非常关键的作用。从大规模集成电路的设计到计算 机通讯网络的构造，从计算机软件的开发与调试到并行计算帆网络的拓扑结 构的选择，图沦理论和方法的应用比比皆足。总之，图论在计算机科学中，如 形式语言、数据结构、分布式系统和操作系统等方面部扮演着重要的角色。第 三，计算机科学和技术的发展为图论的研究提供了强有力的工具和方法。如 果没有计算机这样的工具，即使最简单的最短路问题的解决也不可能得到实 现，更重要的是，计算机推理，人工智能的发展使得一些图论难题的解决成为 可能。一个很好的例子就是a p p e | 和h a k e n l 4 6 】在1 9 7 6 年利用计算机解决了 图论中最著名的四色问题。直到今天，如果不借助计算机和计算机科学的研究 成果，人们还不能解决这个困扰了多少代数学家一百多年的数学难题。另一个 例! 于是计算机程序g r a f f i t i 给出了许多图论猜想，并且人们已经证明其中 不少足正确的【f ；。- ”，8 目。 在下面的两节里，我们将依次介绍本论文所用到的一些基本图论慨念和术 语以及算法复杂性的基本知识。熟悉图论和算法复杂性基本知识的读者可以 跳过这两节直接阅读后面的内容，在需要的时候再来查阅。在本章的第四节， 我们将介绍本论文所研究的主要问题、国内外研究进展和我hj 在本论文中所 得到的研究结果。 第一章绪论 1 2 基本图论概念和术语 我们在这里介绍的图论中一些慨念和术语基本上与文献1 1 一致。沦文中 未加说明的概念和术语参见 1 】。为了便于阅读，在以后各章中我们可能重复 这里介绍的一些概念和术语。 一个图g 是指。一个有序三元组( “g ) ，f ( g ) ，v g ) ，其中i7 ( g ) 是非空的 顶点集，e ( g ) 是不与g ) 相交的边集，4 ，g 是关联函数，它使( ? 的每条 边对应于g 的无序顶点对( 不必相异) 。若e 是一条边，而“和f 是使得 * f ? ( e ) = 川j 的顶点，则称e 连接u 和f ；顶点n 和t j 称为f 的端点一条 边的端点称为与这条边关联，反之亦然与同一条边关联的两个顶点称为相邻 的，与同一个顶点关联的两条边也称为相邻的。端点重合为一点的边称为环， 一个图称为简单图，如果它既没有环，也没有连接同一对顶点的多条边。一个 网称为有限图，如果它的顶点集和边集都有限本论文只研究有限简单图。 g 的顶点 的度如( ”) 是指g 中与”关联的边的数日。用5 ( g ) 和( g ) 分别表示g 的顶点的最小度和最大度图的顶点数和边数分别用符号，t ( g ) 和e ( g ) 来表示。在不致引起混淆的情况下，我们用e ，儿( f ( t ，) ，d 和来分 别代替、( g ) ，e ( c ) ，7 ( g ) ，d a ( v ) ，6 ( g ) 和( g ) 。 只有一个顶点的图称为平凡图，其他所有的网称为非平凡图。每一对不同 的顶点都钉一条边相连的简单图称为完全图。一个有，一个顶点的完全图记为 另一方面，空图屉指没有任何边的图。一个有7j 个顶点的空罔记为止_ 。 所滑偶图足指一个图，它的顶点集町以分成两个( 非卒) 子集- - 和l ，使得 每条边都有一个端点在x 中，另一个端点在中；这样一种分类( 一，1 ) 称 为图的一个二分类。完全偶图是具有二分类( y ，7 ) 的简单偶图，其中、f 的每 个顶点都与 的每个顶点相邻。 两个图g 和日称为相等，如果7 ( g ) = r ( 日) 且e ( g ) = e ( h ) 。网( ； 和h 称为同构，是指存在一个一一对应0 ：l7 ( g ) 一l ( h ) ，使得s ( o ) 当且仅当p ( “) p ( ，) e ( h ) 。 称图日是图g 的子图( 记为，g ) ，如果i ( h ) i ( g ) ，e ( ，) 垦 e ( g ) 。当cg ，但h g 时，则记为hcg ，并且h 称为( ；的真子 图。若h 是g 的子图，则g 称为j ，的母图。g 的生成子图( 或生成母罔) 是指满足1 ( h ) = 1 ，( g ) 的子图( 或母图) 。 假设i 。是l7 的非空子集。以l 。为顶点集，以两端点均在l 。中的边的 连通图中的可去边及英算法分析 全体为边集所组成的子图，称为g 的由i 。导出的子图，记为( ；i - 1 有时也 记为 g f i f 】称为g 的导蹦于图导出子图g 1 1 】记为g i 。假设 e 是e 的非空子集。以中的边的端点的全体为顶点集，以为边集所 组成的子图称为g 的由e 导出的子图，记为g e 】；有时也记为( e ，) ( ? f 】 称为g 的边导出子图。边集为e e 的生成子图简记为a；它是从g 中删去e 中的边所得到的子图。设g i 和g 2 是( ? 的了- 图。若( ；和g 2 没 有公共顶点，则称它们是不相交的。g i 和g 。的并图g ；u ( 屯是指g 的一个 子图，其顶点集为( g 1 ) u g 2 ) ，其边集为e ( g 】) u f f “2 ) ；类似地可以定 义g l 和( ? 2 的交图( ? 1n 国。不相交的两个图g l 和g 2 的联图( ? 。+ g 。是 指在g - ug 2 中，把d ，的每个顶点和g 2 的每个顶点连接起来所得到的图。 g 的一条途径是指一个有限非空序列= t ，o r 叫1 e 2 t ，：c k ，它的项交 替地为顶点和边，使得对lsi k ，“的端点是 i 和t “称i f 是从r ，o 到 ，的一条途径，或一条( ，o ，) 途径。顶点l ，o 和t ，分别称为i i f 的起点和终 点，而，t ? 2 ，t ，n l 称为彤的内部顶点。整数 ：称为i i ? 的长。若途径 的顶点互不相同，则w 称为路，记为尸。类似地，一条起点为? b ，终点为t ，k 的路p 弥为( t 抽t ) 路。g 的两个顶点t 和 称为连通的、如果在( ；中存在 ( f 1 1 川路连通是顶点集1 ( g ) 上的一个等价关系。于是就存在的l ( ( ? ) 一个 分类，把l ( g ) 分成非空子集i j ，圪，其中i j 、j = 0 ( j ) 。使得两 个顶点足连通的当且仅当它们属于同一子集。子图( 邓j 】g 1 i ! 】一，( ；n j l 称 为g 的连通分支。 若g 只有一个连通分支，则称g 是连通的；台则称g 是不连通的。g 的连通分支数记为u ( g ) 。 称一条途径是闭的，如果它有正的长且起点和终点相同。若一条闭途径的 起点和内部顶点各不相同，则称它为圈。艮为 的圈称为一圈。g 中的最小 圈称为g 的围长，我们用9 ( g ) 表示g 的围长。 一棵树g = ( i j 丁) 是一个连通且无圈的图。一个森林就是点不相交的树 之集合。同样的，称( 1 j 7 ) 为i 的支撑树。 包含g 的每个顶点的路称为h a m i l t o n 路；类似地，g 的h a m i l l o n 圈是指 包含g 的每个顶点的圈。一个图若包含h a m i l l o n 圈，则称这个图为h a m i l t o n 图。 若r 的子集s 使得g s 不连通，则s 称为( ? 的点割。s 一点割k - 指 有s 个无素的点割。若g 的顶点割s 必包含一个顶点则称z ，为g 的 第一章绪论 割点若g 至少有一对不相邻的顶点，则g 所有的s 一点割巾最小的s 称 为g 的连通度，记为k ( ( ? ) ；否则定义k ( g ) 为礼一i 。于是，当g 不连通 时，k ( g ) = 0 。若k ( g ) ，则称g 为 一连通的。对i r 的子集 和 口，其中a n b = o ，用f a ，引表示一个端点在a 中，另一个端点在口中的 所有边的集所谓g 的边割是形如慨s 的子集，其中s 是i 的非空真子 集，且s = i s 。一个一边割是指有k 个元素的边割。若g 非f 凡且 e 是g 的一个边割，则g e 不连通；于是把g 的边连通度a ( ( ；) 定义 为：g 的所有k 一边割中最小的k 。若g 是平凡的，则定义a ( g j 为0 。若 a ( g ) ：，则称为k 一边连通的。( 1 是一个f 一圈， 是c 外的：个顶点， 令1 7 ( g ) = ) u ( c ) ，e ( c ) = e ( g ) u 【 ，i ( c ) ，则称g 为轮，记为l k ； 其中，o = f + 1 1 3 算法复杂性简介 我们现在来介绍关于算法复杂性的一些基本知识关于算法复杂性的经典 参考书目为1 4 1 和f 6 1 1 。 一个要解答的一般性题目称为问题( 用n 表示) 。以旅行售货员问题为 例：给定n 个城市f l ，q 、，( ，以及任何两个城市g 和( ? ，之间的距离 r ? 。( 如果城市( 、。和城市c ，之间没有直接通路，则记d i ，= 。) ，一个售货员 从城市c ，出发，然后经过每一个城市一次且只有一次，最后返回城市c 。t ， 求一个方案，使该售货员旅行的总路线最短每个问题都有一些参数，当这些 参数有了确定的值，就得到该问题的一个实例。在旅行售货员问题中，如果确 定r 城市的数目和各城市之间的距离，就得到旅行售货员问题的一个实例。 算法足- 个频繁出现的术语。准确地说，问题的算法由有限个指令的序列 组成。其中每条指令都有明确的含义，每条指令的执行包含有限的工作鲢；序 列的执行会在有限时间内停止下来，并给出问题的任何实例的解答。9 1 ：法a 解决问题是指：如果将a 用于问题兀的任何一个实例i ，辩：法给出实例i 的解。例如，高斯消元法就是解决线性方程组问题的一个算法。 一般而言，解决一个m 题的算法往往不是唯一的。衡量个算法的好坏， 人们常常从其正确性、复杂性、简单性、最优性、可读性以及可修改呵扩展性 等力面加以考虑。算法复杂性包括时间复杂巨和空问复杂性。我们在此只考虑 b , t l u 复杂性，即算法运行所需的u f l 1 。然而由于计算机的速度不同和指令系统 不同，从而所带的时间随着计算机的不同和所使用的算法语言不同而有很大 6 连通图中的可去边及其算法分析 的差别。因此，在算法分析中，人们常用初等运算( 算术运算，比较运算和转 移指令等) 的次数，表示一个算法在假设的计算机上执行时所需的时问。即假 设每做一次初等运算，需要一个单位时间。 一个算法所需要的运算次数与两个因素有关：l 问题实例的大小；2 即 使问题实例的大小相同，算法运行的时间还与实例的具体情况有关。例如，一 个用来解决旅行售货员问题的算法所需要的时间与城市的个数有关，也与城 市之间的具体距离有关。这样，如果用， 表示问题实例的大小，则算法a 运 行所需的时间不仅与n 有关用i 和jlj 分别表示实例和实例的大小，定义 算法a 的时间复杂度( 简称为复杂度) ( n ) 为 几( ) = l i l a x ，ni 存在实例i 使得 il = n 、且a 对i 运行所需的运算次数为m ，。 设，( ，o ) 是定义在非负整数集上的一个函数，如果存在正实数a 及正整数 n ，使得当，z 三n 时，有厂1 ( n ) c ，( n ) 成立，则称，l ( “) 的阶小于或等于 ，( ，) 的阶，汜为f a ( n ) = o ( ，( ，z ) ) 。如果，( n ) 是一个多项式函数，则称算法 a 为一个多项式算法。否则的话，称算法a 为指数算法。对于多项式旃：法， 如果提高了计算机的速度，则其所能解的实例的大小可能成倍地增加；而对于 指数算法而言，提高汁算机的速度，几乎没有增加所解的实例的大小。所以， 通常把多项式算法称为有效算法，把指数算法称为无效算法。 对一个问题的每一个实例，如果只要求回答“是”或“否”，则称这个问题 为判定问题。一般说来，任何一个有限的最优化问题都可以转化为一系列的判 定问题。以旅行售货员问题为例，我们把经过每个城市一次且只有一饮，最后 返回出发城市的旅行路线称为一条h a m i l t , c ) 1 1 环游。一条h a n l i l t o n 环游的长 度是指为对应的旅行路线的总距离。这样旅行售货员问题与下列判定问题有 关； t s p d e c 实例：给定城市的个数m 各城市之间的距离和一个正数b ； 问：是否存在一条h a m i l t o i l 环游，使得其长度不超过口? 很显然，旅行售货员问题可以转化成一系列的t s p d e c 。不难看出，一个 问题的判定形式并不比原问题更困难，如果原来的最优化问题可姒用多项式 算法解决，则与其相应的判定问题一定可以制多项式算法解决。所以，如果在 算法复杂性研究中仅讨沦判定问题，并没有失掉一般性。 一个判定问题，如果可以在多项式时间内得到解决，则称它为p 问题，所 第一辛绪论 r 有p 问题组成的集合称为p 类，记为p 。一个判定问题，如果给出它的解的 一个猜测后，存在多项式算法验证这个猜测是否为问题的解，则诈这个问题为 n p 问题，所有n p 问题组成的集合称为n p 类，记为n p 。不难看出，每个 p 问题均为n p 问题。是否所有的p 问题都是n p 问题，即是否有p = n p ， 足理论计算机科学中的核心问题之一。 给定两个判定问题。和n 。，如果存在一个多项式算法，能够将问题 变换为问题丌2 的一个特例，并且使得h t 的答案为“是”当且仅当r 1 2 的这个 特例的答案也为“足”，则称。可以多项式地归结为玎2 ，记为- 。c z 。如 果( 2 是一个n p 问题，并且对任意的n p ，均有丌( ) ( q ，则称q 为n p 完全问题，所有的n p 完全问题组成的集合称为n p 完全类，记为n p c 。 n p 完全问题是n p 类中最困难的问题。如果一个n p 完全问题能够用多项式 钟：法解决，则n p 中所有的问题都可用多项式算法解决；反之，如果n p 类 中有一个问题不能够用多项式算法解决，则所有的n p 完全问题都足难的。 判别一个问题是否n p 完全问题有重要的意