（计算数学专业论文）图的控制参数和一类极值问题.pdf

摘要 图的某些参数，如图的控制参数，因为其在图论的研究以及现实世界的各种 应用中固有的重要性，而得到广泛的研究和发展。图的控制集定义为图中的一个 点的集合，使得图中其它任何一个点都与该点集中的某个点邻接。确定图的控制 集问题在网络的目标、安全装置和便利设施等的定位的方面有很大用处。在过去 的3 0 多年里，对图的各种控制参数的研究已经成为图论研究的一个重要领域， 迄今为止关于图的控制参数问题的研究已有上千篇文章，现在已有近百种类型的 控制形式得到研究。 本文主要工作包括以下几个方面： ( 1 ) 简单介绍了几种常见的控制参数的概念和应用，以及它们的上下界和 相互关系； ( 2 ) 讨论了连通图g 的连通k - 控制数( g ) 的上下界，并证明了不等式 焖等 嘲埘； ( 3 ) 给出在树和单圈图中，2 控制数和连通2 控制数相等的充分必要条件， 并加以证明； ( 4 ) 讨论了给定边数和顶点数的图的一类极值问题。对于所有给定边数和 顶点数的图，我们将刻画出其所有顶点度数的口f 0 口 1 1 次方的和为最小的一 个图，这个图是由一个最大的完全子图和一个非孤立点，以及其它一些孤立点组 成，并证明这个图是唯一满足条件的图。 关键词：k 一控制；连通k 一控制：2 一控制数；连通2 一控制数；单圈图；m i n i m i z s p g r a p h a l 酶t r a c t g r a p hp a r a m e t e r ss u c ha sd o m i n a t i o np a r a m e t e r sh a v eb e e ns t u d i e de x t e n s i v e l y d u et ot h e i ri n 缸s n s i ci m p o r t a n c ei nt h e 咖d yo f g r a p ht h e o r ya n d t h ea p p l i c a t i o n si n t h er e a lw o r l d a d o m i n a t i n gs e t d o f a g r a p h g i sd e f i n e da sas u b s e to f v e r t i c e si n g ， s u c ht h a te a c hv e r t e xn o ti n d i s a 由a c e n tt oa tl e a s to n ev e r t e xi n d t h ep r o b l e mo f d e t e r m i n i n gt h ed o m i n a t i n gs e t sh a sm a n ya p p l i c a t i o n s i nt h el o c a t i o no fo b j e c t s ， s a f e g u a r d so rf a c i l i t i e so i lt h ev e r t i e e so f an e t w o r k d u r i n gt h ep a s t3 0y e a r st h es t u d y o fd o m i n a t i o np a r a m e t e r so fag r a p hh a sb e c o m eas i g n i f i c a n ta r e ao fr e s e a r c hi n g r a p ht h e o r y t od a t e ，t h e r ea l em o r e t h a no n et h o u s a n d p a p e r sw r i t t e no n d o m i n a t i o n p r o b l e m sa n dn e a r l y1 0 0d i f f e r e n tt y p e so f d o m i n a t i o nr e l a t e dp a r a m e t e r sh a v eb e e n s t u d i e d i nt h ef o l l o w i n g ，w el i s tt h em a i nw o r k si no u r p a p e r ： ( 1 ) w ei n t r o d u c e b r i e f l yt h ec o n c e p t so fd o m i n a t i o np a r a m e t e r sa n dt h e i r a p p l i c a t i o n s , g i v e t h eb o u n d sa n ds o m er d a t i o n o f t h e s ed o m i n a t i o n p a r a m e t e r s ( 2 ) w ed i s c u s st h eb o u n d so ft h ec o n n e c t e dk d o m i n a t i o nn u m b e r 疙( g ) o f c 。n n e c t e a s m p h g ，a n d p r o v e t h e m e 叩豇；谚形( g ) ( z 七+ 等 以( g ) 一z t ( 3 ) w ec h a r a c t e r i z et h ec l a s so ft r e e sa n du n i c y c l i cg r a p h sf o rw h i c ht h e 2 d o m i n a t i o nn u m b e r sa r ee q u a lt ot h ec o n n e c t e d2 一d o m i n a t i o nn u m b e r s ，a n d p r o v e t h e m ( 4 ) w e c o n s i d e r t h e f a m i l y o f g r a p h s w i t ha f i x e d n u m b e r o f v e r t i c e s a n d e d g e s a m o n g a l lt h e s eg r a p h s ，w ea r el o o k i n gf o rt h o s em i n i m i z i n gt h es u mo f p o w e r s ao f t h ev e r t e xd e g r e e s ，f o ra l l l 2 口 ，称非负整数序列( d ( v 1 ) ，d “) ，d ( v p ) ) 为图g 的 度序列。 每一对顶点间都有边相连的无向简单图称为完全图，有n 个项点的无向完全 图记作e 。图g = ( 矿，e ) 称为二部图或者偶图，如果点集矿可以分成两个非空子 集x ，y ，即x u ，= y 且盖n y = o ，使得e 中每条边的一个端点属于z ，另 一个端点属于r 。二部图g 称为完全二部图，若对任意”z ，v y ，都有 u v e e ( g ) 。若完全二部图的两个部分有l x l - s ，l y i = f ，则记作k 。，当其中的 一部分，不妨速z 只含有一个点时，我们称为星，记作墨，其【 堡为，的点称 为星的中心。 路只是指点集为矿( 0 ) = y 1 ，y 2 ，咋) ，边集为五( 只) = 码屹，k 一。吒) 的图， 或称为路“，) ，或v l 心路，n 一1 是路的长度g 中点“与v 称为连通的， 如果在g 中存在”一v 路。若g 中任意两点连通，则g 称为连通图，否则称g 不 连通。圈c 是指点集为矿( c ) = v j ， ，边集为e ( c ) = v 1 v ：，h 。k v 1 ) 的图， 大连理工大学硕士学位论文 记为圈e 或圈“，k ) ，”是圈的长度。没有圈的图我们称为森林，记作f ； 没有圈的连通图称为树，我们记作丁。 图日称为g 的子图，如果v ( h ) v ( g ) ，e ( h ) e ( g ) ；若日包含g 的所 有的点，则称日为g 的支撑子图；当日是森林时，我们称为支撑森林：当日是 树时，我们称为支撑树。对集合z 矿( g ) ，导出子图( 矽或g f z 是以| = j 为点集 的g 的最大予图。 图g 中顶点之间的连通关系构成顶点集合的一个等价关系，在这个等价关系 下，可将v ( o ) 划分成有限个等价类，其中每一个等价类构成的g 的子图称为g 的 一个连通分支，g 的连通分支数目记为国( g ) ，可见g 为连通图当且仅当 埘( g ) = l 。若在图g 中去掉一个点后图的连通分支数增加，则称该点为g 的割点。 对点v 矿( g ) ，定义材与v 的距离如( 材，v ) ( 无混淆的情况下简写为d ( 封，v ) ) 为”与v 之间的最短路的长度，图g 的直径击删( g ) 定义为m a x 。郴) 如( “，v ) 。 设g 是以y ( g ) 为顶点的图，若召中两点在g 中相邻当且仅当它们在g 中不 相邻，则称石为g 的补图。 对任意连通图g ，定义g 的毒次幂g 为：v ( g ) = v ( g ) ，柳e ( g ) 当且 仅当l d 6 ( u ，v ) s 七。对图g l 和g 2 ，定义图的笛卡尔乘积g l x g a 为： 矿( g 1 g 2 ) = 矿( g 1 ) x 矿( g 2 ) ，点( v 1 ，v 2 ) 与“，甜：) 相邻当且仅当v i i 。e ( g 1 ) 且 p 2 = “2 或v l = 且v 2 叱e ( g 2 ) 。 图g i 与g 2 称为同构的，记作g l 兰g 2 ，如果存在双射：矿( q ) _ 矿( g 2 ) ，是 对任意“，v 矿( g 1 ) ，u v e e ( g 1 ) 当且仅当m ( “) o ( v ) e ( g 2 ) ，我们说图g 的一个 c o p y 指的是与图g 同构的图a 本文的主要工作包括以下几个方面： ( 1 ) 简要叙述了图的控制参数的发展，介绍了图论的基本概念和术语； 4 图的控制参数和一类极值问题 ( 2 ) 简单介绍了几种常见的控制参数邸图的控制集，独立集，无赘集以及 图的连通控制集和t o t a l 控制集，以及它们的上下界，弓i t tk ，控制、k 独立控 制、k - 无赘和t o t a l 七控制这四类控制参数，介绍了它们的性质和相应的控制集 在实际中的具体应用；给出了这些参数之间的关系式 以( g ) 靠( g ) i k ( g ) 吼( g ) s f 。( g ) 上唯( g ) ；另外，还给出了有关这些参数的 其他一些关系式，最后，给出了一些控制数的n o r d h a u s g a d d u m 类型的结果。 ( 3 ) 讨论了连通图g 的连通k 一控制数r k g ) 的上下界，并证明了不等式 胛) ( ：七+ 吣) - 2 七。 ( 4 ) 给出在树和单圈图范围内，2 控制数和连通2 控制数相等的充分必要 条件，并加以证明。 ( 5 ) 讨论给定边数和顶点数的图的一类极值问题。对于所有给定边数和顶 点数的图，我们将刻划出其所有顶点度数的口( 圭 口 i ，则存在非负整数m ， f f s l $ i + r n ( k + 1 ) s ， k ，从而八j v ) 是g 的七一独立集，与，是g 的极大 七独立集矛盾。对任意的点甜j ，矗0 ，一每 ) k ，故j 一埘不是g 的； - 控制集， 因此j 是g 的极小k 控制集。 在【2 9 中证明了计算相应的最小k - 独立数f ( g ) 是一个p 一完全问题，即使 对二部图这种特殊类型的图，计算( g ) 也是儿p - 完全问题，因此我们有必要估 计出t ( g ) 的上下界。 下面两个定理是用关于g 的最大七一度色的多项式来表示( g ) 的上下界： 定理2 2 5 设图g 的点数为n ，且最大k - 度a 。2 k ，则有 ( g ) 弓五n j ，且丘( g ) 2 萼式j 当且仅当g 的所有连通分支或者是路或者是 顶点数为? _ 0 ( m o d 2 n + 1 ) 的圈，也或者是其顶点数恰好为2 n + l 的任意图。 证明：设，是图g 的满足j ，i = ( g ) 的七一独立控制集，并令彳，b y ( g ) 一， 满足一中自g 蒽恰与1 中的一个点的距离小于等于女，b 中的点与1 中至少两个点 的距离小于等于k ，则矿( g ) = 八j 4 u b 。对于点x j ， 令 4 = i 爿，d ( u ，z ) i ，由a 的定义可知，若五：x 2 ，则有 n 如= 彩。故 对所有的点x 1 ，有 陋i & ， ( 1 ) 对x e i ，令风= u l u e b ，d ( u ，石) 七 ，有 图的控制参数和一共极值问题 段i 。一 4 i ， 由b 的定义可知，b 中的每一点至少属于两个最，所以有 结合( 2 ) 有 2 h 吲， ( 2 ) 丑f ( 趣一k i ) ， ( 3 ) 利用( 1 ) 和( 3 ) ，我们可得 以= m h + 俐 - k 。现在，u x ) ，一u y ) 在百中都是独立集。因此，g 中任意两个顶点至少有y ( 面一2 个共同的邻接点，并且这些与它们邻接的点在g 中是相互邻接的。 设v 是g 中具有最小度的顶点，s = “y ( g ) j 洲e ( g ) ，则s 是g 的一个 割集，令x ，y 在g s 的不同分支里，因此x ，y 至少有y ( 面一2 k 个相互邻 接的公共邻接点，并且这些邻接点都在s 中。设x c s 是所有像x 和y 这样的顶 点对的邻接点集的并集，则g s 中每一个顶点都被s 中至少k 个顶点控制。 下面我们证明s 中每一个顶点被s 中至少k 个顶点控制。假设v 1 是s 中一个 顶点且满足蟊( v 1 ) l ，矿( g ) 一 v 中每一个顶点都与 ( v ) 中的某个点邻接。因此( v ) 是g 的一个t o t a l 控制集， 一( g ) 蔓l ( v ) j - d ( v ) = 占( g ) ；同理，以( 石) 占( 面= n 一1 ( g ) ，故 n ( g ) + 一( 面n + 6 - a - i 。 定理2 4 8 设图g 和百都是点数”k + 1 的连通图，则 2 以( g ) + 以( 弧斋“1 n ( g ) “( 邵南a 证明：设图g 和百都是连通图，如果批m ( g ) 3 或者d i a m ( 西3 ，由定理 2 2 3 和定理2 2 1 1 ，结论显然成立，如果c 疗a m ( g ) 2 ，且d i a m ( g ) 2 ，则 以( g ) = 以( 舀) = 1 。 上面定理中的上下界在下面的图中是可以达到的，设任一整数t ， 2 t - = 生，把f 条不相交的长为k - 1 的路的一个端点分别与e 一。的f 个点连接， 疗十l 则这样得到的图满足即( g ) = 押，挥( g ) = ，以口) = 1 ，特别她，令f = 苦，则 t l 定理中的上界可以达到。对所有直径为2 且顶点数为n = 0 ，l ( m o d 4 ) 的自补图定理 中的下界都是可以到的。 如果放宽g 和召都是连通图这个条件，可以得到一个更大的上界：设g 是 点数”k + 1 的图，则2 以( g ) + h ( g ) n + 1 ，1 s “( g ) n ( g ) 。 定理2 4 9 t 2 ”设图g 和召都是点数 k + l 的连通图，则 当n - 2 ) 的连通七一控制集，令矿( g ) 一u ：。z ( o , ) - - x ，则存在g 的连 通女一控制集d ，满足d u ：，d j ，并且 l d l l d l + 2 七( s 一1 ) + 七例a ，- l 定理3 1 3 1对k 2 ，若g 和召都是连通图，则有 ( g ) ( 2 七+ 1 ) ( 百) ， 其中，( 召) 是连通图否中y ( 百) 能划分成的彼此不相交的连通七一控制集的最大 数目。 我们把( g ) 定义为连通图g 的连通k - d o m a t i c 数，当k = 1 时， t ( g ) = 霄( g ) 为连通图g 的连通d o m a t i c 数a 在 4 2 中证明了当k = l 时，有 儿( g ) 3 以( 百) a 3 2 图的连通七一控制集的上下界 现在我们来讨论用几个参数来表示的砟( g ) 的上下界，首先，下面的定理是 显然的： 图的控制参数和一类极值问题 定理3 2 1 设g = ( v ，e ) 是连通圈，日是g 的支撑子图，则有 成( g ) 戌( h ) 。 对任意点数”2 的树丁，考虑下面的过程：( 1 ) 删去丁的所有悬点，得到 树t “，由于树的悬点至少为两个，这个过程是可行的：( 2 ) 把( 1 ) 进行k 次， 得到树丁”，直到对菜一f ，l _ i k - 1 ，j 丁1 1 = 1 。用& ( t ) 表示被删去的点的 总数，对任意图g ，定义气( g ) = m a x t ( t ) 卜是g 的支撑树) ，则有下面的定理： 定理3 2 2 对任意点数为玎的连通图g ，有成( g ) + 矗( g ) = ”。 证明：令丁是g 的支撑树，满足以( 丁) = 缸( g ) ，则显然剩下的树，“是g 的 连通k 一控制图，从而成( g ) n - e , ( t ) = n 一& ( g ) 。 反之，令d 是具有厍( g ) 个点的g 的连通七一控制集，则g 【d 是g 的连通子 图。设是g d 的任一支撑树，我们在的基础上通过增加剩下的以一挥( g ) 个 点来构造g 的支撑树r ：连接剩下的每一点与d 中与其k 一邻接( 我们称 玑v 矿( g ) k 邻接，如果d ( u ，v ) 蔓k ，“v ，否则称j i - 独立) 的一个点，则显然 r 满足靠( 丁) n - r ：, ( g ) ，所以吼( g ) 岛( 丁) 一成( g ) 。 由上可知以( g ) + & ( g ) = m 成立a 推论3 2 1 对任意点数为栉的连通图g ，有k ( g ) 栉一色。 证明：令v 是g 中具有最大七一度的点，构造g 的支撑树如下：取g m v 】 的 任一支撑树瓦，连接矿( g ) 一氓 v 】中的每一点与z 中与其七一邻接的一点，则显然 有瓯( 丁) a ，由定理3 2 2 可得成( g ) ，z 一趣。 可以验证当g 中至多有一个度大于等于3 点时，等号成立。 推论3 2 2 对任意的连通图g ，确定蚱( g ) 是一个n p 一完全问题。 证明：文【4 3 中证明了对任意的连通图g ，确定毛( g ) 是一个p 一完全问题， 由矗( g ) 的定义可知，确定& ( g ) 也是p 一完全问题，所以由定理3 2 2 可得确定 大连理工大学硕士学位论文 戌( g ) 也是一个胛完全问题。 定理3 2 3 对任意的连通图g ，令d i a m ( g ) 表示g 的直径，则有 蠼( g ) d i a m ( g ) 一2 t + 1 。 证明：设d i a m ( g ) = ，令“，v 矿( g ) 满足d ( u ，v ) = z ，并设d 是图g 的任一 连通七一控制集，考虑下列三种情况 情况1 地v d 。由g d 】是连通图可知d l z + 1 。 情况2 “d ，v 仨d ( 或者“牟d ，v d ) 。由于v 必与d 中的一点k 相 邻，所以有l d l ，+ 1 一k 。 情况3 “茌d ，v 芒d a 此时显然有d i z + 1 2 k 。 由上面三种情况可知成( g ) d 缸m ( g ) 一2 k + i 。 可以看出，当k = 1 时，定理3 2 2 和定理3 2 3 即为 4 4 中相应的结论。 文 4 5 证明了：如果g 是连通图，则有以( g ) 3 i r ( g ) 一2 ，下面我们来推广 到k 1 的情况： 定理3 2 4 设g 为连通图，则有 郴，( z 后+ 孚) 吣h 七。 证明：设爿= h ，v 肼) 是图g 的满足i z l = 祝的七一无赘集，g 【x 的所有的 k 一连通部分( 这里我们说z 是g x 】的k - 连通部分，如果任取“，v 五，有 ( m ，v ) 女) 记作五，置，l s s 巩= 以。i 殳a x 】中有f 个i 一独立点v 】，v ， 0 蔓，j ，不妨设v l ，u 分别属于墨，五，其余j f 各部分每个至少包含两个 点，显然有2 ( s f ) + t i r 。，即s 堡：。我们考虑下面两种情况： 情况1 f = s ，即肖是k 一独立集，由定理2 3 2 可知，z 也是g 的k - 控制集。 令r = v iv e 帆h b ，g j = g 阮】，i = 1 ，m ，则g i 是g 的连通子图，且g 的任 一点属于某个g fa 由g 的连通性知，存在点而g i ，五与m u q 相邻，不失 图的控制参数和一类极值问题 m 一般性，设m g 2 。同理，存在点而g 1 u g 2 ，x 2 与儿u g , 相邻， i 殳y 2 g 3 我们得到集合 ，y l ，+ 一】) ，显然t 与某个v j ( 只与某个v j ) 之间至多需 k 1 个点使其连接，1 i m 一1 ，连接所有这些点，我们可以得到g 的一个连通 七一控制集，所以有虻( g ) 茎m + 2 k ( m 一1 ) = ( 2 k + 1 ) m 一2 k = ( 2 k + 1 ) i t k ( g ) 一2 k 。 情况2 r s ，由_ = | 是七一无赘集可知，对任意的点v x ，有蹦( 叶，丑) g 取点“；巩( v j ，x ) ，i = t + l ，m ，显然v fg 眦( v j ，z ) ，所以“，v i = t + l ，聊。令x x w u + 1 ，“。 ，则z 含的元素个数为2 以一t ，下面我们 来证明x 是g 的七控制集。 若x 是k 控制集，则显然z 也是k 控制集；若不是k 控制集，令v 是 矿一m 【x 】中的任一点，特别地v y 一【z 】，由定理2 2 9 可知，对某个v f x ， 有p n k ( x ，x ) n a v ) 。如果v v l ，v f ，则v 被v k - 控制，这与v 的选取矛 盾，所以v l v 。， 。由州( 葺，x ) m ( v ) ，我们可知，v 被“，七一控制， 所以由v 矿一m 【x 的任意性可知z 。也是七一控制集。下面我们在肖的基础上 构造一个连通图。 设g 彳】的所有尼- 连通部分为墨，墨，1 g - l s l ， 因此y ：= 圬。 4 32 一控制数等于连通2 一控制数的单圈图 在下面的5 个定理中，我们将要刻画扎= 疗的单圈图。在下面的5 个定理中， 如果一个顶点同时是s u p p d 和e x c l u s i v e ，我们仍把它看作e x c l u s i v e 。同时我们 规定，在( z ) 中顶点度数大于2 的顶点，如果是s u p p o r t ，则它和矿( g ) 一y ( c ) 中的邻接点只能是悬点。我们很容易看到，如果g 是一个圈，则，：= 成当且仅 当g 兰c 3 ，c 4 ，c 5 ，c 6 。 定理4 3 1 如果g 为一单圈图，圈c = u l u 2 u n u l ，n 7 ，x 为c 中所有顶 点度数为2 的点的集合。那么，儿= 戌当且仅当条件( a ) 和条件( b ) 中的任意 一个同时成立；或者条件( a ) 和条件( c ) 中的任意一个同时成立： ( a ) v 一 盖】中除去与( z ) 邻接的点，以及同时与悬点和麟c ，“s f v p 邻接 的点外，顶点度数至少为2 的点均是e x c l u s i v e 。 ( b ) 若( x ) 不连通，则它最多有3 个连通分支g l ，g 2 ，g 3 ，我们规定 l 矿( g 1 ) i i 矿( g 2 ) l l y ( g j ) 1 ，则矿( g 2 ) ，矿( g 3 ) 【矿( g 1 ) 一【矿( g 1 ) 】。 ( i ) 矿( g 3 ) o 。n v ( g o 中顶点度数大于2 的点都是s u p p d ，并且 i v ( g o i = 2 。 大连理工大学硕士学位论文 ( i i ) v ( g o = g ，y ( g ) g 。i 矿( g 2 ) l = 1 ， 矿( g 1 ) 】中顶点度数大于2 并且与y ( g 2 ) 邻接的点都是s u p 即玎。若矿( c ) 一 矿( g 1 ) 卜v ( g 2 ) 中与【矿( g 1 ) 邻接的顶点不是蹦c ，“5 f v e ， 矿( g 1 ) 】中另一个顶点度数大于2 的点也是s u p p o ， 且| 矿( g 1 ) i = 2 。若矿( c ) 一 矿( g 1 ) 卜矿( g 2 ) 中与 矿( g 1 ) 】邻接的顶点是“c m s f w ， 则l 矿( g 1 ) f 3 ，且l y ( q ) i 2 时，n z ( g o 】中另一个顶点度数大于2 的顶点是 s u p p o 或者盱c ，姗f v e ，v ( c oj = 3 时，n v ( g p 】中另一个顶点度数大于2 的顶 点是e x c l u s i v e 。 ( c ) 若盖) 是连通的，则陋i s 5 。 ( i ) 矿( c ) 一n i x 】中不存在与p 】邻接的点，l z i = 5 ，且( z ) 中顶点 度数大于2 的点都是e x c l u s i v e 。 ( i i ) 矿( c ) 一n i x 】中与( z ) 邻接的点中有一个是蹦c k r f v 8 ，另一个不是 e x c l u s i v e 时。c r ) 中度数大于2 的和此非蹦c ，“j f v 8 邻接的点必为s u p