（应用数学专业论文）图论中的若干极值问题.pdf

图论中的若干极值问题 郭秋敏 ab s t r a c t i n t h i s t h e s i s , w e m a i n l y d i s c u s s t w o e x t r e m a l p r o b l e m s i n g r a p h t h e o r y : t h e m i n i m a l o r d e r o f a n ( m , k , l ; n ) g r a p h a n d t h e m i n i m a l b o n d c o v e r o f a g r a p h . l e t 1 7 1 , f z ， 一 ， f q b e q c li q u e s o f g r a p h g , w e c a ll t h e m n o n - id e n t i c a l c l i q u e s , i f v i i q , t h e r e e x i s t s u i f , , s u c h t h a t u i v f i ( v i m + n + 2 必 丽 不 ! k ( “ ) 若 m + n + k + i + 警 显然，由上述结果可以得到伽i k , 1 ; n ) 图可以取得的极小阶数，并 个推论，e n t r i n g e r - g o d d a r d - h e n n in g 定 理 7 也可以由 此很容易 1 .2 . 图的极小键覆盖 用给定的某类子图州如团、圈等) 来覆盖图g的所有边，这是图 论中的一类基本问题.从某种意义上说，一个有效的覆盖就是使得尽 可 能多的边只被覆盖一 次， 因此艇盖e ( g ) 最有效的方式就是把它分解 为这些子图.但是，并不是所有的图都能分解为特定的子图，即使它 )至 丛 塑鱼兰 工鱼 燮噢 一一一一一 郭秋敏 们可以用这些子图来覆盖. 由于这一原因，我们定义图 的覆盖大小( 相对于某类子图万) 为 图的所有覆盖中的 最小边数和， 记为c s ( g , h ) . 在本文的第三章，我们研究了图的键覆盖。证明了一个图存在键 覆盖当且仅当它连通，并进而对连通图的键覆盖大小进行了估计，证 明了连通图的键覆盖大小和它的边割覆盖大小是相等的. 1 .3 . 基本概念和记号 为了方便本文的阅读， 这一节我们给出了 所用的一些记号和基本 概念. v x e ii $ ， 我们分别用lx j 和lx l 表示不大于二 的最大整数和不小于 x 的最小整数. 对任意图g，我们用v ( g ) 和e ( g ) 表示g的顶点集和边集.g中 顶点的个数iv ( g ) 称为图g 的阶( o r d e r ) , g 的边数e ( g ) 称为g的 大 小( s i z e ) ， 记e ( g ) = ie ( g ) i . 任意两个顶点都相邻的图称为完全图或团( c l i q u e ) . 一个m 一 团 是 指阶为m的完全图k m .v ( g ) 的子集s 称为g的独立集， 如果s 中的 任意两个点都不相邻( 独立集有时也称为稳定集) . 图h称为图g 的子图， 如果v 田) c v ( g ) , e 归) c e ( g ) . 此时我们 也说g 包含h. 特别， 当v ( h ) = v ( g ) 时， h叫 做g 的一个支撑子图; 当 e (h ) 二 e ( g ) n ( v 岁 ) 时 ， 称h 为g 的 一 个 点 导 出 子 图 并 且 说a 一 v (h ) 诱 导 出h ， 其 中( v 圳 ) 表 示v ( h ) 上 的 完 全 图 的 边 集 . 我们说图g 和图h同 构， 如果存在一个双射f : v ( g ) - 4 v ( h ) ， 使得“ v e e ( g ) 当且仅当f ( u ) f ( v ) e e ( h ) .v u , v e v ( g ) ， 如果存在g 上的一个自同构中 ，使得$ ( c c ) =v ， 则称g是点可传递图;类似的， v e , w e e ( g ) ， 如果存在g 上的一个自 同 构m ， 使得 ( e ) = w ， 则称g 是 边可传递图. 一个图称为连通图， 如果图中的任何两点之间都存在一条路相连. 如果去掉图g中的任何k 一 i 个顶点仍然得到一个连通图，则称g是k - 连通图。特别的， g的一个极大 2 一 连通子图称为g的块. 任给s , t c v ( g ) ，记: s , t : = u v e ( g ) 为所有从 s 到了 的边的集合 个 边割( e d g e c u t ) ; 特别， 称为键( b o n d ) 如果 7 、 = “ s , v c t 圣 s 二v ( g ) 一 s ， 则s , s 称为“ 的 如果 和s 的点导出子图 都连通，则s , s 图论中的若干极值问题郭秋敏 图g称为k 一 部图或k 一 可着色的， 如果州 ) 可分解为k 个两两不 交的顶点集v i , v 2 , . . . , v k 的并，且任何一条边的两个端点不在同一个v 中. 使得g 是k 一 可着色的最小正整数k 叫 做g 的点色数， 记为% ( g ) , 图论中的其它术语及记号， 请参见 2 , 5 1 图论中的若千极值问题 郭秋敏 2 . ( m , k 出。 ) 图的 极小 阶数 2 . 1 . 背景介绍 c h a r t r a n d , g a v la s 和s c h u l t z 3 在1 9 9 2 年首次引 人了图的框架数 ( f r a m in g n u m b e r ) 的概念。 我们说一个图g可以 被齐次地嵌入到图h中， 如果对于任意的x e 叫 甸和y e 叫 川， 在h中 存在一个包含点y 的子 图， 该子图同构于， 且顶点y 对应于点x 。 使得g 可以被齐次嵌人的 并且阶数最小的的图f 称为g 的一个框架( f r a m e ) ， 并且f 的阶数称为 g 的框架 数( f r a m i n g n u m b e r ) ， 记为f r ( g ) 。 在 3 1 中， 他们 证明了任何 图都存在框架，虽然它的框架不一定唯一。 定理2 . 1 . 1 ( c h a r t r a n d e t a l . 3 ) . 任何图都存在框架. c h a r t r a n , g a v l a s 和s c h u ltz 还 将 上面 框 架数的 概念 推广 到 多 个图 的 情 况. 对图g i 和 : ，g 。 和g : 的 框架数f r ( g i , g 2 ) 定义为使得 , ( i =1 , 2 ) 可以同时被齐次嵌入的图f的最小阶数，图f称为g 。 和g : 的框架。 则f r ( g i , g 2 ) 存在，事实上，f r ( g i , g 2 ) n，存在阶为n 的图f, f是份( 1 i 间 的框架，而当n m + n 十 2 v m- n 在下面的章节，我们将研究比 这更广泛的一类图:( m , k , l ; n ) 图， 并且 给出这类图 存在的 极值条件. 在第二节， 我们首先给出( m , k , l ; n ) 图的 定义，第三节则是两个重要的引理， 最后， 我们在第四节给出主要结 果，由这一结果我们可以直接得到上述结论. 2 .2 . ( in , k , 1 ; n ) 图 首先，我们定义团互异的概念. 设f l , f 2 , - , 凡是图g 中 的q 个团 ， 如 果d l i q ， 存 在“ e f , , 使得 对 任意的1 j s q ( j 6 i ) 有“ i v f j ， 则称f , f 2 , . . . , f q 是互异的、 个团. 下面给出( in , k , 1 ; n ) 图的定义: 图g被称为一个沁, k , 扫 1 ) 图， 如果g中的每个点既包含在一个 ( m + 1 ) 一 团中， 又在一个( n + 1 ) 一 独立集中， 且g 中含有至少l 个互异的 ( 二 + k +1 ) 一 团. 称g为三分拆图， 如果v ( g ) 能分解为3 个两两互不相交的顶点 集r , s , t的并，其中r 是独立集，s ( j t的点导出子图是团，且r 和t 之间没有边相连. 若g的阶数大于1 ， 则总可以假设r 和s 都非空， 而 t 可以为空. 设 是( in , k , l ; n ) 三分拆图， 如果g中存在l 个互异的( m + k + 1 ) - 团f , , f 2 ， 二 ， f i 满足下列条件: h l in + k ，_i _ a的 征一列至少有。 个。 ，母一 行至少有， 个1 ， 特别还有h 行， 它的行一 行至少有( ， ， 一 k ) 个1 ， 其中h 二 ，n a z i 一 ， , 0 ) 图论中的若干极值问题 郭秋敏 2 .3 . 两个引理 我们 下面的主要目 的 就是要对( m , k , l ; n ) 图 进行讨论， 给出( m , k , l ; n ) 图存在的极值条件， 这也是我们这部分的一个主要结果. 在给出 这一 结果并进行证明之前，我们先来看两个重要的引理. 由 上一节最后部分的叙述可知， 讨论一个( m , k , l ; n ) - g o o d 三分拆图 的存在性，只须考虑其对应的: x : 阶关联矩阵a 的存在性就够了. 下 面的引理给出了这样的矩阵a 存在的充要条件. 引理2 .3 . 1 . 设m , n , r , : 为正整 数且: 全 m + k , t , h 为非负整数.a为; x s 阶的( 0 , 1 ) 矩阵，a的每一列至少有n 个0 ， 每一行至少有m个 ， 特别还有h 行，它的 每一行至少有( m + k ) 个1 .则a存在当 且仅当 m r +n s + k h 三r s . 证明: 必要性显然，我们只需证明充分性. 假设我们有m r + n s + k h g r s 成立， 我们来构造一个满足要求的( 0 , 1 ) 矩阵a . 首先， 我们 任意构造一个: x : 阶( 0 , 1 ) 矩阵， 使得它的 前h 行每一 行都恰有m + k 个1 ， 剩下的行每行恰有。 个1 . 如果有某一列， 如第i 列的。 的个数小于。 ， 则必然存在某一列， 不妨设为第.l 列， 其。 的个 数大于n . 则存在某一行， 使得交换第i 列和第j 列位于这一行上的两 个元素之后，第i 列。 的个数增加1 ， 而第j 列。 的个数减1 . 一直重 复这一过程，使得每一列。 的个数尽可能平均， 则我们得到一个满足 要求的( 0 , 1 ) 矩阵二 显然，( m , k , l ; n ) - g o o d 三分拆图的 条件 要比( m , k , l ; n ) 图 强得多， 那 么 ， 这两类图 之间有什么关系呢? 下面的引理表明，( m , k , l ; n ) 图的 存 在 性和( m , k , l ; n ) - g o o d 三分 拆图的 存 在 性是等 价的. 引理2 .3 . 2 . 若p 阶如, k , l ; 的图存在，则v 阶( m , k , l ; n ) - g o o d 三分拆图也 存在. 证明: 设g 是( m , k , l ; n ) 图， 我们来重新构造一个以、 二v ( g ) 为顶点集的 ( m , k , l ; n ) -g o o d 三 分 拆图 . 设 f= f l , f 2 , . . . , f l , e l , . . . ， 乓 是覆盖顶点集v的一个团的集合，其中f l , f 2 , . . . , f 1 是g中l 个互异的 ( in + k + 1 ) 一 团，u i g f , 且“ j f j ( v j o i ) ; e l , . . . ， e 4 是( n 1 + 1 ) 一 团。 且 v i i q , e , 中存在点v i ,， ， 不在f的 其 它元素中出现。 我们可以 假 设g中不含不在f的元素中的边( 否则，只需把其它的边去掉即可) 令xsr是覆盖v的f的一个极小子集， 显然，e l ， 二 ， e , e x. 不 图论中的若干极值问题 郭秋敏 失一般性， 我们 记 7 c = ( e l , . . . ， 凡, f , , - . - , f p ( 0 1 1 ) . 从犬的每个元 素中 取一个点， 使得这个点不被火的 其它元素 包含( 特别的， 对于e i ， 我 们就取v i ) . 我们把得到的这个点集记为r ， 并且令t = ( u p + t , . . . , u i ) , s = v一r一t. v w e r ， 如果3 1 i 1 , s .t w e f , ， 则我们 将、 和f , 之外的点之间 的所有边都去掉. ( 1 ) . 如果v j i , w 0 f , ， 则去掉w 和f i 之 外的 其它点之间 的边不影 响这些团，f , 仍然是一个( m + k + 1 ) 一 团，w e f , 且w不属于其它的 ( 二 + k 十 1 ) 一 团. ( 2 ) . 如 果3 j 36 i ， 使 得、 乓， 则 去 掉w 和f 之 外 的 其它 点 之间的 边 将 破 坏 原 来 的( m + k + 1 ) 一 团f i ， 因 此 我 们 需 要 构 造一 个 新的 包 含u i 的 (m + k + 1 ) 一 团 . 将u 1 和f , 中 除w 之 外的 点 都 连 上 边 ， 则 我们 就得 到 一 个 新 的 包 含u i 的( m + k + 1 ) 一 团 . 为了 叙 述的 方 便， 我们 仍 然 用f j 来 表 示这个新的( m + k 十 1 ) 一 团， 则f ; 本身仍然是( m + k + 1 ) 一 团， 且w 不在 其它的( m 十 k 十 1 ) 一 团中. 现在我们得到r是一个独立集.接下来，我们要将r 和t 之间的 边 都 去 掉 .v w c r , ( 1 ) 加果v i i q , w o v i ， 则w不 和t 中 的 任 何点 相 邻. 因 此， 去 掉 r 和t 之间的边对点w 没有影响. ( 2 ) 如果3 1 i q , s .t w = v i ， 则我们分两种情况讨论: . v l i q , u j v e i ， 则、 也 不和t 中 的 任 何点 相邻， 因 此去 边不 影响w. * 3 1 i m + n + 2 沂 丽 下 瓦 ( “ ) 如 果 _ m + n + k + 1 + 臀 证明: 当p m + n 的情形.设 p = m + n + d , d 为正整数. 则由 引 理可知，p 阶( m , k , l ; n ) 图存在当 且 仅当存在正整数r , ， 以及非负整数t 使得 r +s +t = p s 全m+k m r +n s +k h兰r s 成立， 其中h = m a x l 一 t 0 1 . 即 r +s +t = p s 全m+k t l mr +n sm+k t1 m r +n s + ( 1 一 t ) k r s 之一成立. 容易验证，如果 ; 二: 。 ， 、 =s i , t = t : 是 ( 2 .2 ) 的一组解，则 ( 2 . 3 ) r 二 si十 t , 一 ! , t 二1 是( 2 .3 ) 的一组解，因此我们只需考虑( 2 . 3 ) 就够了. 将; =m + n + d 一( : + ) 代人m r + 。 : + ( l 一 t 冲 m + k 由( l ) 得: ( 、 一 ， ， : ) 0 由( 2 ) 得: ( d - t ) 2 4 m n + 4 ( 1 一 t ) k 。 由于d - t 二 ， 则d t + 2 , d 2 k + t 或 ， 。 ， ， +( l 一 t ) k k + l + 竿 d m , 11k， 于 是 、 : in a x (t + 2 v 6 -n n + (1 - t)k ,k + l + 竿 ) =( ，一， 了 ) + 图论 中的若干极值问题 郊秋歌 如 果k + l + 警 2 k + t ， 即 g 一 “ + 竿: 因 为 0 ， 所 以 二 ( t + 2 沪n n + ( l 一 ) k , 2 k + t ) = t + 2 , / m n + (l 一 ; ) k _ 2 v m n + i k . 重新整理上面的结果， 我们有: 如 果k 警， d 2 侧 m n + l k 如 果臀_ m in ( 2 m n + i k , k + l + 竿) 一 2 / .- n + !k 如 果无 十 mt n , d _ k + l + -v. 由 上述讨论知， 存在正整数r , s 和非负整数t 使得2 . 1 成立当且仅 当: ( i ) 如 耘 1 十 竿，“ 2 m n + l k ( ii) 如 果 k l + 竿，“ k 十 l + 臀 因此定理成立二 注. 根据这个定理， 对于任意给定的正整数， , n , k 及非负整数l ， 我们 可 以 求 出(m , n ,k ; l) 图 可 能 取 得 的 最 小 阶 数 当 _ k 一 警时 ， 最 小 阶 数 为 ， 二 m + ” 十 2 m n + ik ; 当 n ， 斗 n + m in ( 2 m tt , k + 警) 一 ” t + n + 2 而n . 因 此 我 们 有 : 推论2 .4 .2 ( 7 1 ) . 设g 为p 阶图 ， 且g中 每个顶a 既包 含在一个( n e + i ) - 团中，又包含在一个 n +约 一 独立集中.则g存在当且仅当p n e + n + 2 了 n u i . 另外，由伽, k , l ; n ) 图的定义可知， 它包含至少l 个互异的帅+ k + i ) 一 团，如果我们要求图中包含恰好l 个互异的伽+ k 十 1 ) 一 团， 则定理 的结论依然成立， 这是因为如果恤, k , l ; n ) 图中 包含大于l 个的互异的 如+ k 十 ) 一 团， 则如我们 在引 理2 .3 .2 的证明中的那样， 取g 的一个团 集粗盖犷，然后把其余的边都去掉，则我们得到的就是包含恰好1 个 互异的( m+ * 十1 卜团的图. 图论中的若千极值问题 郭秋敏 推论2 .4 . 3 . 设m , n , k , p 是正整数，1 为非负整数，p 阶图g中的每个顶 3 、 既包 含在一个( m + 1 ) 一 团中 ， 又包 含在一 个( n 十 1 ) 一 独立集中， 且g中 包含恰好l 个互异的( m + k +l ) 一 团.则图g存在当且仅当: ( 1) 如 果 k 一 警， m + n + 2 、 m n + lk ( “ ) 如 果 l _ m + n + k + l + 平 图论中的若干极值问题 郭秋敏 3 . 图的极小键斑盖 3 . 1 . 图的斑盖问题 用给定的某类子图， 如团、匹配、 树、圈、 路等来覆盖一个图的 边， 这 是图 论中 的 一 类基 本问 题.e r d o s 、g o o d m a n 和p 6 s a 8 证明 了 任意一个n 阶图 的所 有边可以 用至多l n 2 f 4 个两两 边不交的团 来覆 盖 ， 并 且t u r fi n 图t,2 = k ln l 2 j ,fn l 2 表明 这 是 最 好 的 可 能 结 果.g y d r i 和 k o s t o c h k a 1 4 ,c h u n g 6 以及k a h n 1 9 随后又各自 独立地证明了一个更 强的结果:任何一个n 阶图g 可以分解成若干个团，使得这些团的阶 数 和( o r d e r s u m ， 即 所 有这些团 的阶 数 之和 ) 不 超过时/ 2 j . 从那以 后， 一大批的这类问题开始被研究. 例如， t u z a 2 9 证明了 任 何一 个。 阶图的 边都可以 用至多。 一 l o g n j 十 1 个完 全二部 子图 来 覆 盖. 这也是最好的可能结果，因为r b d l 证明了 存在这样的图，它需要 用n - c l o g 一 个完 全二部子图来覆盖.k a t o n a 和s z e m e r 6 d i 2 0 则证明了 完全图k的完全二部子图 覆盖的阶数和( o r d e r s u m ) 至少是。 l o g n ， 且 存在阶数和为。 f l o g 川的 覆盖.r e z n i c k , t i w a r i 和w e s t 2 6 以及k r a t z k e , r e z n i c k 和w e s t 2 2 则用g 的关联矩阵的特征值对覆盖e ( g ) 所需的完 全二部子图的个数进行了 研究. p y b e r 2 5 在他的名为c o v e r in g t h e e d g e s o f a g r a p h b y . 的一篇综 述中， 定义c o v ( g , 9 f ) 为用x中的图覆盖侧句时所需要的图的最小个 数. 类似的， 定义c o v ( g , 州 为用9 f 中的图分解到g ) 时 所需要的最小 个数. 若令9 f 为g 中的团 构成的集合， 则由 8 有: c o v ( g , 川 3 的完全图都可以用三角形 来 援盖， 但它能分解为若干个三角 形当且仅当n 三1 , 3 ( m o d 6 ) . 它的必 要性是因为图的边数要能被3 整除，并且每个点的点度必须为偶数; 关于它的充分性， 这是组合设计理论中最古老的结果之一，图的一个 分解就等价于一个s t e in e r 三元系( s te in e r t r ip le s y s te m ) 从某种意义上来说，对一个图最有效的覆盖就是使得尽可能少的 边被覆盖的次数大于 1 .基于这一点，我们定义图g 相对于某类子图 x的粗盖大小( c o v e r in g s i z e ) 为用x中的图覆盖g 时所得到的所有覆盖 图 论 中 的 若 千 极 值 问 题_一 .一 些 燮 中的最小总边数， 记为c s ( g , h) .即: c s ( g , h ) := m in y e ( h ) : u e ( h ) = e ( g ) , h h . 图g的一个覆盖称为是最优覆盖，如果该覆盖中的边数之和恰好等于 图的覆盖大小. 因 此，c s ( g , 州 = e ( 句当且仅当g 能被h中的子图 分解. 从这个 意义上来说，c s ( g , h ) 一 e ( g ) 衡量了图g 离能被h分解相差有多远. 如果h的每个元素都有k 条边， 例如h是连通图g 的所有支撑树的集 合， 则c s ( g , 州 = k - c o v ( g , h) . 而对于一般的非平凡倩况来说， 要计算 c s ( g , 川 是非常困 难的， 甚至只 是对c s ( g , 哟 进行某些估计都是非常不 易的. 这一章， 我们将考虑用键( b o n d ) 来覆盖连通图g ， 并且对图的 键覆盖大小进行讨论. 3 .2 . 图的键扭盖 连通图g 的一个键覆盖是指g 中 键的 一个集合c = s , , s i 1 , s 2 , 及 ， , s k ,s k ， 使 得乙 s i, s i 一 : (g ) ， 其 中 s i, s i 是 g 的 键 。 。 的 键 覆 盖 i =t 大小记为b c s ( g ) ， 根据我们前面的定义，即是: b c s ( g ) := c s ( g , g 中 的 键 ) . 显然，当g不连通时，g不存在键覆盖为了保证图g的键覆盖 存在， 我们只对连通图进行讨论. 在下一节， 我们将首先证明: 任何连 通图都存在键覆盖. 在此之前，已 经有一些对图的边割覆盖的研究. 记g 的边割覆盖 为。 s s ( g ) : = c s ( g , s , 3 1 1 ) ，则对完全图k n ， 我们有( 1 7 , 1 8 , 2 1 , 2 3 1 ) : ， 一 、f (。 一 1 ) 2 t i n 一 ) 一 ， n 尹4 , 8 n =4 , 8 对至少有8 个点的完全图， 它的最优边割攫盖在同构意义下是唯一 的. 对。 8 ， 我们可以用11 一 1 个 边割来覆盖凡 : ， 其中每个s ， 是由 一个点 构成的集合。 对。 二 8 ， 可以 用3 个k 4 ,4 来覆盖k g ， 其中is i 一 4 , is i n s , 一1 ( i ii ) 且s i 自 s z 门 s 3 二1 . 对一般的图，若令 c u t ( g = m u x i (s , s 卜 s c v ( g ) i c u t ( g ) := m a s i fs , s i : s 是独 立集 则显然c u t ( g c u t ( g ) 以它们为参数，f ii r e d i 和k ii n d g e n 9 得到了 图论中的若干极值问题 郭秋敏 c c s ( 甸的一个如下估计结果: 2 e ( g ) 一 。t ( g ) c c s ( g ) c c s ( g ) . 作为这一章的主要结果， 我们 将证明， 事实上有b c s ( g ) = c c s ( g ) 成立. 3 .3 . 被 彼盖的 存在性 这一节，我们首先来讨论图的键覆盖的存在性问 题.显然对于非 连通图g, g 不存在键覆盖，因此要讨论图的键覆盖，至少要求g 是 连通图.那么， 这一条件是否就足以保证g 存在一个键覆盖呢? 答案 是肯定的， 这就是我们在这一部分所要证明的结果. 引理3 .3 . 1 . 设g 是块，r i1 g 有健在盖. 证明 : 我们 直 接来构造g 的 一 个键覆盖.v v e v ( g ) ， 令 s , = t v ,瓦= v ( g ) v , 由 于g 是块， 所以s ， 的导出 子图 连通.因此s , s 是一个键， 它覆盖 了所有以， 为一个端点的边. 若令 c = s v , 瓦 : v e v ( g ) ) 则 是 g的一个键覆盖二 引理3 . 3 .2 . 设。 i , g : 有键覆盖， 且v ( g i ) n v ( g 2 ) 卜 1 ，r 1 g , u g : 也有 键在盖，且b c s ( g 1 ( _) g 2 ) = b c s ( g i ) + b c s ( g 2 ) 。 证 明: 设g= ( s i , s 1 , . . . , s k , 酗 和c 2 二 s i , s i ) , . . . , s , s i) 分 别为g i 、 g : 的一个最优键覆盖， 记v ( g i ) 自 v ( g 2 ) = u ， 不 妨设u s l ( v i i k ) ， u e 另 (v i j b s ( g i ) + b s ( g 2 ) . 设 _ s l , s l l , . . . , s m , s n ,l 是g i u g : 的一个最优键覆盖， 且不妨 设。 e s i ，( 1 i m ) . 令 ( s i v ( g i ) ) u n , ( s j v ( g 2 ) ) u n , =v ( g 2 ) s i , = v ( g i ) 必 ， 1 三i 兰k , k +1 j m 一si-乳 则 v i i _ b c s ( g i ) + b c s ( g 2 ) 。 定理3 .3 . 3 . 任意连通图都存在健友盖. 证明: 若g 是块，由引理3 .3 . 1 知g 有键覆盖，因此只需对g 不是块的 情况进行证明. 对g 的顶点数进行归纳.当!v ( 叨卜2 时，g 显然有 键覆盖. 设v ( g ) 3 ) 时，g 有键覆盖， 我们 考虑v ( g ) l = n 时的 情况.任取g中的一个块b ， 则g 一 e ( b ) 被分成若干个连通分支， 不 妨设为gi,.-,gk.由 归纳假设，g : ， ， g * 有键覆盖， 且v i e ( g ) 即得到b c s ( g ) = e ( g ) . 反过来， 若b c s ( g ) = e ( g ) ， 我们 证明g 必为二部图. 若不然， 则 g中含有奇长圈c.因为g的任何一个键所包含的c 的边数必定是偶 数， 因此c中 存在被覆盖次数大于一次的边， 即得b c s ( g ) e ( g ) ， 矛 盾，因此，g 为二部图二 定理3 .4 . 2 . 设g是连通图，则b c s ( g ) = c c s ( g ) . 证明: 设 = s1,311,. , s k , s k 是g 的一个最优边割覆盖， 即c c s ( g ) = 直 is l,s kii . 我 们 由 出 发 来 构 造 一 个 g 的 键 覆 盖 。 ， 使 得 。 中 的 边 ( = 数之和等于c c s ( g ) . 任给s , 3 1 ， 若s , s 是g的一个键， 则直接将 s , 3 1 作为， 的一个元素; 若 is 司 不是键， 不妨设s 的点导出子图的连通分支为 g i , g 2 , . , g r , s 的点导出 子图的连通分支为h i , h 2 , . , h r ， 如下图所 小 。 h,场 m 1 : 1s , 习 则我们 来用 若干个 键重新n盖s , s 中的边， 并使得1s , 3 1 的边只被 覆盖一次。 若将s 和s 中的每个 连通分支看成一个点， 则s , s 的边导 出子图可以看成一个连通二部图. 而由 命题3 .4 . 1 ， 连通二部图存在键 w l 盖，使得每条边只被租盖一次，因此存在g的若干个键，这些键搜 盖s 冈的边恰好一次， 我们 将这些键作为，的元素. 图论中的若干极值问题郭秋敏 对c中的所有边割都通过上面方法进行变换之后，我们就得到g 的一个键覆盖 ，且，的大小等于c ，即，中所有键的边数之和等 于c c s ( g ) ， 因此b c s ( g ) c c s ( g ) ， 即得 b c s ( g) =c c s ( g ) 二 根据这一定理，讨论连通图的键覆盖大小的问题就可以 转化为研 究它的边割覆盖大小的问题，而图的边割覆盖相对来说要容易一些， 并且对边割覆盖已有的结果对键筱盖同样成立. 另外，还可以考虑覆盖一个连通图时所需要的键的最少个数.对 图的边割覆盖， 这一间题已 经解决， 任何一个图可以 用f l o g x ( g ) 个边 割来覆盖， 并且f l o g x ( g ) 1 是所能达到的 最小值.n e u m an n - i a r a , r i v e r a - c a m p o 和u r r u ti a 2 4 考 虑了2 一 连 通图 的 键 覆盖， 得到了 下面 的 结论: 任 何一 个2 一 连 通图 可以 用 至 多咭 c l 个 键 覆盖 ， 其中。 为图 的 周 长 ， 即 图的最长圈的长度. 图论中的若千极值问题 郭秋敏 参考文献 1 b . b o l l o b d s , e x t r e m a l g r a p h t h e o r y , a c a d e m ic p r e s s , n e w y o r k / l o n d o n , 1 9 7 8 . 1 2 1 j a. b o n d y a n d u . s .r . m u rt y , g r a p h t h e o ry w i t h a p p l i c a t i o n s , m a c m i l l a n , l o n d o n , 1 9 7 6 . 3 1 g . c h a r t r a n d , h . g a v l a s , a n d m. s c h u l t z , f r a me d ! a g r a p h e m b e d d i n g p r o b l e m, b u l l i n s t c o m b i n a p p l 4 ( 1 9 9 2 ) , 3 5 - 5 0 . 沪 g . c h a r t r a n d , m. a . h e n n i n g , h . h e v i a a n d e , j a r r e t , a n e w c h a r a t e r i z a rt i o n o f t h e p e t e r s e n g r a p h , j c o m b i n f o s y s t s c i 2 0 ( 1 9 9 5 ) , 2 1 9 - 2 2 7 5 1 g . c h a r tr a n d a n d l . l e s n i a k , g r a p h s &d i a g r a p h s , t h i r d e d i t i o n . w a d s w o r t h & b r o o k s c o l e , mo n t e r e y ( 1 9 9 6 ) . 6 1 f r x. c h u n g , o n t h e d e c o m p o s i t i o n o f g r a p h s , s i a m j . a l g e b r a i c d i s c r e te ma t h . 2 ( 1 9 8 1 ) 1 - 1 2 . 7 1 r .c . e n t r i n g e r , w . g o d d a r d a n d m.a . h e n n i n g , a n o t e o n c l i q u e s a n d i n d e p e n d e n t s e t s , j g r a p h t h e o ry 2 4 ( 1 9 9 7 ) , 2 1 - 2 3 . 8 p e r d 6 s , a .w g o o d m a n a n d l . p 6 s a , t h e r e p r e s e n t a t i o n o f a g r a p h b y s e t i n t e r s e - ti o n s , c a n a d . j . ma t h 1 8 ( 1 9 6 6 ) 1 0 6 - 1 1 2 . 9 z . f il r e d i a n d a . k u n d g e n , c o v e r i n g a g r a p h w i t h c u t s o f m i n i m u m t o t a l s i z e , d i s - c r e t e ma t h . 2 3 7 ( 2 0 0 1 ) 1 2 9 - 1 4 8 . 1 0 1 h . g a v l a s , m. a . h e n n i n g a n d m. s c h u l t z , o n g r a p h s a n d t h e i r f r a m e s , v i s h w a i n - t e r n a t i o n a l j g r a p h t h e o r y 2 4 ( 1 9 9 2 ) , 1 1 1 一 1 3 1 . 川 wg o d d a r d , m.a . h e n n i n g a n d h . ma h a r a j , h o m o g e n e o u s e m b e d d i n g s o f c y c l e s i n g r a p h s , g r a p h s c o m b i n 1 5 ( 1 9 9 9 ) , 1 5 9 - 1 7 3 . 1 2 1 w. g o d d a r d , m.a . h e n n i n g , o .r . o e l l e r m a n n a n d h .c . s w a n , s o m e g e n e r a l r e s u l t s o n t h e f r a m i n g n u m b e r o f a g r a p h , q u a e s t i o n e s ma t h 1 6 ( 1 9 9 3 ) , 2 8 9 - 3 0 0 1 3 1 w. g o d d a r d , m. a . h e n n i n g , o .r . o e l l e r m a n n a n d h .c . s w a r t , wh i c h t r e e s a r e u n i q u e l y f r a m e d b y t h e h e a w o o d g r a p h , q u a e s t i o n e s ma t h 1 6 ( 1 9 9 3 ) , 2 3 7 - 2 5 1 . 1 4 e . g y o r i a n d a .v . k o s t o c h k a , o n a p r o b l e m o f g .o .h . k a t o n a a n d t .t a r j a n , a c t a ma t h . a c a d . s c i . h u n g a r . 3 4 ( 1 9 7 9 ) 3 2 1 - 3 2 7 . 1 5 1 m. a . h e n n i n g , o n e d g e c l i q u e s a n d e d g e i n d e p e n d e n t s e t s , b u l l i n s t c o m b i n a p p l i c 1 8 ( 1 9 9 6 ) , 7 5 - 8 1 . 1 6 m. a . h e n n i n g , o n c l i q u e s a n d b i c l iq u e s , j g r a p h t h e o r y 3 4 ( 2 0 0 0 ) , 6 0 - 6 6 . 1 7 1 f j a e g e r , a . k h e l l a d i a n d m. mo l l a r d , o n s h o r t e s t c o c y l e c o v e r o f g r a p h s , j . c o m b i n .