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

摘要 摘要 图的控制理论是组合与图论的一个重要研究领域三十多年来，随着图的控 制理论不断发展和实际问题的需要，研究者提出了控制数的多种变形本文主要 围绕控制的v i z i n g 猜想及控制理论中其他重要问题展开研究主要研究对象有： f 七) 一控制、全控制和p 控制 在第一章里，我们首先介绍图论的历史背景和一些常用的概念然后，介绍经 典控制的概念及其研究问题 第二章重点讨论 七 控制数根据我们提出的划分和映射挪点新方法，得 到了c a r t e s i a n 乘积图的 庇 一控制数的一个下界：t 七 ( g 口h ) p ( g ) 7 懈( 日) + 7 m ( 日) ，这里m = 7 懈( g ) 一k p ( c ) 这个下界包含并提高经典控制v i z i n g 猜想 的多个现有的结果，为解决v i z i n g 猜想提供了一种新的方法同时，我们提出的 尼) 控制类v i z i n g 猜想也能从这个下界得到部分证明 第三章我们着重讨论全控制的一些等号刻画问题3 2 节分别刻画了所有满 足等式2 7 , ( k 2 i - - h ) = m ( k 2 ) 饥( 日) 和2 7 t ( c n 口h ) = 仇( g ) m ( h ) 的图日3 3 节 刻画了所有( m ，2 7 ) 一块图，从而将h e n n i n g 的结果从树情形推广到块图情形 第四章讨论树的p 控制在4 2 和4 3 节，我们首先给出了树图p 一控制数 的一个下界，并刻画了达到这个下界的树；其次刻画了带有唯一最小p 控制 集的树在4 4 节，我们提出新的概念一p 约束数6 p ( g ) ，并证明了对于树t ， 1 ( t ) a ( t ) 一p + 1 ，以及刻画了所有达到这些界的树 最后，我们总结本文所做的结果，并提出一些值得进一步研究的问题 关键词：控制，填装， 忌) 一控制，全控制，p 控制，树，块图，i 2 a r t e s i a n 乘积 a b s t r ac 1 a b s t r a c t t h ed o m i n a t i o nt h e o r yo fg r a p h si sa ni m p o r t a n tt o p i ci nc o m b i n a t i o na n dg r a p h t h e o r y i nt h el a s tt h i r t yy e a r s ，t h ec l a s s i cd o m i n a t i o nh a v ed e r i v e dv a r i o u so t h e rd o m i - n a t i o n sa c c o r d i n gt ot h ed i f f e r e n c eo fp r a c t i c a lp r o b l e m s t h i st h e s i sm a i n l ys t u d yt h r e e k i n d so fi m p o r t a n td o m i n a t i o n s ： ( g ) 一k p ( g ) t h i sl o w e r b o u n dc o n t a i n ss o m ek n o w nr e s u l t so nv i z i n g sc o n j e c t u r e ，a n ds ow ep r o v i d ea g e n e r a l a n dc o n c i s ep r o o ff o rt h e s er e s u l t s i na d d i t i o n ，w ep o s tt h e 七) 一d o m i n a t i o nv e r s i o no f v i z i n g sc o n j e c t u r e ，a n dp a r t i a l l yp r o v et h a ti ti st r u eb yt h i sl o w e r b o u n d i nc h a p t e r3 ，w eg i v es o m ec h a r a c t e r i z a t i o n so nt o t a ld o m i n a t i o n s e c t i o n3 2 c h a r a c t e r i z ea l lg r a p h shs a t i s f y i n g2 7 t ( k 2 口日) = 7 t ( k 2 ) t t ( h ) a n d2 7 t ( c n i q h ) = 7 t ( c n ) t t ( h ) ，r e s p e c t i v e l y s e c t i o n3 3g i v eac h a r a c t e r i z a t i o no f ( 吼，2 7 ) - b l o c kg r a p h s ， w h i c hg e n e r a l i z e st h er e s u l tg i v e nb yh e n n i n g i nc h a p t e r4 ，w es t u d ys o m ep r o b l e m so np - d o m i n a t i o n i ns e c t i o n s4 2a n d4 3 ， w ef i r s tg i v eal o w e rb o u n do fp d o m i n a t i o nn u m b e ro ft r e e sa n dc h a r a c t e r i z ea l lt r e e s a t t a i n i n gt h i sl o w e rb o u n d ；a n dt h e nw eg i v eac h a r a c t e r i z a t i o no ft r e e sw i t hu n i q u e m i n i m u m p d o m i n a t i n gs e t i ns e c t i o n4 4 ，w ei n t r o d u c ean e wc o n c e p t p b o n d a g e n u m b e rb d a ) ，s h o wt h a t1 b p ( t ) a ( t ) 一p + 1f o ra n yt r e et ，a n dc h a r a c t e r i z e a l lt r e e sa c h i e v i n gt h ee q u a l i t i e s i nt h ee n d ，w ec o n c l u d eo u rr e s u l t si nt h i sp a p e r , a n d p r o v i d es o m ep r o b l e m st h a t a l ew o r t h yo ff u r t h e rc o n s i d e r a t i o n k e y w o r d s ：d o m i n a t i o n ，p a c k i n g ， 尼】- d o m i n a t i o n ，t o t a ld o m i n a t i o n ，p - d o m i n a t i o n ， f l e e s ，b l o c kg r a p h s ，c a r t e s i a np r o d u c t i i i 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志 对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 保密的学位论文在解密后也遵守此规定。 挪 作者签名：j 碴正 细i 年月7 日 第1 章绪论 第1 章绪论 在这一章里，我们首先简要介绍图论发展的历史背景其次给出本文所涉及 到的图的基本概念和术语最后，介绍本文的主要概念一控制，以及所研究的问 题和结果 1 1图论的历史背景 图论从产生到现在已经有两百七十多年的历史了人们普遍认为图论第一 篇论文产生于1 7 3 6 年( 数学家l e u l e r 解决k 6 n i g s b e r g 七桥问题f 1 1 ) ，此后一直到 1 9 世纪中叶均被看成是图论的萌芽阶段，这一时期的图论大多是用图作为工具来 解决一些因游戏而产生的问题 1 9 世纪中叶到1 9 3 6 年，是图论的基本形成阶段这个时期里，大量图论中 的问题出现了特别是著名的四色问题( 1 8 5 2 年) ，它鼓励和引导图论发展了一 百多年虽然在1 9 7 6 年人们用计算机实现了它的证明，但是即使到现在还有许 许多多的图论工作者致力于寻求它的一个数学的证明同时，用图作为工具去解 决问题已经不仅仅局限在由游戏产硅的问题，还扩展到其他许多领域中例如， k i r c h h o f f ( 1 8 4 7 年) 用树研究电网络方程组问题；c a y l e y ( 1 8 5 7 ) 用树研究有机化 合物的分子结构问题这一切都促使图论产生了许多奠基性的新理论( 其中最杰 出的是m e n g e r 定理( 1 9 2 7 年) 、r a m s e y 定理( 1 9 3 0 年) 和k u r a t o w s k i 定理( 1 9 3 0 年) 等) ，为图论的形成扎下了坚实的基础终于，在1 9 3 6 年匈牙利数学家d k 6 n i g 写 出了第一本图论专著有限图与无限图的理论，标志了图论真正成为一个新的 数学分支 1 9 3 6 年以后，由于计算机、通讯网络、交通运输、和生产管理等方面卅现了 许多离散性问题，尤其是随着计算机技术的飞速发展，图论的各个分支，如代数图 论、极值图论、随机图论、化学图论、超图和复杂性理论等得到了空前的发展这 也归功于图论与其他数学分支的联系更加紧密了到现在，数论、概率、分析、 拓扑、代数和几何等作为数学工具已经被大量运用在图论的研究中；与此同时， 图论方法也被越来越多地被运用到其他数学领域的研究中，一个杰出的例子是 s z e m e r 6 d i 正则性引理 这种大繁荣也相辅相成地产生了一大批非常优秀的图论专著例如，有 向图方面的b a n g j e n s e n 和g u t i n t 2 1 ，代数图论方面的b i g g s t 3 。，极值图论方面的 b o l l o b g s t 引，随机图方面的b o l l o b g s t s l ，染色方面的j e n s e n 和t o f t t 6 ，匹配方面的 l o v f i , s z 和p l u m m e r l 7 1 ，组合优化方面的s c h r i j v e r t 引，流方面的z h a n g 引另外，还有 1 第l 章绪论 许多好的电子书刊和致力于图论方向的杂志，这些都为图论的发展注入了新鲜的 血液 1 2 图的基本概念 什么是图? 简单地说，图( g r a p h ) 是由些( 项) 点和一些由两点连成的 线( 边) 组成的整体一般地，一个图g 严格的数学定义是：g 是个有序的三元 组( y ( g ) ，e ( g ) ，矽) ，简记为( ke ，妒) ，其巾y 是g 的( 顶) 点集( v e r t e x s e t ) ，它的 元素称为g 的( 顶) 点( v e r t e x ，n o d e ，p o i n t ) ；e 是g 的边集( e d g e s e t ) ，它的元素 称为g 中的边( e d g e ，l i n e ，a r c ) ；而矽是e 到vxv 的映射，称为g 的关联函数 ( i n c i d e n c ef u n c t i o n ) ，它规定了g 的边与顶点之间的关联关系，即 曲：e 叫v v 妒( e ) = x y 若v v 中元素全是有序对，则称g 为有向图；若v v 中元素全是无序 对，则称g 为无向图如果 是图g 的一个顶点和e 是图g 的一条边，则我们分 别记之为 v ( c ) 和e e ( g ) 给定一个无向图g ，我们可以给g 中每条边规 定一个方向，得到的有向图称为g 的定向图( d i r e c t e dg r a p h ) ，于是我们就能将所 有的有向图看成某个无向图的定向图了图g 的边集e 如果包含相同的元素，则 称g 有重边( m u l t i p l ee d g e ) ；如果e = u 钉e ，则称e 是g 的一个环( 1 0 0 p ) 一个 无环无重边的图称为简单图( s i m p l eg r a p h ) 值得注意的是，本文所说的“图”，均 指简单无向图 下面我们简要介绍本文涉及到的基本术语，这些术语在一般的图论书 本上都有，读者可以参考任何一本优秀的图论教科书，作者推荐b o n d y 和 m u r t y 1 0 1 、d i e s t e l l l l 】和徐俊明1 1 2 , 1 3 1 阶与规模( o r d e ra n ds i z e ) ：图g 的顶点个数称为g 的阶，即l y ( g ) i ；边的 个数称为g 的规模，即i e ( c ) i 如果i y ( g ) l = 1 ，则称g 是平凡图( t r i v i a lg r a p h ) ， 所有其他的图均为非平凡图( n o n t r i v i a lg r a p h ) ；如果l e ( g ) i = 0 ，则称g 是空图 ( e m p t yg r a p h ) 2 端点( e n d - v e r t e x ) ：如果两点z 和可有一条边e 相连，那么我们称z 和y 为 e 的端点为了突出边e 的两个端点，我们通常用z 留米表示边e ，即e = x y 边与 它的两个端点称为关联的( i n c i d e n t ) 一个顶点若不与任何边相关联，则称之为孤 立点( i s o l a t e dv e r t e x ) 3 相邻( a d j a c e n t ) ：如果两点有一条公共的关联边，则称这两点是相邻的；如 果两边有一个公共端点，那么也称这两条边是相邻的 2 第1 章绪论 4 邻域( n e i g h b o r h o o d ) ：图g 中所有与顶点口相邻的顶点均称为口的邻点 ( n e i g h b o r ) ，所有口的邻点构成的集合称为u 的开邻域，记为g ( u ) ，并称gv 】= g ( u ) u 口) 为口的闭邻域；令s y ( g ) ，我们分别用g ( s ) = 乩s a r a 扣) 和 n d s 】= ( s ) us 来表示s 的开邻域和闭邻域 5 度( d e g r e e ) ：图g 中顶点钉的所有邻点个数i g ( u ) l 为u 的度，记为d a ( u ) ； 图g 中顶点度的最大值和最小值分别被称为g 的最大度和最小度，记为a ( a ) 和6 ( g ) g 的所有一度点均称为g 的叶点( 1 e a f ) ；与叶点相邻的点被称为g 的支 撑点( s u p p o r tv e r t e x ) g 的叶点集和支撑点集分别被记为l ( g ) 和s ( g ) 6 子图( s u b g r a p h ) ：如果图g 和日满足v ( h ) y ( g ) ，e ( h ) e ( g ) ，则称 日为g 的子图，记为日g 若日为g 的子图且f y ( 日) l = i v ( g ) i ，则称日是g 的支撑子图( s p a n n i n gs u b g r a p h ) ；设e 7 e ( g ) ，g 一表示g 的一个带有边集 e ( g ) 一e 7 的支撑子图，当e 7 是单边e 时，用g e 来代替g 一 e 设s v ( g ) ， 称g s 1 为s 的生成子图( 也称诱导子图) ，它的顶点集是s 并且边集满足s 中任 意两点相邻当且仅当它们在g 中也相邻为方便起见，我们用g s 来表示诱导 子图g v ( g ) 一翻，特别当s 是单点z 时，用g z 来代替g 一 z ) 7 完全图( c o m p l e t eg r a p h ) ：n 阶完全图是一个任意两个不同的顶点均相邻 的佗阶图，记为 墨路( p a t h ) ：r = z l z 2 z n 表示一条带有礼个顶点的路，它的顶点 集是y ( r ) = x l ，x 2 ，z n ，边集是e ( r ) = z l x 2 ，x 2 x 3 ，x n - l x 几) ，简记 为x l x n - 路并称n 一1 是r 的长度( 1 e n g t h ) ，y ( r ) z 1 ，x n ) 是r 的内点 ( i n t e r n a l l yv e r t e x ) 如果两条z y 路p 和q 没有公共内点，则称p 和q 是内点不 交的( i n t e r n a l l yd i s j o i n t ) 9 圈( c y c l e ) ：我们用g = z l z 2 z n z l 表示一个带有礼个顶点的圈，它的顶 点集和边集分别是y ( q ) = p l ，x 2 ，z 住 和e ( c k ) = x l x 2 ，x 2 x 3 ，x n - 1 z n ， x n 2 1 ，并称扎是g 的长度( 1 e n g t h ) 1 0 二部图( b i p a r t i t eg r a p h ) ：我们将一个不含奇圈的图称为二部图于是， 任何一个二部图g 的顶点集可以划分为两个非空子集x 和y ，使得g 的任意一 条边分别与x 和y 中某点相关联这里的x 和y 是g 的两个部( p a r t ) ，并记g 为g = ( x ，y ) 如果点集x 为单点集，y 有礼个点，则称g 为星图( s t a r ) ，记为 甄，n ，并称单点x 为琏，n 的中心点( c e n t r a lv e r t e x ) 另外，符号s ( a ，b ) 表示一个 双星图( d o u b l es t a r ) ，它是通过在两个星图n ，a l 和k 1 b l 的中心点间填加一条 边构成的 1 1 连通( c o n n e c t e d ) ：若图g 中任意两点之间都有路相连，则称g 为连通图 它的每一个极大连通子图都叫作g 的一个连通分支( c o m p o n e n t ) ，g 的所有连通 分支个数叫作g 的连通分支数，记为叫( g ) 3 第1 章绪论 1 2 七连通的( k - c o n n e c t e d ) ：如果图gi i i 任何两个不同的顶点问均至少有尼 条内点不交的路 1 3 割点( c u t v e r t e x ) ：设z 是图g 的一个顶点，如果g 是连通的但是g z 不是连通的，则称z 是g 的一个割点 1 4 块( b l o c k ) ：一个不包含割点的极大连通子图称为一个块因此图g 的块 要么是指g 的极大2 连通子图要么是指g 中2 阶完全图恐如果图g 的每个 块均是完全图，则称图g 为块图( b l o c kg r a p h ) ；如果图g 的每个块或者是圈或者 是，则称g 为仙人掌图( c a c t u sg r a p h ) ；如果图g 的每个块或者是完全图或者 是圈，则称g 为块仙人掌图( b l o c k - c a c t u sg r a p h ) 1 5 林与树( f o r e s ta n dt r e e ) ：不含任何圈的图称为林不含任何圈的连通图 称为树，为区别起见，我们通常用f 来表示林，用t 来表示一棵树很容易证明， l e ( f ) l = l y ( f ) i 一“，( f ) 很明显，林与树均是最简单的块图 1 6 距离( d i s t a n c e ) ：令也和u 是图g 中任意两点，g 中最短的t 与u 之间的 路的长度称为乜到u 的距离，记为d g ( u ，秽) 所有顶点对中，距离最长的一对点称 为g 的一对直径点，它们之间的距离称为g 的直径，记为d ( g ) ，即 d ( g ) = m a x d g ( u ，u ) ：v 让，钉y ( g ) ) 1 7 同构( i s o m o r p h i s m ) ：两个图g 和日是同构的，记为g 竺h ，是指存在一 个双射 0 ：v ( a ) 一v ( h ) 满足 让u e ( g ) 亨口( 缸) p ( ) e ( 日) 很显然，两个相互同构的图可以看成是同一个图 1 8 c a r t e s i a n 乘积( c a r t e s i a np r o d u c t ) ：我们用g 3 h 来记g 和日的笛卡 尔乘积图，它的顶点集是 v ( a 口h ) = v ( g ) v ( h ) = ( z ，y ) ：z y ( g ) ，y v ( 日) ) ， 边集是 e ( g v i h ) = ( z l ，y 1 ) ( z 2 ，y 2 ) ：2 ：1 = z 2 且y l y 2 e ( h ) 或x 1 2 1 2 e ( g ) 且 y x = y 2 ，这里x l ，x 2 v ( g ) 和可l ，y 2 y ( 日) 也就是说，g i - - i h 中任意两个顶点( x l ，y 1 ) 和( x 2 ，y 2 ) 相邻当且仅当或者x l = 现 且y l y 2 e ( 日) ，或者y l = y 2 ，且x l x 2 e ( g ) 类似地，我们可以定义仇个图 4 第l 章绪论 g 1 ，g m 的c a r t e s i a n 乘积g 1 口d g m ，即 v ( g a 口e g m ) = y ( g 1 ) v ( g m ) 且任意两点 z ，z m ) 与( y 1 ，) 相邻当且仅当它们恰有一个坐标不 同( 不妨设第i 个) 和盈玑e ( g t ) 因为c a r t e s i a n 乘积保留了许多原图的性质，所 以c a r t e s i a n 乘积是一种由小图构造大图非常有效的方法本文所研究的对象很 大一部分就是c a r t e s i a n 乘积图图1 1 就是我们熟知的立方体q 3 ，它是由a 与 鲍或者由三个鲍相互c a r t e s i a n 乘积所得的图 图1 1 立方体q 3 = c 4 口鲍= 尬口鲍口尬 1 3 问题研究及所得结果 首先介绍经典控制的概念它的提出也是源于现实问题一设施选址问题，发 展至今已在许多领域都有重要的应用例如，在通信网络里，信息传输是要靠某些 站点的发射器来完成的，并且发射器只能将信息发送至一些与之相邻的站点为 了让信息传输至每个站点同时又考虑到节约成本，需要选取恰当的站点安装发射 器使得发射器的数目尽可能地少为了解决这一问题，人们将通信网络抽象成图， 每个站点看成图中的点，站点间的连接视为图中的边这样，寻找恰当的站点就成 了找图的最小控制集，对应站点数目就是图的最小控制数 定义1 1 设g 是图和d y ( g ) 如果对于任意的顶点u y ( g ) ，均有 i g p 】nd l l ，则称d 是g 的一个控制集( d o m i n a t i n gs e t ) 所有g 的控制集中 包含顶点数最少的称为g 的最小控制集最小控制集的顶点个数称为g 的控制 数( d o m i n a t i o nn u m b e r ) ，记为7 ( g ) 所有g 的最小控制集均可记为- r ( a ) - 集 5 第1 章绪论 从控制集的定义看出，每个控制集以外的点在该控制集里至少有一个邻点 换句话说，如果我们找到通信网络抽象图的最小控制集，在对应站点安装发射器， 则就能确保每个站点接收到信息至少一次，并且安装成本最小 下面顺便给出填装和填装数的定义，它们同控制有一定的联系，在许多控制 理论的文献里都被涉及到 定义1 2 设g 是图和s y ( g ) 如果对于任意的顶点u ，t ，s ，均有g 【乱】n g m = 0 ，则称s 是g 的一个填装( p a c k i n g ) g 中最大的填装所含顶点个数称 为g 的填装数( p a c k i n gn u m b e r ) ，记为p ( g ) 很显然，对于g 的任意一个最大的填装s 和，y ( g ) 一集d ，s 的任一顶点的 闭邻域均含有d 中点，从而p ( g ) = l s i d l = ，y ( g ) 如果p ( g ) = 7 ( g ) 一而， 则我们称g 是一个( p ，y 一惫) - 图d o m k e 等人【1 4 1 已经证明任意块图g 均满足 p ( a ) = - y ( g ) ，所以块图是( p ，7 ) 一图类的一个子类；对于n 长的圈g ，如果n 三o ( m o d3 ) 时，则有j d ( g ) = p ( g ) ，从而g 是一个( p ，y ) - 图，如果n 为其他情形，则 均有p ( c k ) 一1 = p ( c k ) ，所以g 为( p ，7 1 ) 图；对于著名的p e t e r s o n 图g ，我 们可以根据控制数和填装数的定义，很容易验证出p ( a ) = 3 和p ( a ) = 1 ，所以 p e t e r s o n 图是一个( j d ，1 2 ) 图 时至今日，控制理论的理论体系日趋庞杂：吸引了越来越多的图论工作者为 之努力奋斗对它的研究切入点也是非常之多，我们大致列举以下五个与本文研 究相关的方面 一类v i z i n g 猜想 1 9 6 8 年，数学家v i z i n g 在文献里提出了著名的v i z i n g 猜想：对于任意的 两个图g 和日， 7 ( g 口h ) ，y ( g ) ，y ( 日) 四十多年过去了，令人遗憾的是该猜想仍然未能得到证明或反证，但是却也得到 一些令人可喜的结果，例如： ( a ) 1 9 9 5 年，h a r t n e l l 和r a i l t l 6 】证明了：如果g 是一个( p ，y ) 一图或( p ，y 一1 ) - 图，则v i z i n g 猜想成立； ( b ) 1 9 9 6 年，c h e n 等i ”】证明了：7 ( g 口日) p ( g ) ，y ( 日) + p ( 日) n ( g ) 一p ( g ) ) ； ( c ) 2 0 0 0 年，c l a r k 和s u e n l l 9 1 证明了：y ( g n h ) ，y ( g ) ，y ( 日) 以上三类分别代表v i z i n g 猜想的三个主要研究方向：( a ) 代表了寻找尽可 能多地使得v i z i n g 猜想成立的图类；( b ) 代表了通过引人新的有关参数，给出 c a r t e s i a n 乘积图的控制数下界；( c ) 代表了寻求尽可能大的，使得7 ( g 口日) 七7 ( g ) 7 ( 日) 6 第1 章绪论 对v i z i n g 猜想的研究还在继续，陆续有些结果出来，但是大多是属于( a ) 类研究方向于是，人们转而考虑其它各种控制数的类v i z i n g 猜想，比如全控制类 v i z i n g 猜想：2 7 t ( a 口h ) 7 d g ) 7 t ( h ) 它在2 0 0 5 年由h e n n i n g t 2 0 1 提出2 0 0 8 年， u t i l m a t h 接收的文章【2 1 】证明了该猜想是对的，并在文章里提出了公开问题：刻 画满足2 7 t ( g 口h ) = 吼( g ) 饥( 日) 的所有图g 和h 2 0 0 9 年，李宁和侯新民【2 2 】独 立地证明了全控制类v i z i n g 猜想的更广形式一全 忌 控制类v i z i n g 猜想也是 成立的 本文第二章主要研究c a r t e s i a n 乘积图的 七) 控制数，证明了7 懈( g 口h ) p ( g h 似( h ) + 1 伽 ( h ) ，这里m = 一y 懈( g ) 一k p ( o ) 根据这个下界，我们提出了 v i z i n g 猜想的广义形式一 尼) 控制类v i z i n g 猜想： k 7 詹) ( g 口h ) ，y 懈( g ) ，y 七) ( 日) 并证明了对于( p ，- y ) 图该猜想成立；此外，当七= 1 时，很容易看出我们所得的下 界不仅提高了c h e n 等【”1 的结果，还能推导出h a r t n e u 和r a i l t l 6 1 的结果，从而为 解决v i z i n g 猜想提供了一种新的方法 关于全控制类v i z i n g 猜想的等号刻画问题，h e n n i n 9 1 2 0 l 已经刻画了g 为至 少3 阶的树时的所有日，t r 未能解决g = 恐情形本文第三章第二节就是刻画 在g = 或c k 时的所有日结合h e n n i n g 的结果，全控制类v i z i n g 猜想的等 号刻画问题在g 为树和圈情形得到解决，更广情形仍需进一步研究 二各种控制数之间的关系 随着对经典控制理论研究的深入和各种实际情况的需要，人们提出了各种各 样的控制，它们均是经典控制的推广或者对控制集增加某些约束条件在多样化 的控制理论研究中，很自然就会产生一个研究方向：研究各种控制数之间的联系 这一方向的研究一方面是用一种控制数给出另一种控制数的界，更广泛的是另一 方面，刻画所有达到这种界的图 例如，众所周知控制数小于或等于独立控制数，在文献t 2 3 】里，c o c k a y n e 等人 就刻画所有( 7 ，i ) 一树；很容易证明：7 ( g ) m ( g ) 2 ，y ( g ) ，2 0 0 1 年，h e n n i n g t 2 4 1 刻 画了所有的( m ，2 ，y ) 树，并在2 0 0 8 年发表在d i s c r e t em a t h 的关于全控制的综述 文章里将( m ，2 7 ) 一图的刻画问题列为二十个公开问题之一关于各种控制数之间 的关系的文献很多，读者可以参阅两本重要的综述性书1 2 5 , 2 6 1 ，以及文献1 2 7 - 2 9 1 等 本文第三章第三节就是刻画了所有的( t ，2 7 ) 一块图，从而将h e n n i n g 的结果推广 到更广的块图情形 三各种控制数的界 任何一种参数的提出，人们首先要考虑的是它的界，也就是利用各种已知或 易知的参数给出该参数的上下界对于各种控制参数，同样如此图中易知的参数 7 第1 章绪论 有图的阶、规模、叶点数和支撑点数等等于是，对于经典控制数，人们试图利用 图的阶给出，y 的上界，日前最好的结果是：对于任意的n 阶图g 有，y ( g ) 号1 ， 这个上界早在1 9 6 2 年就由o r e l 3 0 给出，但是对于达到这个上界的刻画却是要到 2 0 0 0 年，它是由x u 和z h o u 3 1 】刻画的；但是关于经典控制数的下界，目前较好的 结果仅仅是树情形，即l e m a f i s k a t 3 2 证明了：如果树t 的阶为7 1 , ，叶点数为，则 7 ( t ) ( 7 1 , + 2 0 1 2 1 9 8 5 年，f i i l l 【和j a c o b s o n 3 3 】首先提出了经典控制数7 的另一种广义形式一 p 一控制数，这儿，y 1 = 1 自然他们也是首先考虑了的界，在该文章里，他们给 出了扎阶树图t 的一个下界：( t ) 垃等盟2 0 0 7 年，v o l k m a n n t 3 4 1 又刻画了 所有满足( t ) = f 半1 的树t 2 0 0 6 年，b l i d i a 、c h e l l a l i 和v o l k m a n n 在文 章【3 5 1 里利用树图t 的阶礼和p 叶点数i l p ( t ) | 给出并刻画了- y p ( t ) 的一个上界： ( t ) m + i l p ( t ) i ) 2 受b l i d i a 等人的启发，我们引入了p - 支撑点数昂的概 念，从而给出了n 阶树图t 的3 , p ( t ) 的一个下界： ( t ) 堕婴坐趔， 并且我们刻画了所有达到这个下界的树，可以证明这个下界在某些情形下提高了 f i n k 和j a c o b s o n 提出的界这部分的内容在本文第四章第二节 四唯一最小控制集 我们都知道，各种控制参数就是它们对应的最小控制集的基数可见，在对于 控制数的任何研究中，都必须要讨论最小控制集的有关性质于是，许多图论工作 者对于最小控制集的一种极端情形产生了兴趣：刻画带有唯一最小各种控制集的 图由于一般图的内部情况过于复杂，使得人们所得的结果大多局限在一些特殊 图类上 例如，g u n t h e r 等【蚓刻画了所有带有唯一最小控制集的树图；f i s c h e r m a n n 和 v o l k m a n n l 3 7 1 以及f i s c h e r m a n n t 3 8 1 推广了g u n t h e r 等的结果，分别刻画了所有带 有唯一最小控制集的仙人掌图和块图；2 0 0 4 年，f i s c h e r m a n n t 3 9 1 又刻画了所有带 有唯一最小全控制集的树图还有许多这种刻画我们就不一一列出从他们的研 究得到启发，我们刻画了所有带有唯一最小p 控制集的树，这部分的内容在本文 第四章第三节 五控制稳定性 1 9 9 0 年，f i n k 等m j 为了测量互连网络( 可以抽象成图) 在一些连接失败条件 下的稳定性，而引入了约束数b 的概念，也就是图中最少需要破坏掉多少条边才 能使得图的控制数提高随后许多人都投入到对于约束数的研究中，读者可参阅 文献 4 1 - 5 5 等 除了对约束数本身进行研究外，根据控制参数的多样化，人们也提出了对 g 第1 章绪论 应于其他控制参数的约束数例如，1 9 9 1 年。k u l l i 和p a t w a r i 在【蚓提出了全约 束数的概念；2 0 0 8 年，r a c z e k 在【5 7 】提出了成对约束数的概念；同样在2 0 0 8 年， h a t t i n g h 和p l u m m e r 在【5 8 】提出了限制约束数的概念等等至今，约束数的概念 已经非常丰富在本文的第四章第四节，我们提出了p 约束数的概念6 口，注意， b 1 = b ，证明了对于任意带有最大度p 的树t 均有b p ( t ) 一p + 1 ，并且 分别刻画了达到这个上界和满足k ( t ) = 1 的树 9 第2 章 尼) - 控制 本章主要研究c a r t e s i a n 乘积图的( 惫 一控制数内容取材于已发表于d i s c r e t e m a t h 的文章f 5 9 】，主要结论为： 1 证明了：，y 时( g 口日) m a x p ( g ) v 七 ( 日) ，p ( h ) ，y 耐( g ) ) 2 证明了：如果m = ，y 懈( g ) 一k p ( g ) 0 ，则 9 七 ( g 口日) p ( g ) ，y 七) ( 日) + 一y m ，( 日) 3 提出了 尼) 控制类v i z i n g 猜想：k 7 q ( g 口日) 7 懈( g ) 7 懈( 日) ，并利用上 面结果给出部分证明 2 1 忌一控制的定义 令d 是图g 的一个控制集如果给d 上所有点赋上权1 ，v ( a ) 一d 上所有 点赋上权0 ，根据控制集的定义有，g 中任意顶点的闭邻域的权和均大于或等于 1 根据这一思路，人们将经典控制推广到 七) 一控制 假设y 是一个实数集，函数，：y ( 台) 一y 的权是u ( ，) = 口y ( g ) ，( u ) 对 于任意子集s y ( g ) ，我们定义y ( s ) = s f ( v ) 因此u ( ，) = ，( y ( g ) ) 定义假设k 是一个固定的正整数，n = o ，1 ，2 ，) i 是非负整数集如果函数 ，：v ( c ) 一n 满足条件：对于任意的点u y ( g ) ，厂( g m ) k ，则称，是g 的 一个 忌) 控制函数( k - - d o m i n a t i n gf u n c t i o n ) 并称 7 七) ( g ) = m i n ( w ( f ) ：，是g 的 七卜控制函数) 是g 的 七) - 控制数( 七一d o m i n a t i o nn u m b e r ) 从上述( ) - 控制数的定义可以看出，我们能够将 l l 。) 一控制函数的取值范围 限定在 0 ，1 ，尼) 关于三个参数p ( g ) 、，y ( g ) 和7 似) ( g ) 之间的关系，d o r n k e 等 6 0 1 已经证明了： 定理2 1 l 删任意图g 和正整数k ，k p ( g ) 7 懈( g ) 研( g ) 从定理2 1 ，我们立即能得到下面推论 推论2 2 如果g 是一个( p ，7 ) 图，则一惫1 ( g ) = k p ( o ) ；研( g ) 第2 章 k ) 一控制 在第一章里，我们说到了v i z i n g 猜想吸引了许多的注意，但是不幸的是至今 v i z i n g 猜想仍然未能得到证明或者反驳于是，许多人很自然地将目光转向其他 的控制数，希望解决类似的问题在 七) 控制数方面，最先考虑c a r t e s i a n 乘积图 的是b r e a r , h e n n i n g 和k l a r z a r t 6 1 1 他们证明了： 一y 七( g ) 7 ( 惫 ( 日) k ( k + 1 ) ，y 七 ( g 口日) 和 ，y 詹 ( g ) ，y ”( 日) 2 k 7 七 ( g d h ) + 七妒( g ，日) ， 这里g 和日是任意两个图，以及 妒( g ，日) = m i n l v ( h ) l ( k 1 ( g ) 一7 七( g ) ) ，i y ( g ) i ( 尼7 ( 日) 一，y 知 ( 日) ) ) 受他们的研究启发，我们利用g 和h 的填装数及 惫) 一控制数也给出了 ，y 懈( g 口日) 的一个下界 2 2 c a r t e s i a n 乘积图的 尼) 一控制数 在这一节里，我们主要是给出并证明下述定理2 3 定理2 3 已知g 和日是两个任意的图，k 1 是一个正整数，则 ( 1 ) ，y ( g 口日) m a x p ( g ) 7 七) ( 日) ，p ( 日) 7 似) ( g ) ) ( 2 ) 如果m = 7 t 七) ( g ) 一k p ( g ) 0 ，则 ，y 忙 ( c d h ) p ( g ) ，y 惫) ( 日) + ，y m ) ( 日) 为了证明定理2 3 ，我们需要一些准备工作取定a = v l ，v p ( c ) ) 是g 的 一个最大的填装根据填装的定义，闭邻域集 g 【u 1 】，g 【( g ) 】是两两相互 不交的对于i = 1 ，p ( g ) ，令 = g 【仇】和o = y ( g ) 一u 骘h 于是， h o ，1 ，玎p ( g ) ) 是v ( a ) 的一个划分( 注意1 1 0 可能是空集) 就i = 1 ，p ( a ) 和叫y ( h ) ，我们令 = 仇) y ( 日) 、g 叫= v ( c ) ) 和g t 芦= 叫) 很明显，由凰。( g 叫) 诱导的子图同构于日( g ) ，因此在下面的表述中我们用玩 和g 来分别代替( g 口日) 【上k 】和( g r - h ) g 1 1 2 第2 章 k ) 控制 设，是g 口日的一个最小的 七) 一控制函数，则u ( 厂) = 7 畸( g 口日) 为了方便 起见，我们用，( t ，u ) 来代替，( ( u ，口) ) ，这里( u ，u ) 是g v l h 的任意顶点 引理2 4 ，y 知 ( g n h )