（应用数学专业论文）图的控制参数研究.pdf

摘要 本文一共五章。第一章介绍一些图论的基本概念和控制参数的预备知识。然 后，我们分别对笛卡尔乘积图的成对控制数，强全控制边临界图，以及树的上控 制数这三个问题进行研究。最后，我们总结本文的主要结果，并提出几个有待继 续研究的问题。 记饰( g ) 和助( g ) 分别为图g 的成对控制数和成对i x l c k i n g 数记g o l f 为图g 和图h 的笛卡尔乘积。称图g 为( 办，饰) 一图，如果砌( g ) = 饰( g ) 。在第二章，我 们证明了，对于任意的不含孤立点的图g 和图日，其中至少一个是不舍三角形 的协，馋) - 图，有饰( g ) 饰( 日) 2 饰( g 口日) 。进一步在一般情况下，我们证明了，对 于任意的不含孤立点的图g 和图日，有铀( g ) 饴( j ! r ) 7 饰( g 口h ) 。 不含孤立点的图g ，如果它的任意两个不相邻顶点u ，口，有7 t ( g + t v ) 乍( g ) ， 则图g 是全控制边临界的，简称竹临界。 y t 临界图g ，如果对任意顶点u y ( g ) 存 在g 的一个基数为饥( g ) 一1 的控制集d ，使得u d 且g d 1 除 外不含孤立点，则 图g 是强临界的。在第三章，我们研究了竹l 临界图和强7 t - l 临界图的性质，并给 出了一个构造强竹临界图的方法 记7 ( g ) 和r c c ) 分别为图g 的控制数和上控制数。在第四章，我们给出了一个 确定树? 上控制集的算法，并利用该算法分别刻划了满足条件7 + r ( = n 和 7 ( t ) = r 口) 的树。 a b s t r a c t i nt h i st h e s i sw ed i s c u s st h r e ep r o b l e m sa b o u td o m i n a t i o np a r a m e t e r so f g r a p h s i tc o n s i s t so ff i v ec h a p t e r s i nt h ef i r s tc h a p t e r ，w ei n t r o d u c es o m ef o v n - d a t i o n a lp r o p e r t i e so fg r a p h sa n dd o m i n a t i o np a r a m e t e r su s e di no u rd i s e t m s i o n s t h e nw ed i s c u s sp a i r e dd o m i n a t i o no fc a r t e s i a np r o d u c t s ，s t r o n g l y7 t - c r i t i c a l ，u p - p e rd o m i n a t i o no ft r e e s ，r e s p e c t i v e l y i nt h el a s tc h a p t e r ，w es u m m a r i z et h em a i n r e s u l t si nt h i st h e s i s ，a n dg i v e8 0 m ep r o b l e m st ob es t u d i e df u r t h e r l e t ( g ) ，一( g ) d e n o t et h ep a i r e dd o m i n a t i o nn u m b e ra n dt h ep a i r e dp a c k i n g n u m b e ro fag r a p hg r e s p e c t i v e l y l e tg 口hd e n o t et h ec a r t e s i a np r o d u c to f g r a p h sga n d 日ag r a p hg i sc a l l e da ( 伟，) 一g r a p hi f 乃( g ) = 饰( g ) i nt h e s e c o n dc h a p t e r ，w es h o wt h a tf o ra n yg r a p h sga n dhw i t h o u ti s o l a t e dv e r t e x ，a t l e a s to n eo fw h i c hi sat r i a n g l ef r e e ( 昂，饰) - g r a p h ，t h a t 佛( g ) ( 日) 2 饰( g 口日) f u r t h e r m o r e ，w ep r o v et h a t ( g ) 饰( 日) 7 ( g 口日) f o ra n yg r a p h sga n d 日 w i t h o u ti s o l a t e dv e r t e x a g r a p hg w i t h o u ti s o l a t e dv e r t e xi 8t o t a ld o m i n a t i o ne d g ec r i t i c a li ff o ra n y n o n - a d j a c e n tp a i ro fv e r t i c e st a n d 口，m ( g + 伽) 孛连接褒点2 耪蘸长度( 1 e n g t h ) 凳奄瓣链( 幽妇残秘w ，谗 为$ ”键，是指顶点魏和边吩交错出现的序列 w = ( = # ) 啾l 矗l 啦2 。魄霸。( _ ， 其中与边都相邻酌两顶点一：和正好是嘞的两个端点( 筲挠有窖如一，= 翰) z 和称为w 的端， i ( e n d - v e r t i c e s ) ，其余顶点称为内部点( 锄删l 氆lv e r t i c e s ) 。w 中 边的数爨称为w 的长度。边互不稳阏斡链称为缱( t r a u ) 。内部廉置不相同的遮称 兔臻( p a t h ) 。两翡赢耱丽豹链( 迹，鼹) 称为溺( c l o s e d ) 链( 透、路) 。麓有囱洚又裙 为( 有向) 圈( q c l e ) 设g = ( 矿( g ) ，嚣( 秭，妒。和h 一( v ( 露) ，e ( h x 硝留) 是两个图，嚣矿( 日) 矿( 谚， 霉羹联谚，势显妒榉是钯在承嚣) 上熬限翻，繇妇= 蟾| 斟m ，舞 l 称嚣为g 豹 子困( 8 u h 鲫巾h ) ，记为盯g 。设是矿( g ) 的非空真子集，以为顶点集井 以g 中阿端点均在巾的边为边集合的子图称为g 的由导出的子图，简称导建 子霉瓣t 葩s u b g r a p h ) ，记为。戮。零塞子塑矿、明记舞g 一妒。羞驴= 磅， 则简记g 一伽) 为g 一霉。 设口v ，若a 中存在连接g 和的路，则称g 和p 是连遗的( c n 础e d ) 容易验诞，矿孛元素乏瓣懿连逶关系楚矿上翦等徐荧系。这势等徐关系将矿努戏 等价类h ，k ，磁。z 和g 属于嗣一类k 筒和是连通的。子圈a i r , 】( 1 i ) 称为g 的连通分支( c o n n e c t e dc o m p o n e n t ) ，称为g 的连邋分支数( n u m b e r o f c o m p o n e n t s ) ，记戈；* ( g ) 。若# ( 圆= 1 ，剿拣0 菇绷( c o n n e c t e d f 雄h ) ； 反之为j # 连通图f d i 8 c 删e dg r a p h ) 。 4 中国科学技术大学硕士学僻论文 设鼹g = 襁胡t 顶点口v 熬开部点粟( o p e nn e i g h b o r h o o d ) 记秀粕g 釉* “viw 研，即顶点口的所肖邻点组成的集合。顶点 的闭邻点集( c l o s e d n e i g h b o r h o o d ) 记为m 一g ( 嘭u 如l 。对于y 的子集ssv ，寓的开邻点集记 兔n o ( s ) = u , ，e s n a ，闭邻轰集鬣为糯淄= i r a ( s ) u s 。 设图g = 聊，m 是e ( g ) 的q b 空子集若盯中任意两条边在g 中均不相 邻，则称材为g 的熙薅己( m a t c h i n g ) 。g 中的顶点如果与m 中边关联，称为m 饱朔 纛( s a t u r a t e d 瓣。爱之，称为嚣掰键_ 帮熹。设x 矿 谚，器x 孛每个磺震 都是m 饱和点，则称肘饱和x 。着m 饱和y ，则称m 为图g 的究备匹配( p e r f e e t m a t c h i n g ) 。若对图g 的任何匹配 均有i m ，| i m i 成立，则称m 为g 的最太阪 配( m a 3 d i n m l 囟崤，。显然，每个完鍪嚣配鄂愚最大嚣琵t 爱之不囊。鼹鞭 配材巾的任意一条边，称这条边上的两个端点互为成对点。 设犯”y ( g ) ，图g 中从z 到”最短路( s h o r t e s tp a t h ) 的长度称为z 和的距 ( d 觚n c e ) ，记隽瓤，妨。g 懿轰绦掇8 m e 獗) 键隽g ) = 电扛，) l v z , ys y ( g ) 。如果毛f 满怒酝扛渤= d ( 回，称z ，薯，为直瓴蕞。对y ( g ) 的两个子集置y ， 定义它们之间的距离为 d a ( x ，y ) 一m i n d o ( 。，口) i 慨五y 。 墩鬻g = ( h 秘，熟莱顶点集矿胃默翅劈为薅令菲空子集x 搬y ，使德x 串 任何两顶点之闯无边橱连并且y 中谨何两顶点之阈也无边相连，则称该圈为露鄙 分 鸳( b i p a r t i t eg r a p h ) ， x ，n 称为2 鄙划分( b i p a r t i t i o n ) 。简单2 部分无向图似u y , e ) 豁为完全君部分躅( c o m p l e t eb i p a r t i t eg r a p h ) ，如果x 中的每个顶点与y 中的 每个瑗淼筠有边穗遣， l 。3 控靠参数余缓 定义1 3 1 设图g 一( k 曰，s 是y 的子集，如果 b 翻= v ，则s 是图g 的控制 集( d o m i n a t i n gs 哟。如果s 是圈g 瓣瑗点数最少盼羧割集，剐称嘲为匿g 驰敦制 数，记为7 ( 翻。也称s 为图g 的最小控袭| 集。 1 3 控制参数介绍 5 图1 2s p i d e r 图的控制集 在褥串，一度点被称作是盱点，嚣它的邻点称作是支撵焦。翔果某个支撑点 与两个域两个玟上瓣卧患相邻，粼被称作是强支撵点。考虑鼙l o 中的s p i d e r 鬻。 我们抱圈f 中的5 个黑色顶点组成的集合记为s ，淀意f 中剩下的顶点都和s 巾 的某个顶点相连。因此，乍( 聊5 。又因为每个时点和它的支撑点至少有一个爆 予s ，嚣露骞( 两5 。掰淤，我髓褥餮霹= 5 。 考虑图1 3 。集合疗= 啦c ) 构成图h 的控制集，又因为不存在一个与其他顶 点都棚连盼餍点，所以，( 哪= 2 。褥看图1 4 中瓣瓣? 。因为5 个黑色顶点控制 耱? ，势基耱t 豹控簇数登是丈予黪予它懿支箨藤盼令数，掰戳骞? 器，= 5 。 d 嚣1 3 强嚣熬控翻巢 6 c 图1 4 树? 叠每控制熊 6 中国科学技术大学硕士学位论文 死一 嚣二台! 图1 , 6 阕厅的全控制榘 图1 7 树t 的全控制熬 每个全控制集掰孵氇是控制集，艨鞋对不含孤也纛静鍪g ，毒7 ( 回馈( 球。 我们褥瓣图1 2 中的跆i d e r 圈。黑色顼点梅成f 鹃羧潮集s ，毽懋这5 个顶点郝熏 1 3 控制参数介绍 7 少蒜簧有一个s 中弱邻赢。壹照得翻f 的全控簌煞s ，翔图1 5 掰汞。由圈中豹 黑色顶点构成，注意f 中的每个顶点都与中的浆个顶点相连，得到m ( f ) 6 因为，强少需要5 个】煲点来控制叶点，且所有的支撑点之间互不棚逑，所以f 的众 控籁囊爱少还嚣要1 今臻点，帮镄秘6 。嚣魏，我髓褥刭蕊( 秘一6 。 谯图1 3 中，集合8 = “c 构成图日的控制集且1 ( 日) = 2 。但是，这两个顶 点互不相连，使得s 不是目的全控制集。嚣的全控制集酽= 协砖如图1 6 所豕 注意，嚣瓣控裁数等予全整懿数。簸嚣考虑强1 4 串黪耩t ，t 串掰骞支撵纛稳蔽 一个控制集。但是，幽予这些支撑点曩不相连，所以它并不是t 的垒控制集r 的 全控制熊如图1 7 所承，由8 个黑色顶点构成，且( 卵= 8 瓣予全控鬟囊葶，凌爨霹滏一疹簧求s 串戆竣杰嚣秀成鼹，蠹蘧褥嚣藏辩控 制集。下面给出成对控制集和成对控割数的定义。 定义l 。3 3 ，设图g 。e ) 不含孤立点，s 是y 的子集，如果( 研* v ，且c i s 麓 多惫禽一个完备匹嚣，掰s 是嚣g 戆残霹整裁条p 穗蟠d o m l n s t 妇g 鼯磅。懿暴8 惩 图g 的顶点数最少的成对控割集，则称i s l 为圈g 的成对控制数，记为饰( g ) 设s , t 是y ( g ) 的子集，如果tg 盹$ ，称s 全控制r 。炎似地，我们阿 毅定义s 控锈f ，翔荣r 怒r 瀚。慰不含孤立点戆壅g ，我稍窍 回麓固 饰( g ) 2 7 ( g ) 。如荣读者希望迸一步了解以上三种控制参数，可分别参见【3 ，8 ，1 捌 对予l 吝_ - - 种控制参数在互连网络中盼应用，我们绘个简单的例子。设不食孤 立点翡翔8 = 澎蜀瓣疲令互连瓣络。秀这个瓣缀囊装警至系统，子集scv 巾 的每个顶点”对应一个警卫的位置，它的作用是保护眦m 中的每个顶点。那么敬 制集s ( d o m i a a t h 堰毗) ，是要求y 疗中每个顶点都得到保护，即n a ( s ) 2v 掌 全控稍纂s ( t o t ad o m t u a t i 珏g 峨 ，送一疹要求每令聱至氇藐舞餮穗镲聱墨静搽护， 即拖挪；v 。成对控制集s ( p a i r e dd o m i n a t i n gs e t ) ，是在全控制的基础上，要求 所有警m 每两个相邻的一组，互相提供保护。满足如上要求的予熬s 分别被称为 控制集、金控寿集秘成对整射集。我们希望投入聱墨靛数量最少，于是就有了掇 割数、龛控筋数帮戚对控镪| 数的穰念。 第二章笛卡尔乘积图的成对控制数 v i z i n g 猜想是图的控制理论中未解决的最著名的猜想之一。已经证明该猜想 对一些特殊图类和特殊情形成立。围绕这个猜想，人们主要从两方面进行研究，一 方面是研究类似v i z i n g 猜想的不等式关于其他控制数是否成立。另一方面，研究 其他类型乘积图控制数的类v i z 堍猜想不等式，希望找到解决v i z i n g 猜想的途径 本章，我们研究笛卡尔乘积图的成对控制数，和成对控制数的类v b i n g 不等式。 2 1v l z i n g 猜想 笛卡尔乘积是图的个重要构图方法，其定义如下： 定义2 1 1 设图g 和j ! r 是两个顶点不交的简单图。g 和日的笛卡尔乘积( c a r t 曲m p r o d u c 0 g 口日是一个简单图，其中v ( g 口哪= y ( g ) y ( 田，并且对。l ，g l y ( g ) ，托，抛v ( h ) ，( ( 1 ，现) ，( 讥，妇) ) e 归口印 啼或者$ 1 = lj | - ( x 2 ，抛) e ( h ) ，或者规= 抛且( l ，”1 ) e ( g ) 广r 。 图2 1 笛卡尔乘积图j 岛岛 猜想2 1 2 f y i 细劬对于任意图g 和日， 7 ( q 7 ( 哪，y ( g 口日) 虽然这个猜想尚未解决，但对特殊图类证明v h z i n g 猜想或算出乘积图控制数 确切值( 如【7 ，1 7 ，1 8 ，1 9 】) ，或是确定其他类型乘积图的控制数的界( 如1 2 0 , 2 1 】) ， 8 2 1v i z i n g 猜想 9 或建姘究乘积图缒冀镳控裁数( 翔陵2 2 1 ) 的类v 洳g 猜想不等式，文献非常率 富。 群簸，对般戮关于这个猜想的最佳上界楚蠡c l a r k ，s u e n 翻给出缒： 定理2 1 3 ( o n r k , 瓤阱f 劲婶于任意图g 和日，叮( g ) 7 ( 露) 铆够口田 相关的结果有： 定理2 。1 4 ( s u n 脚珈砖于任意圈群和嚣，如幕( 街；3 ，( 国7 ( 嚣) 7 ( g 口鳓 h e n i u g ，r a l l 【9 】研究了笛卡尔莱积图的全控嚣数，提出猪憨；两个不舍孤立 纛戆辫瓣金莲潮数象漱不超过这嚣令鹜警专象豢获戆全羟裁数熬2 穆。在该交审俸 者已经证明该猜想对一些特殊图类( 如树) 成立 瀚一般图证明了： 定理2 。l ，5 ( h e a n l n g , 晁盘跬黝对予镣意不会嘻氐盏患酌图g 争拦，有 m ( g ) 饿( 灯) 6 仉( g 口聊 h o u 改避上嚣鹣络桑为 定理2 1 6 ( h o u p 聊神于任意苍合孤立点的图g 和日，仉( 回饥( 聊5 弛( g 口哪 定理2 。l 。五鼬口搿够砖于轻意零食孤立点镑翳g 争嚣，骞 r ( g ) r ( 堋十1 f ( g 翻盯) 羧撂7 ( 谚( 勰谚窝是灌2 1 3 ，我弱霹滋立饔褥蘩； 推论2 1 8 对于任意幂龠弧盘点的蹰g 和日，饰( 研强( 日) 8 知 口日) 我假牟鼙在第三、嚣节申讨论甏篾成髓控铡数瓣类v 赫矗g 猜憋不等式鞫戆。麓 先分缨下p k l 埘絮静概念，它将在以后的证髓过程中雳到。 中国科学技术大学硕士学位论文 2 2p a c k i n g 集的概念 定义2 2 1 设图g = 切，s 是y 的子集，如果s 中任意两个顶点之问的距离 至少是3 ，则s 是图g 的p a c k i n g 集。如果s 是图g 的顶点数最多的p a 庙讥9 集，则 称俐为p o 吐i 邶数，记为p ( g ) 。 对于任意的图g ，有p ( g ) 1 ( g ) 。如果p ( g ) = 1 ( g ) ，则称图g 为( p ，7 ) ，图。 定理2 2 2 ( m e i r , m o o nl l a ) 所有树都是( p ，y ) 图 如图2 2 所示，树? 中5 个黑色顶点构成t 的顶点数最多的粥曲i 哪集，即最 大p a c k i n g 集，并且有p ( t ) = 1 ( = 5 图2 2 树t 的p a c k i n g 集 定义2 23 设图g = 司不含孤立点，s 是矿的子集，如果s 的导出子图g 吲包 含一个完备匹配m ，且m 中任意两边之间的距离至少是3 ，( 即对任意边z l y l ，z 2 抛 m ，有如( 1 ，玑 ， 现，! 2 ) 3 ) ，则s 是图g 的成对胆砖t w 集。如果s 是图g 的 顶点数最多的成对曲咖集，则称例为成对粥c 讯9 数，记为脚( g ) 。如果一( g ) = 却( g ) ，则称图g 为( 脚，) - 图。 显然，如果s 是图g 的成对卵c 航w 集，那么l s l 是偶数，且g 吲= u 叁1 j 岛， 其中自= 粤。如果图g 中任意三个顶点的导出子图都不是三角形，则称图g 是不 含三角形的。不难验证，对任意不含三角形且不含孤立点的图，一定存在它的成 对m c b 打增集。以下将证明，饰) 图是存在的 2 3 特殊情形 1 1 i l 蓬2 2 。4 对于任意不舍三角影美翠龠孤立点斡蹋g ，有氟回静犯) 证明设a ； z l ，t ，k ，搬) 是图g 的最大成对舯出唧集，其中对任意正整数“ 顶点辫秘辍在g 孛藤连，困瑟鳓一姥。因为颤( ，热 ， 彩，辫羚3 ，i ，子 集族抛f ，弘 】，i = 1 ，两两交集为空。设祭台d 是图g 的最小成对控制 集，觑= d n n a i x t ，弘。因为图g 不含三角形，所以对于任麓成对点，tm 1 ，一定存在瓿中熬顶点t ，口分别控铡承，虢。阏j 琏：，l d | l 2 ，进两褥到l 磁 疑，掰戳鳓( 固铀。证毕。0 引理2 2 5 如果不合墨角形的图g 楚( p 7 ) 。图，则g 口硒是如，饰) - 图 莲翡浚谚= g ) 一，憨= l ，2 ，銎g 豹覆文p a c k i r ；9 集秘最夺控裁集势掰 是 $ 1 ，。， 轨，挑) 。显然，蹋g 口鲍的成对p a c k i n g 集和成对控制集分别 是 ，1 ) ，恤，2 ) ，1 ) ，( z k ，2 ) ， ( 讥，1 ) 觚，2 ) ，饥，1 ) ，觚，2 ) ，因j 比脚( 研 毖蚀簿) 。辗据葶l 瑗2 2 4 ，寿玲( = 铷( g ) ，掰叛g 蜀j 岛，憝轴雉) 一篷。 露 使用编码理论中的海明码( 勘蝴c o d m ) 我们可以计算部分超立方体的掇 制数，如果希望进一步了解海明码，可参见【1 3 】。 l 建2 2 6 + 阮臻瞬掰承黟砖争逡释砖起立方搭瓴，英孛d 一寥一1 ，女蔻藏 整数，钒有最小控制熊，阶数为貉 p e l e g ，切l m 8 n 在【1 3 l 孛绘出口d ( d - - - - 驴一l 鲍一个最小控靠集，这个最小控 寨 阂对逛怒现豹弦醢办w 集，帮p ( 7 ( 瓴) 。由予孵任意鹫g ，p ) 乍0 回，掰 p ( q d ) 一一r ( q d ) ，钆照( n r ) 图。由引理2 2 5 得到，乳l = 仇0 拖是( 脚，仲) - 图。 2 3 特臻德形 先介绍证明中将骚用到的几个记号。笛卡尔黎积g 凸口中的任意顶点0 ， 在匿嚣审与顶点# 对艨，髂戈溆) 懿嚣映餐，记必一妇瓴妨矿姆。层) 黪锤 j 蕞子集a = 扛l 舟) ，池，魂) ，集含a 的丑i 爽射记为颧 ) 一啦；l 妇涵，碱) - 中国科学技术大学硕士攀位论文 设图g 不含孤立点，s 和? 是y 固的子集，如慕阮潮2t ，剿称s 在强g 上控 制t ，或者s 是r 在图g 上的控制集。如果 b 嘲0t ，且g f 别包含一个完备躁 配，爱称s 是r 在瞬g 上的成对控锖撬。 定理2 3 1 对于任意笨合孤立点的圈g 和蠢，如暴其中至少一个逶不舍三角彤的 ( 昂，饴) * 阉，那么有 饰( 固铷( 鹂擘静g 国国， 且谊举等式的界是紧的 证明不妨设图。是不含三角形的( 踟，) 图。设瑚( g ) = 卸( g ) 一虢r 并且集合a * 缸l ，戳，奶，y 2 ，。，秘，搬 是盈g 熬袋犬戍对弘出错集，其孛对每个歪整数 ，谈煮蕊 和船程阕g 中相连。阻此子集族域z q ，挑) 】o ；1 ，两两不交。设集 合d 魁g o h 的最小成对控砖4 集，d 婀导出子图( c o h ) l d 】包含一个完备匹配m 远致一d n 瀑x y 搿强 = l 2 一，菇，露= 蕊 v ( h ，豫一蕊 y 搿) ， 显然觑在g 口置中控制集合最k 和编。的所有顶点。设 熙。；缸1 8 鼽，p ( 4 ) 彗取，妒口( 貔) 蜘( 承) 魄；侈l 芦瓿，鼬) 簪马，如始( 鼽硌 其巾芦( 是顶点n 的m 成对点。设是所霄足。中顶点的材成对点组成的 集合，烫酝遮霉茨褥戮最郅，甏= ( 癣l e ，蒜一 | 筘毒赫 显然l 联。i = i 疋小j 磁j = i j i 不失一般性，假设f 屁i i i 因为图g 不禽 三角形，所以足。n 婚。；a 。又因为无法控制瓢h 中的任何个顶点，得到熬 合反菇。是骂。在g 曩露土懿控割榘。注意集会魏串懿程意璜焱8 ，翔果反妨聋 d ，翼| j 顶点口或者在玩。中，或者在翰中，医眈集合( 觑) u 毪怒凰。在珂上 的一个成对控制集，并且j ( 皿) u 吃l l d t i 。 瑷镁设最是l 酝燕g 曩嚣上懿簸小残露控联繁，量趣含枣霹糍多懿甄；孛瓣 顶点。貔们将证晚最篓蜀。否刚，集合岛中存在顼点a = ( $ ，“) 簪z k 。 2 。3 特殊情形 情形一如栗p 和) 岛。，那么梦缸) = 蕊，。于是顶点口只和甄串静疆 点p ( n ) 相邻。如果顶点p ( a ) 在凰巾的所有邻点都属于鼠，那么煞合最仞( a ) ，a ) 是k 谯g 口日上的成对控制集，与集合岛的最小性矛盾；否则，将s i 中的顶 点寇蛰挨残如；在l 酝上苓覆手最豹部熹，于燕褥爨了题；的舅一令最零残辩控 制集，但是包含更多的也。中的顶点，矛盾。 悖形二如果p ( 彗z k ，那么p q ) = “) 或者瓴曲如聚p ( = ， 爨镶纛a 窝p 酶灵藏髑岛。孛兹 簧患纽，磅。嚣秀集合韪是昱毫凌g 蜀嚣主懿爨夺 成对撩制集，顶点溆，和它的邻点都不在岛中。因此将鼠中顶点a 和p ( n ) 替换 成 ，“) 和它在日毛上任意一个邻点，得到另一个最小成对控制察，且包含更多 鹣磁。孛豹褒点，矛媾。絮暴谚一扛，t 0 ，裂磋点8 窝固分嬲穗剩露毫串瓣谈 点慨，t ) 和慨，) ，并且由于集合蕊的最小性，遨两个顶点都誉在最中。因此将 集合鼠中顶点a 和p ( n ) 替换成协，“) 和慨，t ，) ，得到另一个最小成对控制集，鼠 包含鼹多的黾中黪瑗点，矛詹。 综上所述，我稍诋臻7 最魄。，并且集合躐是蜀的成澍控制集。因为玩。 与日同构，i 最i 蚀( 哪。又因为集含( 取f k ) u 蟛。是峨。在g d h j = 的成对控制 集，鸯l ( 甄f 瓣) u 磁| | & l 。最终我们得到： 饰伶口聊一i d i i d o l l 慨) u 磁i 吲 妻强硼；i 1 铷( q 仰( 嚣) ( 2 ，3 强硼；毒铷( q 仰( 嚣) ( 2 ，1 ) 士= l 一 下丽给出该不等式等号成立的情形。设图有顶点集矿( ) 一伽i ，粕 。 由图构造图g ：对y ( g ，) 中的每个顶点增加一个一度邻点，在嚣( g ，) 中的每条边 土壤纛巍令瑗赢，势戏三条透。热嚣2 3 耩示。( 注意，热果嚣慧窆霆】东，爨g n 配) 嫁样集合h ) 是图g 的最火p o 曲d n g 集和溅小控制集，p ( 研= 7 ( g ) = ，；， 且饰( 铆；2 n 。设甘* 飓； 1 ，2 ，易证 ( z l ，1 ) ，0 l ，2 ) ，( ，1 ) ，( ，2 ) ) 是管卡 尔乘积g c i i 豹威辩羧联爨，秘孰。蘼以蚀( 固静( 嚣一瓴( 嚣， 再撮攒不等式2 3 1 ，肖( g ) 蚀( 嚣) * 2 7 p ( g o h ) 1 4 中国科学技术大学硕士学位论文 图2 3 图g 的构j 鬣 2 曩一般馕形 考虑与顶点p ，) v ( c o 聊茂联的边。我们把连接顶点 ，”) 和国，“) 妇e 肮7 0 ) ) 的边，称之为g 3 1 1 的g 边。炎f 以地，连接顶点0 ，u ) 和0 ， ) 扣蜥( ) 的 迭，嚣乏失g 3 嚣懿嚣逸。 定理2 4 1 对于任意不舍孤立点的阑口和日， 却( g ) 铷( 霸够d h ) 证明设集合d 是g a 日的最小成对控制集，d 襁g 口日上的导出子图包含一个 完备聪嬲材。设m * 婚u 脚，箕巾拖是m 巾所有g 边的集会，蛳是时中 囊有嚣逑戆集舍。象鼍：爨。窝器燕黠稳鹃，不魏浚| 鳓l l 臻l 。记集会d a v ( m o ) ，d s = 矿( 肘知) ，贝i j 有d = d a u d s ，i d 盘l l d h f 。所以l 曩。1 1 d i 。 设集合a = 砚，搬，瓢，溉 是圈g 的最小成对控制集，其中对每个正整数， 矮焘承箨馥在g 主耱邻，显强( 回一蕊。竣琏，瑰，珏蠹燕辩凌轰集矿瓣 一个划分，使得对1 女，有 粕，驰 甄( 协，玑) ) 对 = 1 ，2 ，血， 设岛md n 慨x v c h ) ) ，d g i = m nd t 。设地= 蜘n e ( c 口吲皿1 ) ，其 中e ( gah 隆黔是墩在彗卡尔乘积g 3 嚣孛妨等窭予霉豹边裳。注意，瑰* 矿( 船执) * d d u , 2 4 一般情形 炭食 和 靛称作笛卡尔乘积g 3 h 中一个肇元，如栗f 鞲x 谚) n ( d ) * 妒，则称琢 ) 来被觑垂直控制，否则凰扣 被肪垂直控制对l = 1 ， 设集念晟= 扣l 眠 螂) ) n n ( d _ ) m 毋， y ( 琊 ，= 1 只 。对簿个集合d ，我 靛祷逡密鞠痘戆蚕嚣鹩藏对控爨集。 设删= 细( d i ) ，则d ：是v ( h ) 的子集，且是露一只的控制熊，( 日一或是集 合y ( 盯) 晟在拄上的蟹出子图) 设魄= 妇( 砜) ，有d 设 是好f l 熬最大莲配，尹丑。* 缸，萄| 扛，司瓴，“簪联蚴 t 鑫淹醒筵最大嚣鬣，翔 果n 魄，那么它的m 成对点p ( 聋甩，且存在顶点卢p 峨使得如) 。 妇( p ( n ) ) 。所以i d ；i 慨卜l 魄i 眭意拍矗是舰在g e h 上爵出子图的完备甄 鬈，| 瓿 l 纽l ，敷黻2 1 p , l | 黟壤l 。 ， 设 是日魁l 的最大匹配，韪满足蟛删。显然1 q y ( 蝉) l 1 d 圆l 十 1 因为集合d ：怒h 一晟的控制榘，集合v ( h ) ( 日吵( 埘) l u 蜀) 在图盯中 被毯矿辫) 控铡，掰孩集会v ( h 、舷罗蟛) ；瓷圈嚣孛旋( 职矿g 癸u 最装 翩。墩韪一( d ：矿( 帮) ) u 蜀，对每个顶点“& ，鼬果嘞耋矿( 掣) ，那么扶熊 合最中去掉顶点u ，所得到的集合记为鼋。如果碍簪，那么设熊合q 是二部分 图嚣一y ( a 掣) 的最大旺艇，其中v ( n 一联 掣) ) 一u 硒弘r 磁，) ( 鼢记集合璇楚 掰有酝串饱帮点缀藏的集合。注意姣2 1 韪i 。 现在，我们来证明集合矾是矿( 哪h i v ( 州7 ) 】在图日中的成对控制集。注意 集合最鞠都是y ( 聊舫y ( 埘) l 农图耳中的控制熊。如果鹾，口譬醍，趣 子集会酝是最大莲甏，有l 强一巩榉) 秘0 琢鄯熊台酝是矿琊始i y a ) l 在 图h 巾的控制集，且轨包含完美匹黻q ，所以玩燎v ( h ) 舰r i v ( 州7 ) 】的成对投 制集。阂此集合y ( 掣) u 魄是图日的成对控制集，并且 矿( 拟) u 识i y ( 蜚) + 2 | 镬y ( 碧) | + 2 一i 叫j + l q y ( ) f + 2 k | 穰| 一l 昂氟l + l d o , | + l p h , l + 2 = 强l + i d 囟 + 2 k + 1 6 中国科学技术大学硕士学位论文 囊淤， 七 七i ；却( g h ( 辩) i v c m ； ) u u d i z ) d + i d d , l + 2 扫；li=i=l t = l 蠹 = | d | 十i 玩| 2 毳 七 ；i d l + 2 h ( 2 4 1 ) 谈集合= y 鳓 。魏巢藕无琢 ”，束被d 垂直控制，由于集合d 怒 g 口的成对控制集，肖砜 t ，) n ( d o v w ) 。因此，未被垂直接制单元中的每个 顶点被d n 控制。攀元琢姗巾的每个顶点( 特别地，对予被垂直控制单元) 被 ，转x ) 全撩灏。集合毪串米被垂直整麟攀元豹个数记为m 。这m ”令 单元中的每个顶点被熊台仇，全控制。考虑下面由h e n n i n g ，r a l l 得出的结论： 引理2 磊。2 。( t l e n n i n g , r o g l 鳓却瓣2 搪一) + 2 | 幽上面的结论，我们得到”锄l d t 小所以 膏 k = l l = i d t 幸= 。l 埘y 辩蜒y ( 丑3 因此由等式2 4 1 ，得剜 饰( g ) 卸( 研7 | d l = 7 嘞( 秽0 日) 髓 第三章强全控制边临界图 研究图论参数的临界性是图论中一个基本问题。临界性是指任意添加( 或删 去) 图上的一个顶点( 或者一条边) 均导致某个图论参数( 例如连通性，色数) 增 加( 或者减少) 本章，我们研究图的全控制边临界性，即任意添加图的一条边，均 导致该图的全控制数增加。进一步我们提出强全控制边l 临界的概念，并且给出一 个构造强临界图的方法 3 1 全控制边临界 定义3 11 设图g = e ) 不含孤立点，如果对任意不相邻的两个顶点”，都有 m ( g + w ) 6 ， 圈c i 不是饥i 临界图。 引理3 1 6 ( i g e n n i n a e 7 1 ) 设n 3 ，饥( r ) = 吼( g ) = 【副+ f 2 1 一【利 定理3 1 7 设n 6 ，固岛不是m 一临界图 证明假设对n 6 ，圈g 是m 一临界图，其中y ( g ) = ( ， 0 1 ，一1 ) ，昱( ) = i b i k + lj 七= 0 1 n 一2 u 珊札1 。对于边e = t j 0 饰簪e ( 瓯) ，记图瓯+ e 为诺 设fzc ：f t 1 0 ，t 1 ，坞h ，日= c ：【 珊，一1 ，如 】，则图f 和日分别是顶 2 0 中国科学技术大学硕士学位论文 点数为6 和n 一4 的圈。设集合s 是图锈的最小全控制集。根据命题3 i 4 ，顶 点v o 和奶中至少有一个在s 中。设s f = y ( n n s ，妇= v ( h ) ns 如果顶 点v o 和坞都在s 中，则集合跏和鼬分别是图f 和日的全控制集。因此，l 跏l 仉( d ，l 鼬i m ( 印。所以佻( ) + 2 m ( 刃+ 讯( 日) 如果顶点如和也中恰好有一 个在s 中，不妨设v o s ，则v o 被集合跏或鼬全控制，不妨设是跏，则有昂全 控制f ，路= 勖u 珊) 全控制h 。因此 曲l + i 路i = l 跏j + i h h i + l = 例+ 2 。所 以，m ( c ：) + 2 钆( d + m ( 哪。 再设集合昂和鼬分别是图f 和目的最小全控制集，且 t 1 0 ，) s 跏， ，镪 s 矗( 因为圈是点可迁的，所以存在这样的s 和釉) 。则跏u 勋是嚷的全控 制集，且顶点数是钆( 聊+ m ( 日) 一2 。因而，m ( f ) + 恤( 日) 一2 m ( 碟) ，所以 有饥( 日+ m ( 鄙一2 = t ( 铹) a 根据引理3 i 6 ，仳( 岛) 一【利+ 劓一【利所 以m ( c ：) = 仉( c h ) + m ( c ；一4 ) 一2 = 4 + 【2 尹j + f 旦1 一【孚j 一2 = 催( 1 ) ，推出矛 盾。因此，对于n 6 ，圈g 不是竹i 临界图。 口 注意，完全图忙2 ) 是平凡的强砷p 临界图，下面我们介绍三个强临界图 区别于一般临界图的性质。 命题3 1 8 图佚强m - i 临界图，当且仅当它的每个连通分支都是强7 t 临界图 m 一临界图的每个连通分支都是忙临界图，反之则不然。例如，图3 i 中的 图( 6 ) ( 记为g b ) 是m 临界图，但图岛u 岛则不是。 根据命题3 1 8 ，研究强m 临界图，我们只需考虑连通图。 命题3 1 9 连通图g 是强m 1 临界图，且顶点数大于2 ，则图g 不合度点 证明设连通图g 是强饥一临界图，且顶点数大于2 。假设图g 含有一度点u ，设顶 点口是它的支撑点。因为i y ( g ) i 3 ，顶点”存在另一个图g 中的邻点 考虑 图g 的全控制集d 子，”是g 雠】中唯一的孤立点。所以有，”d 器，u d 答，则 顶点u 是另一个孤立点，矛盾。因此图g 不舍一度点。 口 注意图3 1 中的图( b ) ( c ) ( d ) ，它们都含有一度点 3 2 构造强临界图 设图g 是强m 一临界图，则对任意顶点u y ( g ) ，集合d 器u f 。) 是图g 的最小 全控制集，其中 g 扣) 注意图3 1 中的m 一临界图( 6 ) ，其中一个顶点记为”1 容易验证，不存在图( 6 ) 的包含顶点”l 的最4 , 4 t 控制集。 命题3 1 1 8 图g g - i m 一临界图，则对任意顶点t 6y ( g ) ，存在图g 的包含顶 点u 的最小全控制集 3 2 构造强临界图 现在我们给出一个构造强临界图的方法。设顶点“和”分别是图f 和日中的 任意顶点，图r 由图，添加新的顶点而得到，且顶点t ，和u 拥有相同的开邻 点集。类似地，图月。由图日添加新的顶点t ，而得到，且顶点t ，和”拥有相同的 开邻点集。对图r 和凰添加边和t ，t ，得到的联结图记为( f o 日) ( u ，口) 。饲 如，设图f 和日分别是图3 2 中的图( ，) 和劬，则由图f 和日得到的联结图g = 妒。日) ( t ，口) 如图3 3 所示： f ：( ，)日： 图3 3 联结s g = o 哪( “，口) 定理3 2 1 由不舍孤立点的图f 和日得到联结图g = ( f o i 叼( u ，”) ，有证明仉( g ) = ( 聊+ m ( 研 证明由构造法，m ( r ) = m ( f ) ，m ( 风) = 仉( 日) ，所以有m ( g ) m ( r ) + m ( 凰) 一 m ( f ) + m ( 日) 。因此只需证明m ( g ) m ( r ) + m ( 凰) 。 中国科学技术大学硕士学位论文 设榘台s 是圈引搀最小全控镥l 爨，显昂= y ( r ) n s ，勖一y 鼠) n s 魏 果坼( ) n 鼬a 且n l l ( v ) n s 搿，则集合昂和妇分别全控制图凡和风所 以债( 研；i 酬= l s m + i s 氆( r ) + 僵( 1 0 ) 。如果( u ) f 、5 i f a 且n 日( v ) n s h 学 g ，那么集会全攘潮y 墨) 、 社，0 。嚣魏，秀了金控裁璎点”期，骞毡玲蕊 如。设顶点”是顶点“在图f 中的任意一个邻点。所以集合踟u 伽全控制玩， 集合翰 一 全控制熄，饥( g ) = l 删一l s f u w i + i s 圩 4 i 讯( r ) + 仉( 凰) 炎 骰缝，我朝霉敷迁骥，麴果蝎鬈) n s g 显n h 卿n 一痧，鄢么( 固麓( 我) + 馈( 鼠) 。如果坼一( ) n 踟；g 且慨r ( n 岛= a ，为了全控制顶点“、”、矿， 有 饥“，以s 设顶点是顶点t 在图f 上的一个邻点，顶点撕是顶点 在 图