（运筹学与控制论专业论文）几类图的匹配、点独立集、点极大独立集的计数.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 本论文在前人研究的基础上，进一步研究了儿类图独立集，匹配和极大独立集 的计数问题主要内容包括： ( 1 ) 在第一节和第二节介绍了本文研究的背景和研究意义，以及国内外在这方 面具有代表性的发展状况通过对本文研究背景及研究现状的深刻讨论，充分说明 了本文的主要研究工作的必要性和创新性最后，给出了本文涉及到的部分记号和 引用的引理 ( 2 ) 在第三节，我们主要对双圈图的独立集计数进行了研究，给出了双圈图独立 集的上下界，并给出了达到上下界时对应的图； ( 3 ) 在第四节，我们主要对q u a s i 一树图的独立集计数和匹配计数进行了研究，给 出了第一大，第二大上界和第一小，第二小下界，对应的极图也进行了刻画，同时我 们也给出了含忍个叶子的q u a s i 一树的匹配计数的下界及其对应的极图； ( 4 ) 在第五节，我们主要对圈秩个数至多为2 的连通图的极大独立集计数进行了 刻画，给出了上界，并刻画了达到上界时对应的图； ( 5 ) 在第六节，我们主要在g c y i n g ，k k m e n g ，b e s a g a n s t l v r 。v a t t e r m a x i m a li n d e p e n d e n ts e t si ng r a p h sw i t ha tm o s trc y c l e s ，j g r a p ht h e o r y , 5 3 ( 2 0 0 6 ) ， 2 7 0 - 2 8 2 1 的基础上，对至多有r 个圈的图第二大极大独立集计数进行了刻商，给出了 极大独立集达到第二大的界，对应的给出了达到第二大界的图。 关键词：独立集；匹配；极大独立集；双圈图；圈秩；q u a s i 一树图 硕士学位论文 m a s t e r st h e s i s a b s t r a c t t h i sp a p e rw h i c hs t a n d so nt h eb a s i so fp r e v i o u sr e s u l t s ，a n dw h i c hf u r t h e r r e s e a r c ho nt h ei s s u eo ft h en u m b e ro fi n d e p e n d e n ts e t s ，m a t c h i n gs e t sa n dm a x i m a l i n d e p e n d e n ts e t sf o rs e v e r a lg r a p h s ，m a i n l yi n c l u d e s ： ( 1 ) o nt h ef i r s ta n ds e c o n ds e c t i o n s ，w ei n t r o d u c et h ep a p e r sr e s e a r c hb a c k - g r o u n da n ds i g n i f i c a n c e ，i n c l u d i n gt h ed e v e l o p m e n to far e p r e s e n t a t i v ea th o m ea n d a b r o a dr e g a r d i n gt h i sa s p e c t b a s e do nt h i sr e s e a r c hb a c k g r o u n da n dp r o f o u n dd i s - c u s s i o no nt h es t a t u sq u o ，i tf u t l ys h o w st h em a i nw o r k sn e c e s s i t ya n di n n o v a t i o n ( 2 ) o nt h et h i r ds e c t i o n ，w ed e t e r m i n eu p p e ra n dl o w e rb o u n d sf o rt h en u m b e r o fi n d e p e n d e n ts e t si nab i c y c l i cg r a p hi nt e r m so fi t so r d e r ，w ed e t e r m i n eu p p e r b o u n df o rt h et o t a ln u m b e ro fi n d e p e n d e n ts e t si nac o n n e c t e dg r a p hw h i c hc o n t a i n s a tl e a s tt w oc y c l e s i ne a c hc a s e ，w ec h a r a c t e r i z et h ee x t r e m a lg r a p h s ； ( 3 ) o nt h ef o u r t hs e c t i o n ，w ed e t e r m i n et h el a r g e s t ，t h es e c o n d - l a r g e s t ，t h e s m a l l e s ta n dt h es e c o n d - s m a l l e s tn u m b e ro fi n d e p e n d e n ts e t si nq u a s i t r e eg r a p h s f o ro r d e rn ，t h e nw ec h a r a c t e r i z et h en - v e r t e xq u a s i t r e eg r a p h sw i t ht h el a r g e s t ， t h es e c o n d l a r g e s t ，t h es m a l l e s ta n dt h es e c o n d s m a l l e s tn u m b e ro fm a t c hs t e s ，a s w e l la st h o s en - v e r t e xc l u a s i t r e eg r a p h sw i t hkp e n d e n tv e r t i c e sh a v i n gt h es m a l l e s t n u m b e ro fm a t c hs e t s ，t h ee x t r e m a lg r a p h sa r ea l s oc h a r a c t e r i z e d ( 4 ) o nt h ef i f t hs e c t i o n ，w ed e t e r m i n et h el a r g e s tn u m b e ro fm a x i m a li n d e p e n - d e n ts e t sa m o n ga l lc o n n e c t e dg r a p h so nnv e r t i c e sw i t hc y c l o m a t i cn u m b e r 叼，f o r 叼2 w ea l s oc h a r a c t e r i z et h o s ee x t r e m a lg r a p h sa c h i e v i n gt h em a x i m u mv a l u e s ； ( 5 ) o nl a s ts e c t i o n ，e s t a b l i s h e do nt h ef o l l o w i n ga r t i c l eg c y i n g ，k k m e n g ， b e s a g a n ，a n dv r v a t t e r m a x i m a li n d e p e n d e n ts e t si ng r a p h sw i t ha tm o s tr c y c l e s ，j g r a p ht h e o r y , 5 3 ( 2 0 0 6 ) ，2 7 0 2 8 2 ，w ed e t e r m i n et h es e c o n dl a r g e s tn u m b e r o fm a x i m a l i n d e p e n d e n ts e t sf o rt h eg r a p hw i t ha tm o s trc y c l e s ，t h ee x t r e m a lg r a p h s a r ea l s oc h a r a c t e r i z e d k e yw o r d s ：i n d e p e n d e n ts e t s ；m a t c h i n g s ；m a x i m a li n d e p e n d e n ts e t s ；b i c y c l i c g r a p h ；c y c l o m a t i cn u m b e r ；q u a s i t r e eg r a p h i i 硕士学位论文 m a s t e r st t t e s i s 华中师范大学学位论文原创- 陛声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者躲粤牛吼秒7 年钿口 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华 中师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 导师签名： 嘭多丝 日期夕年莎月日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中 的规定享受相关权益。同意论文提交后滞后：口半年；口一年；口二年发布。 作者签名：謦、睁 b 鞠：oj 年占弱fb 节吖 孑“ ：n、1， 名d 签 ： 者期怍日 2、rrt 坌户 巷月 ， 年：力、， 轹哆 签 师期 第一节绪论 本节首先介绍了课题的研究背景及研究意义与国内外研究现状 1 1研究背景及研究意义 图的独立集的和，我们用参数i ( g ) 表示，它是图论中研究图的一个重要指标， 在工程，管理等学科和实际生活中有主要的应用同时l ( g ) 也被称为f i b o n a c c i 数， 我们知道f i b o n a c c i 是一个很有趣的数列，对它的研究成果也有很多而在化学 中i ( g ) 也被称为m e r r i e l d s i m m o n 指标，简称m s 指标，它是一个十分有用的化学拓 扑指标，此指标与物质的沸点有很大的联系图的匹配的和，我们用z ( g ) 表示，它与 独立集是对偶关系化学中称为h o s o y a 指标，简称h 指标，它也是一个很重要的化 学拓扑指标，此指标与物质的沸点，熵，化学键的计算和化学结构等有很大的联系 陶的极人独立集和，我们用m i ( g ) 表示，显然，极大独立集是独立集的子集，他也是 图论中一个重要的图指标 1 2本课题国内外研究现状 图的独立集个数，记做i ( g ) ，为图g 的所有独立集个数的和i ( g ) 也称为图 的f i b o n a c c i 数路r 的f i b o n a c c i 数即是原f i b o n a c c i 数列巾的r + 】，也许这就是 称i ( g ) 为图的f i b o n a c c i 数的原因文献f 2 2 1 在1 9 8 2 年首先对此问题进行研究，之 后，人们对图的f i b o n a c c i 数进行了广泛的研究而计算一个图的独立集个数是 一个n p 一完全问题f 见文献r o t h 2 3 ) 对于要确定一个为n p 一完全问题的图参数 来说，我们转而确定它的界则是非常有意义的，通常也是可行的文献1 3 ，1 4 ， 7 1 对树的f i b o n a z c i 数进行了研究，确定了树的f i b o n a c c i 数的上下界在礼阶树中 路r 具有最小的f i b o n a c c i 数，而硒凡一l 具有最大的f i b o n a c c i 数文献【1 4 】对两类 树的f i b o n a c c i 数进行了研究，并由此给出了住阶树第二小，第三小的界和对应的 图；文献f 1 5 1 则是独立的对树和森林的情形进行了研究；文献f 1 6 1 对给定直径的 树进行了研究；文献f 2 8 】则对给出最大度的树进行了研究，而文献 3 8 则是对给 出度的界的树进行了研究；文献2 6 1 对有尼个叶子的树进行了研究；文献2 】给出了 极大平面图的f i b o n a c c i 数的上界；文献f 2 7 1 和2 8 1 分别对苯链和c a t a c o n d e n s e d 系统 的f i b o n a c c i 数进行了研究后面文献f 2 1 ，2 4 ，3 5 科i 继对单圈图或给出限制条件的单 圈罔进行了研究，给出了其f i b o n a c c i 数 图的匹配数，记做z ( g ) ，为图的所有匹配个数的和它首先由h o s o y a 于1 9 7 1 年提 出并进行研究文献f 3 3 ，2 6 ，1 8 ，1 6 1 分别对树，给定叶子的树，具有最大度的树和给 1 定直径的树的匹配数和进行了研究，在n 阶树中路r 具有最大的匹配数，而k x 具,n-1 有最小的匹配数文献 3 4 贝j j 对单圈图的匹配树和进行了研究；在文献 3 6 ，3 7 】中定 义t q u a s i 一树图，并分别对q u a s i 一树图的图谱s h r a n d i d 指标进行了研究q u a s i - 树图 即图g 存在点札。使得g 一伽为树，显然当锄为叶子时，g 就是树，当u o 的度大于1 时， q u a s i - 树图的结构就比较复杂了，他包含的圈的个数也随着乱。的度发生了变化，g 可 能是单圈图，也可能是含三个圈的双圈图故q u a s i 一树图既包含了我们常见的树，单 圈图等? 也包含了许多结构较复杂的图，它是一类很大的图类 e r d 6 s 和l m o s e r 第一次提出了计算图的极大独立集的个数的问题，文献【2 0 】对此 进行了研究，文献f 4 9 ，4 2 ，4 3 1 等各自独立的对一般图情形进行了研究文献 5 1 1 对树 的极大独立集数进行了研究；f 4 5 对不含三角形的图的极大独立集进行了研究；文 献晦4 1 对二部图的极大独立集计数进行了研究；文献【4 7 】对至多含一个圈的图的极 火独立集进行了研究：随后文献 5 0 l 对两大类图的极大独立集进行了研究，其中一 类是至多含有7 个圈的竹阶图：对应的极图是以多个托和拖为连通分支组成；另一 类是至多含有r 个圈的n 阶两通图，其中n 3 r ，对应的极图是以，配为块最近 文献f 1 8 ，4 4 1 分别对f 4 3 1 中研究的一般图的第二大和第三大极大独立集上界进行了 研究，并给出了对应的极图 1 3本文主要解决的问题 第一节：对本文研究意义和背景的简介： 第二节：预备知识和记号： 第三节：对双圈图的f i b o n a c c i 数进行了研究，给出了它的上下界，并给出了对 应的极图，本文中求上界的方泫较【6 1 中的简单； 第四节：对q u a s i 一树图的f i b o n a c c i 数和匹配的计数进行了研究，给出t q u a z i 一 树图f i b o n a c c i l 拘第一，第- - 2 ：界和第一，第- - t 界，同时也确定了含k 个叶子 的q u a s i - 树图的匹配数的下界，各种界对应的极图也分别作了刻画； 第五节：对至多含有2 个圈秩的图的极大独立集的计数进行了研究，给出了至 多含有2 个圈秩的图的极大独立集的上界，刻画了对应的极图； 第六节：对g c y i n g ，k k m e n g ，b e s a g a n ，和v r v a t t e r m a x i m a li n d e - p e n d e n ts e t si ng r a p h sw i t ha tm o s trc y c l e s ，j g r a p ht h e o r y , 5 3 ( 2 0 0 6 ) ， 2 7 0 2 8 2 6 p 的至多含有r 个圈的一般图的第二大极大独立集的计数进行了研 究，给出了第二大上界，对应的极图也作了刻画 2 第二节预备知识及记号 2 1基本记号与定义 本文所说的图g = ( ve ) 都是简单，无向图图g 的点集合和边集合分别 用y ( g ) ，e ( g ) 表示 定义2 1 图g 的一个点z 所有邻点形成的集合成为此点的开邻域，记为g ( z ) ， 开邻域与z 的并称为点z 的闭邻域，记为g 旧= zu ( z ) 开领域和闭领域一般简 记为( z ) ，n x 1 点z 称为孤立点，若g ( x ) = d ，称为叶子，若i n ( x ) l = 1 定义2 2 图g 的两个点称为独立的，若此两点不相邻图g 的一个后元点子集称 为七一独立集( 或独立集) ，若止h k i r , 子集中任意两点都不相邻 对任意的图g ，我们用i ( g ，七) 表示g c p k - 独立集的个数，且约定 ( g ，0 ) = 1 ， 记g 的所有独立集形成的集合为，( g ) ，记 i ( g ) ：= i i ( a ) l = i ( g ，七) k = o 定义2 3 图g 的一个独立集s 称为g 的极大独立集，若g 不包含适合sc 的 独立集n m i ( g ) 表示g 中极大独立集的个数 定义2 4 给定图g ，并$ d i s t ( x ，可) 为图中从z 到可的最短路的距离，其中z ，可在g 的 同一连通分支 定义2 5 图g 的圈秩7 7 定义为7 7 ：= e ( g ) 一v ( c ) + 1 显然，由上面的定义我们知道：当叼= o 时，g 是树；当7 7 = 1 时，称g 为单圈图； 当叩= 2 时，称g 为双圈图 定义2 6 图g 的一个没有一个割点的极大连通子图称为此图的块称g 中的块 为端块，若此块仅含有g 中的一个割点 定义2 7 称r 为第礼个f i b o n a c c i 麦炙，若r = r 一1 + r 一2 ，其中f o = 1 ，f l = 1 ，n 2 3 下面我们给出一些记号，若y ( g ) ，我们用g 一表示g 除去中的点 和与这些点关联的边后得到的子图类似的，若e 7ce ( g ) ，我们用g e 7 表 示g 除去e ，中所有边后得到的子图特别的，当w = u ) ，e 7 = ( z 可) 时，我们分别 用g 一 ，c x y 4 潜a 一 u ) ，g 一 z 可 g + z 可表示把g 中不相邻的点z ，用一边 相连最后我们用尸n ，瓯和k 1 , n - - 1 分别表示佗个点的路，圈和星图 2 2引理 对任意的图g 和日，规定：g u 日表示g 和日的不交并，对任意非负整数，用g 表 示t 个g 的比较并g + 表示图g 和h 任意两点之间连边 引理2 8 ( 【7 】) 设g = ( ve ) 为礼阶图 ( i ) i 殳u v e ( g ) ，则i ( g ) = i ( g u v ) 一i ( g 一( n u 】u u 】) ) 和z ( g ) = z ( a 一 ? z v ) + z ( c u ，u ) ) j ( i i ) 设口y ( g ) ，则 ( g ) = i ( g u ) + i ( g 一【 】) 和z ( g ) = z ( a 一 ) + 。( 。) z ( a 一 u ，u ) ) j ( i i i ) 设g 1 ，g 2 ，g 。为图g 的不同分支，则i ( g ) = n ；：li ( 岛) 和z ( g ) = 呓：lz ( q ) 引理2 9 ( 1 5 】) 设t 为住阶树，则r + 1 i ( t ) 2 n 一1 + 1 ，左边等式成立当且 仅当t 竺r ，右边等式成立当且仅当t 笺k 1 ，n 1 我们用巩七表示竹一七个叶子粘到一个尼阶圈的某个点上得到的图 引理2 1 0 ( 2 1 1 ) 设g 为礼阶单圈图，若g 箬巩，3 ，则i ( g ) 5 2 铲4 + 2 ，等式 成立当且仅当( i ) g 笺巩，4 ，或( i i ) g 为一个叶子和n 一4 个叶子分别粘到岛的两个不 同点上 引理2 1 1 ( 【7 】) 设t 1 为n 阶的树，则n z ( t ) r ，左边等式成立当且仅 当t 竺k l 。n l ，右边等式成立当且仅当t 笺r 引理2 1 2 ( 【1 6 】) 设h ，x ，y 为两两不交的连通图u ，口为日的两个点，为x 的 点。牡，为y 的点设g 由x 中的口7 与日中的u 粘合，y 中的点札7 与h 中的点“粘合得到 同样的设g ；由日，x ，y 的点口，口，? z 7 粘合得到，g ；d ah ，x ，y 的点让，口7 ，乱7 粘合得到( 如 图j 所示) 则有 i ( g ：) i ( g ) ，或i ( q ) i ( g ) z ( g ：) 易r 一2 r r 一4 b m 岛m + r 尼m l r m + r + l r i 一3 f 2 m + r + 3 玛r 一3 r r 一1 ( i i ) 若r 2 ，3 ，则有 昂r r r 一2 r r 一4 f 2 m f 2 。+ r f 2 m + l r m + r l f 2 m 一1 f 2 m 十件1 f 3 r 一3 只r 一1 引理2 1 5 ( 【2 9 ，3 3 】) 设丁磊 k 1 扩1 ，p n n - 2 ，r ) ，则 z ( 研，n 一1 ) z ( r ，n 一2 ) z ( t ) 夕( m ，r ) ) ( i i ) 若r q2o 且n 3 r 一1 ，则有g ( n ，r ) 9 ( 佗，q ) 当且仅当几，r 奇偶性不同 _ g - q = r 一1 时取等号 ， 设佗2 ，定义 劬卜 溉黜嘞舞爱m o d3垂) 利用公式m i ( guh ) = m i ( g ) m i ( h ) 可得 夕c 扎，：= m t c g c 佗，= 3 等。 4 3 孚， 2 3 孚 若n 三0 若扎三1 若死三2 ( m o d3 ) ； ( m o d3 ) ； ( m o d3 ) 引理2 2 7 ( 【4 6 】) 设g 为n 3 阶的图且g 笋g ( 佗) 则有m i ( g ) ( n ) 其中 坳，= 豢萋赫；( m o d 3 l 8 硕士学位论文 m a s t e r st h e s i s 当且仅当g 望日( n ) 时取等号，其中 ( n ) ： ( 配木凰) u ( s 一2 ) 配，或3 u ( s 一2 ) 配， 或心u 恐u ( s 一2 ) 尥， ( 心丰) u ( s 一2 ) ， 若仡兰0 若扎三1 ( r o o d3 ) j ( r o o d3 ) j ( 木配) u ( s 一2 ) 配u 鲍，或4 k 2u ( s 一2 ) 配， 或心u2 虬u ( s 一2 ) 配，或2 心u ( s 一2 ) 凰，若n 三2 ( r o o d3 ) j 9 第三节双圈图的独立集计数 文献 6 1 研究了双圈图独立集的上界，在第- - d 节我们将用更简单的方法给出 双圈图的上界，刻画对应的极图在第二小节我们将刻画双圈图独立集数的下界及 其对应的极图设u 为图g 的一个叶子，“为其唯一的邻点，由引理2 7 ，我们有i ( g ) = l ( g u ) + i ( g 一 u ，乱) ) 通过定义和简单的计算，我们有i ( p o ) = 1 ，i ( 尸1 ) = 2 ， 且i ( r ) = i ( r 1 ) + i ( r 一2 ) ，其中r , 2 我们得到 一= 去l ( 学) n + 2 一( 学门 又由r + m = r 矗+ r l r l ，故规定当7 , 0 时，r = 0 由引理2 7 ，我们可以得 到一个重要的结论：对任意e e ( g ) ，i ( g ) i ( g e ) 给出整数礼和七其中3 k 仡，我们用l 砒表示由一条边连接伉的点季l ：l p n 一是的 端点乱形成的n 阶图 弓l 理3 1 i ( l 露，奄) = f k 一2 f 一七+ j k j k 南十1 证明：由引理1 1 ，l n , k d ? 包含u 的独立集的个数为i ( k ，七一 札】) = i ( p k 一3 ) i ( p n 一七一1 ) ，不包含乱的独立集的个数为i ( l m 七一u ) = i ( p k 一1 ) i ( r 一七) ，则有， i ( l 七) = i ( r 一3 ) i ( r 一惫一1 ) + i ( p k 一1 ) i ( p 住一) = f k 一2 r k + f k r k + 1 引理得证 口 3 1 双圈图独立集数的上界 下面我们将证明双囤图的独立集数上界，方法要较 6 】中的简洁 设g * ，t b h 1 ，n 一1 中的一个叶子与其他两个不同的叶子连边形成的n 阶双圈图， g ：如图5 所示 定理3 2 设g 为7 , 5 阶双圈图 ( a ) - ：k i n = 5 时，则i ( g ) 1 1 - ：l l 且6 z - ：k l g 口5 2 ，g 时取等号 ( b ) 当佗6 1 1 r j ，则i ( g ) 5 2 n 一4 + 1 当& 6 z - 3 g 型g ：时取等号 证明：通过简单的计算可得 i ( g ：) = 5 2 加4 + 1 1 0 th6n 5 幽i 勃 b 岛。6 图5 ：图簖，玩 1 b n ，2 ，风，3 ，b n ，4 ，玩，5 和玩，6 ( 口) 当扎= 5 w i - ，5 个点的双圈图集合为 g ；，b 5 l b s ，2 ，b s 4 风，6 ，通过直接计算得 到i ( g ) 1 1 当且仅当g 魄。2 ，嚷】- 时取等号 ( 6 ) 若g 型驴，结论显然成立，否则，我们分下面两种情况证明 情形一g 中的圈长至少为4 选择e e ( g ) 使得g e 仅含有一个圈且圈长长 至少为4 由引理2 9 得到 i ( g e ) i ( 巩，4 ) 显然要么g e 箬仉，4 ，要么g e 竺巩。4 若g e 喾，4 ，则有 i ( g ) i ( g e ) t ( 巩，4 ) = 5 2 沪4 + 2 ， 即有i ( g ) 5 2 “一4 + 1 若g e 竺巩，4 ，则g 玩 1 ) ，2 豌，3 ，玩，4 ) ；如图5 所示 通过直接计算我们得到 i ( 既。1 ) = 4 2 舻4 + 2 ，i ( b n ，2 ) = 9 2 ”5 + 2 i ( b n ，3 ) = 1 5 2 n 一6 + 2 ，i ( b n ，4 ) = 4 2 n 一4 + 2 所以有i ( g ) 5 2 铲4 + 1 情形二g 巾最长圈的圈长为3 ，则g 含有两个圈且圈长都为3 选取e e ( g ) 使得g e 为单圈图若g e 笺玩，3 ，则g 笺既，6 因此 i ( g ) = ( b 。，6 ) = 9 2 ”_ 5 + l 5 2 n 一4 + 1 若g e 筹矾m 由引理2 7 ( i i ) 和假设，可以得到i ( g e ) i ( g ) ，其中g 由粘一个 和他一4 个叶子到岛的两个不同点上若g e 箬g ，则有i ( g ) i ( v e ) i ( g ) = 5 2 n 一4 + 2 ，即有i ( g ) 2 r 1 情形二g 的圈上粘有悬挂树 设瓯。和瓯。为g 的两个圈，z 为g 中到伉。u 瓯：距离最远的点若d s t ( c k 。u g 。，z ) 2 则g 中包含z 的独立集的个数为i ( g n i x ) ，由假设可知g n i x 为 一个双幽子图和一些孤立点的并，即g n i x l = 日u 瓦：其中h 为佗一2 一s 阶 的双圈图由归纳假设知i ( g n i x ) 2 8 2 r 一3 一。2 r 一3 事实上，若s 1 ， 则有i ( g n i x ) 2 r 一3 不包含z 的独立集的个数为i ( g z ) 2 r 一2 即 有i ( g ) 2 r 一3 + 2 r 一2 = 2 r - 1 当s = 0 ，i ( g - n i x ) = 2 r 一3 ，i ( a - 茁) = 2 r 一2 时 等号成立，又g z 不是图g ：一1 ，所以由归纳假设知g z 竺g 基1 ，故g 笺g ： 若击s ( q 。ug 。，z ) = 1 ，设i v ( c 七。) i i y ( 瓯。) i ，下面分三中情况讨论 ( i ) 若g 的某个圈( 设瓯。) 上存在点秽，至少粘有2 个叶子，设为z ，且( 1 ) n 瓯。= 【u 2 ，仇 定义h ：= ( g 一 v l y ， 3 1 0 2 ) u z 可，y v 2 ，显然日也是个佗阶的双圈图 设为，( ) 到，( g ) 的映射，b 为何的一个独立集，( b ) 如表格1 所示每个点下的数 字表示该点是否在口内，1 表示在，o 表示不在显然咖为单射，但是 z ，秒，仇 ，( g ) ， 但是找不到b ，( ) 使得( b ) = z ，可，魄 故不是满射n i ( c ) j ( h ) ，这与我 们假设的i ( g ) 最小矛盾 ( i i ) 若g 的圈上所有的点至多粘有1 个叶子，不失一般性，设g 的某个圈上的连 续点 1 ，忱， 0 3 ，使得u l 没有粘叶子，而忱粘有叶子z 定义h ：= ( g 一 u ，忱) ) u z u 。】 同i 中一样定义：i ( h ) 一，( g ) ，见表格2 显然为单射，但是 z ，u l ，忱】，( g ) ，但是 找不到b ，( 日) 使得( b ) = 扛，仇，地】故不是满射则i ( g ) ，( 何) ，这与我们 假设的i ( g ) 最小矛盾 1 3 表l ：映射：1 ( n ) _ ，( g ) v l z 可 忱 ( b ) 0000b 000lb 0010b 0100b l000b 0101b 1001 ( b 一 t ，1 ) u 。，) l010 ( b 一 u 】) u z 表2 ：映射：，( 日) _ ，( g ) v l z v 2 ( b ) 0 00b 001b 010b 100b 101 ( b 一 忱) ) u z 】 ( i i i ) 若g 的圈上所有的点仅粘有1 个叶子，不失一般性，设g 的某个圈上的连续 点v l ，v 2 ，v 3 ，使得v l ，忱分别粘有叶子z ，y 定义h ：= ( g 一 u l t j 2 】) u z 可 同i 中一 样定义咖：r ( h ) 一，( g ) ，见表格3 显然为单射，但是 z ，y ，v 3 ，( g ) ，但是找不 到口，( 何) 使得( b ) = z ，y ，忱，故不是满射则i ( g ) ，( 日) ，这与我们假设 的i ( g ) 最小矛盾引理得证 口 引理3 4 设g 是有一条边连接圈瓯的一个点和树丁的一个点得到的扎阶单圈 图，其中l y ( t ) i = 佗一七则有i ( g ) i ( l n ，k ) - ：t a _ t ；1 i 叉当a 竺l n ，七时取等号 证明：设e = v w 连接q 的一个点v 署 i t 的一个点7 1 1 ，g 中包含点 的独立集的 个数为t ( g 一m ) = ( r 一3 ) i ( t 一叫) ，不包含的为i ( g v ) = t ( r 1 ) i ( t ) ， 于是i ( g ) = i ( p k 一3 ) i ( t w ) + i ( p k 一1 ) i ( 丁) ，而由引理2 1 ，i ( k ，k ) = i ( r 一3 ) - i ( p n k 一1 ) + t ( p k 一1 ) i ( r 一詹) ，由引理1 2 知i ( t w ) t ( r k 1 ) ，i ( 丁) i ( r 一七) ， 贝i j i ( a ) z ( k ，七) 当且仅当g 竺l 知时取等号 口 1 4 硕士学位论文 m a s t e r st h e s i s 表3 ：映射咖：r ( e ) 一，( g ) v l z 掣 v 2 ( 8 ) 0000b 0 001 。b 00 10b 0100b l000b 01 01b 1001 ( b v l ，t j 2 ，) u z ，可 lol0b 引理3 5 设g 为只含有两个圈的佗阶双圈图，则i ( g ) ( g ：) 当且仅当g 望 g ：时取等号图g 2 见下图 图7 ：图嚷 证明：我们分两种情况讨论设g 为的两个圈为瓯。，瓯。，且瓯。，c k 。卜没有粘树， 显然g 的每个圈都含有一个度为3 的点，设g ：的为2 ”， ，扎为埘在中的邻点g 中 包含乱的独立集的个数为i ( g 一m ) i ( l 。一3 ，七。) ，当g n u 】竺l - 3 ，k 。时取等号， 不包含的为i ( g ) i ( l 。一1 ，七。) ，当g u 竺l n 一1 ，七。，即七2 = 3 且连接瓯。，的路上没 粘树时取等号 i ( g ) i ( l n 一3 ，七1 + i ( l 凡一1 ，奄1 ) 兄1r 一一k 1 + 1 + r 1 2 r 一3 h + 兄lr 一1 一七l + l + 凡l 一2 r 一1 一k 1 最1r 一南1 2 + 忍1 2 r 一詹1 3 + 最，r 一南1 + r 1 2 r k l 一1 屁1 一l r 一屉1 2 + 风1 2 r 一七1 2 + 凡l 一2 r 一七1 3 + 凡l 一1 r 一七l + 最1 2 r k 1 + 最1 2 r 一凫1 1 r 一3 + r 1 2 r 一七l 一2 + r 一1 + 一2 r k 1 3 r 一3 + r 一4 + r 1 2 r h 一2 + r 1 2 r k 1 等号成立当且仅当= 3 且连接瓯。，( k 的路上没粘树时 同样的，我们可以类似得到 i ( g 曼) = i ( l 住_ 4 ，3 ) + i ( 岛) i ( l 一3 ，3 ) = 5 r 一3 因此 i ( g ) 一z ( g ：) = i ( g ) 一5 r 一3 3 r 一3 + r 一4 + 以1 2 r k 1 2 + f k l 2 j k 一忌1 5 f k 一3 = r 一4 + f k l 一2 r 一七l 一2 + f k l 2 r k 1 2 f 一3 = 最1 2 r k l 一2 + f k l 2 r k l r 3 一r 一5 = r l 一2 r k 1 2 + f k l 2 r 一七1 一r k 1 1 + 七1 2 一r 一5 = 风l 一2 r 一七1 2 + f k l 2 f 一k l r k 1 1 f k l 2 i f k k 1 2 凡1 3 一f k 一5 = 芦k 1 4 f k k l 一2 + f k l 2 f k k 1 2 一f 1 n k l 一2 + k 1 3 = r l 一4 r k l 一2 + f k l 一2 r k 1 2 一r k l 一2 凡l 一3 一f k k 1 3 j k l 4 = r l 一4 ( r k l 一4 + r k 1 2 ) 等号成立当且仅当= 3 且连接伉。，g 。的路上没粘树时，又巩，一4 0 ，f n 一七。一4 0 ，n 一七1 2 0 ，则有r 一一4 + r k 1 2 0 ，即凡1 4 ( r 一凫l 一4 + r k 1 - - 2 ) 0 故i ( g ) i ( c o ) 当且仪当后1 = k 2 = 3 n 连接瓯。，瓯。的路上没粘树时取等号，即g 竺 g o 下面只用考虑圈上粘树的情形，我们将用数学归纳法来证明，可直接验证 对n 5 ，6 ，7 ，8 】成立，我们假设礼9 ，且对较小的礼结论成立设g 是所有只 有两个圈的双圈图中独立集个数最少的图之一，且z 为粘在瓯戗。上的树中的 到q ，u 瓯。的距离最远的点 若d i s t ( c k ，u 瓯。，z ) 2 则g 中包含z 的独立集的个数为i ( g 一m ) ，由假设可 知g n i x 为一个双圈子图和一些孤立点，即g 一m = u u h 。，其中日为n - 2 一s 阶 的双圈图由归纳假设知i ( g n k l ) 2 85 e n 一5 一。5 f 一5 不包含z 的独立集的 个数为i ( g z ) 5 r 一4 即有i ( g ) 5 f 一3 若沈s ( g 。u 瓯。，z ) = 1 ，证明类似引 理3 2 中的情形二，故在此省略 1 6 口 引理3 6 i ( g ：) t ( g 2 ) ，i ( g ：) i ( 噼) 证明：由i ( g ：) = 2 p 一l ，i ( g 曼) = 5 p 一3 ，则有 i ( g ：) 一i ( 碟) = 2 r 一1 5 p 一3 = r 一6 0 显然当n = 5 时i ( g ：) = i ( g ：)