（应用数学专业论文）笛卡尔乘积图的控制问题.pdf

a b s t r a c t i nt h i s 七h e s i sw ed i s c u s st h ed o m i n a t i o np 8 r a m e t e r so tu a r t e s l a np r o d u c t g r a p h s i tc o n s i s t so ff b u rc 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 b u n d a t i o n a lp r o p e r t i e so fg r a p h sa nd o m i n a t i o np a r 锄e t e r su s e dj no u rd i s c u s s i o n s t h e nw ed i s c u s st h er e l a t i o n s l l i pb e t w e e n ( t o t a l ) d o m i n a t i o nn u m b e ro fc a r t e s i a n p r o d u c tg r a p h sw i t hs o m ep a r a m e t e r so ft h ef a c t o r s ，w h i c hi n v o l v et h em a x i m u m d e g r e e ，( t o t a l ) 2 ) 一d o m i n a t i o nn u m b e ra n d ( t o t a l ) 2 一t u p l ed o m i n a t i o nn u m b e r i n t 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 nr e s u l t si nt h i s 七h e s i s ，a n dg i v es o m e p r o b l e m st ob es t u d i e df u r t h e r l e tg 口日d 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 dh l e t ( g ) ，7 2 ) ( g ) ， 1 ( 。2 ( g ) b et h em a x i m u md e g r e e ， 2 ) 一d o m i n a t i o nn u i r l b e ra n d2 一t u p l ed o m i n a t i o n n u i l l b e ro fg r a p hg r e s p e e t i v e l y i nt h es e c o n dc h a p t e r ，w ep r o v et h a t ，i nc e n a i n c o n d i t i d h s ，y ( g 口h ) 兰m 。z j i g 牿7 ( 日) ，j i 蔷，y ( g ) ) ，7 ( g 口h ) 2 ，y ( 2 1 ( g ) a n d 1 ( g 口日) 1 。2 ) ( g ) l e t 矗2 ( g ) ，一y f 。2 ( g ) b et h et o t a l 2 ) 一d o m i n a t i o nn u m b e ra n dt o t a l2 一t u p l e d o m i n a t i o nn u m b e ro fg r a p hgr e s p e c t i v e l mi nt h et h i r dc h 印t e r ，w eg i v et h a t ，i n c e r t a i nc o n d i t i o n s ，m ( g 口日) m o z j i g 持m ( 日) ，j i * 仉( g ) ) a n d m ( g 口日) 7 f x 2 ( g ) i nt h ee n do ft h e s er e s u l t s ，w eg i v es a m p l e st os h a w 七h a te 砌1r e s u l tg i v 郫a b e t t e re s t j m a t i o nt h a no t h e r s 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权。即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：盘 知一口年r 月? 。日 第一章基本概念和预备知识 图论( g r a h pt h e o r y ) 的历史最早可以追溯到二百多年之前，起源于游戏难题 的研究，最具代表性的是瑞士著名数学家l e u 】e f 于1 7 3 6 年提出的k 6 n j g s b e r g 七桥 问题，他的那篇论文被公认为图论历史上的第一篇论文。1 9 世纪中叶之后，出现了 大量著名的图论问题，如四色猜想和h a m i l t o n 问题。同时，出现了以图为工具去 解决其他领域中一些问题的成果。例如k i r c h h o f f ( 1 8 4 7 年) 和c a y l e y ( 1 8 5 7 年) 分 别用树的概念来研究电网络方程组和有机化合物的分子结构。“图( g r a p h ) ”这个 词第一次出现是在1 8 7 8 年的英国自然杂志中。1 9 3 6 年，匈牙利数学家d k 6 n j g 的 第一本图论专著有限图与无限图的理论标志着图论做为数学的一个新的分支 已经基本形成。进入2 0 世纪，特别是7 0 年代以后，大型电子计算机的出现使得大规 模问题的求解计算成为可能，图的理论及其在物理、化学、运筹学、计算机科学、 电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中 各方面应用的研究得到了空前的发展。 图的控制数最早起源于十八世纪五十年代的国际象棋问题，问题的目标是使 得棋盘上所有的格子或者被某些棋子占用或者可毗被这些棋子通过一次移动到 达。最著名的问题就是五皇后问题，即最少需要将几个皇后放入棋盘中就可以控 制棋盘上所有的格子。1 8 6 2 年d ej a e n i s h 得出最少需要五个皇后，这五个皇后的 摆法被称作五皇后问题 3 ，5 1 ，如图1 1 所示。设g = ( e e ) 是一个图，s 是v 的 子集，若y s 中每个点都和s 中至少一点相邻，则称s 为g 的一个控制集。最小 控制集的基数称为g 的控制数。通过对控制集加以限制，可衍生出许多其他类型 的控制数。对一般图而言，确定其控制数是n p - h a r d 问题。图的控制理论是图论 研究中的热门问题之一。1 9 9 8 年，在图的控制理论研究中处于领先地位的h a y n e s ， h e d e t i e m i 和s l a t e 教授主编出版了两本有关控制理论的专著 1 ，2 】f 、l n d a m e n t a l so f d o m i n a t i o ni ng r a p h s 和d o m i n a t i o ni ng r a p h s ：a d v a n c e ( 17 r o p i c s ，进一步推动 1 1 2 图论的基本概念 3 是特殊的有向图f 对称有向图) 。 用无序对z 来表示对称边( z ，) 和( ，z ) ，有序对e = ( 毛f ) e 称为有向边。z 称为边e 的起点，称为边e 的终点；而e = z 称为无向边，起点和终点统称为 边e 的端点。边的两端点称为相邻的( a d j a c e n t ) 。两端点相同的边称为环( 1 0 0 p ) 。无 环并且无平行边的图称为简单图( s i m p l eg r 印h 或d i g r a p h ) 。 设图g = ( v e ) ，y 中元素的个数u 和e 中元素的个数e ，即”= 矿i 和e = i 倒分别称为该图的顶点数或阶( o r d 玉) 和边数( s i z e ) 。 设图g 是无向图，z y ( g ) 的硕点度( v e r t e ) 【d e g r e e ) 定义为g 中与z 关联 的边的数目( 一条环要计算两次) ，记为d g ( z ) 。顶点度为d 的顶点称为d 度点( d _ d e g r e ev e r t “) 。零度点称为孤立点( i s o i a t e dv e r t e ) 【) 用( g ) 和6 ( g ) 分别表示g 的 最大( m a x i m u m ) 和最小( m i n i m u m ) 顶点度。即 ( g ) = m a x d g ( 。) z y ( g ) j ( g ) = ：m i n d g ( z ) i 。y ( g ) ) 设图d 是有向图，f y ( d ) 的顶点出度( v e r t o u t d e g r e e ) 定义为d 中以f 为 起点的有向边的数目，记为d 十( ) ：y ( d ) 的顶点入度( v e r t e x i n d e g r e e ) 定义 为d 中以口为终点的有向边的数目，记为d i ( y ) 。 图d ( 或g ) 中连接顶点z 和9 且长度( i e n 昏h ) 为七的链( c h a i n 或w a 的，记 为列链，是指顶点筑和边n 交错出现的序列 w = z l o ( = z ) n e l z 2 】m 2 8 哇瓢k ( = 可) 其中与边o o 都相邻的两顶点2 巧一，和正好是n q 的两个端点( 可能有。日一，= z o ) 。 z 和g 称为w 的端点( e 谢一v e r t i c e s ) ，其余顶点称为内部点( i n t e r n 越v e r t i c e s ) 。w 中 边的数目硐家为的长度。边互不相同的链称为迹( t r a i l ) 。内部点互不相同的迹称 为路f p a t h ) 。两端点相同的链( 迹、路) 称为闭( c 1 0 s e d ) 链( 迹、路) 。闭( 有向) 路又称 为( 有向) 圈( c y c l e ) 。 4 中国科学技术大学硕士学位论文 设g = ( y ( g ) ，e ( g ) ，妒g ) 和日= ( 矿( 日) ，e ( 何) ，妒h ) 是两个图，若y ( 日) y ( g ) ， e ( 日) e ( g ) ，并且妒h 是抛在e ( 日) 上的限制，即妒= 妒ge ( l ，则称日为g 的 子图( s u b g r 印h ) ，记为日g 。设y 7 是y ( g ) 的非空真子集，以为顶点集并 以g 中两端点均在中的边为边集合的子图称为g 的由y 7 导出的子图，简称导出 子图( i n d u c e ds u b g r a p h ) ，记为g ( 1 。导出子图g y 1 记为g y 7 。若y 7 = z ， 则简记g 一 。 为g z 。 设z ，y ，若g 中存在连接z 和的路，则称z 和是连通的( c o n n e c t e d ) 。 容易验证，y 中元素之间的连通关系是y 上的等价关系。这种等价关系将y 分成 等价类，u 。z 和属于同一类k 错z 和是连通的。子图g f ( 1 i u ) 称为g 的连通分支( c o n n e c t e dc o m p o n e n t ) ，u 称为g 的连通分支数( n u i n b e r o fc a m p o n e n t s ) ，记为u = w ( g ) 。若u ( g ) = 1 ，则称g 为连通图( c o n n e c t e d 掣a p h ) ： 反之为非连通图( d i s c o n n e c t e dg r 印h ) 。 设图g ；( ue ) ，顶点u y 的开邻点集( o p e ni l e i g h b 。r h o o d ) 记为( ? ( u ) = u y u ”e ，即顶点u 的所有邻点组成的集合。顶点”的闭邻点集( c 1 0 s e d n e i g l l b o r h 0 0 d ) 记为 b m = g ( ) u 。对于矿的子集s y ，它的开邻点集记 为g ( s ) = u 删g ( ”) ，闭邻点集记为g 旧= g ( s ) u s 。 设z ，y ( g ) ，图g 中从z 到g 最短路( s h o r t e s tp a t h ) 的长度称为z 和g 的距 离( d i s t 跏e ) ，记为d g ( z ，掣) 。g 的直径( d i 锄e t e r ) 记为d ( g ) = m n z d g ( z ，g ) 1 v z ，掣 y ( g ) ) 。如果z ，满足d g ( z ，g ) = d ( g ) ，称置g 为直径点。对y ( g ) 的两个子集x ，y ， 定义它们之间的距离为：d g ( x ，y ) = m i n 如( z ，) l v z x ，y ，。 设图g = ( v e ) ，s 是y 的子集，如果s 中任意两个顶点之间的距离至少是3 ， 则s 是图g 的m 砒伽口集。如果s 是图g 的顶点数最多的p n c f n 9 集，则称蚓为图g 的m 幽e n 9 数，记为p ( g ) a 设图g = ( v e ) ，如果顶点集y 可以划分为两个非空子集x 和y ，使得x 中 任何两项点之间无边相连并且y 中任何两顶点之间也无边相连，则称该图为2 部 分图( b i p a r t i t eg r a p h ) ， x ，y 称为2 部划分( b i p a r t i t i o n ) 。简单2 部分无向图( x u 1 0 中国科学技术大学硕士学位论文 士lz 2 i 3 i h 图11 0 图t 的2 一t u p l e 控制集 点。有i ( u ) n s i k 。满足如上要求的子集s 分别被称为控制集、全控制集、成对 控制集和一t 印k 全控制集。我们希望投入警卫的数量最少，以达到最优的效率， 于是就有了控制数、全控制数、成对控制数和女一“比控制数的概念。 如果读者希望迸一步了解以上四种控制参数，可分别参见13，8，12，36】口下面介绍本文中涉及的另外一种控制参数， - 控制数( 女) d o m i n a t i o nn u m b e r ) ，由d o m k e 等于1 9 9 1 年提出【3 m 定义1 3 5 对于个给定的实值函数，：y r ，的权重为u ( ，) = 。；y ，( ) ， 对于任意s y ，我们定义，( s ) = 。s ，( ”) 。设整数芝1 ，那么函数，：v 一 o ，1 一，被称为个 ) 一控制函数( ) 一d o m i n a t i n gf u n c t i 0 ) ，若有，( m ) t a 如果，是图g 中权重最小的函数，则称u ( ，) 为图g 的( 耐控制教记为1 ( g ) 。 若，( ( ) ) 2 ，则，被称为一个 女 - 全控制函数( t o t a l q d o m i n a t i n gf u n c t i o n ) a 如果，是图g 中权重最小的函数，则称u ( ，) 为图g 的 一全控刳数，记为矗 ( g ) 。 图1 1 1 给出了图g = p 3 口p 4 的一个最小 2 ) 一控制函数，如图所示，顶点旁边 的数字代表该顶点的取值( 8 或1 ) ，所以了( 马。只) = 6 ， 2 卜控制集的概念可 以由如何设置城市消防站的例子来形象的解释。将上面的图看成一座大型城市的 地图，每个顶点代表该城市的一个区，两个顶点之间的边代表车辆可以在很短时 1 3 控制参数介绍 g o 图1 1 1g = 局口角 0 o 问内由一个区直达另一个区，而两点不相连表示需要从其他的区绕道，从而需要 耗费较多的时间。现在考虑如何在该城市内优化设置消防站的问题。如果要求每 个区域在发生火灾之后，消防队能够在很短时间内到达该区，即每个区都有一个 消防站或者至少和一个消防站所在的区相连，则上述问题可以看成是求上图的一 个最小控制集。考虑到较大火灾的发生，要求危险发生后，在很短时间内至少有 两支消防队能够赶来同时灭火，这时，即要求每个区有一家消防站且至少与另一 消防站所在的区相连，或者该区附近有两个区拥有消防站。这时问题即变成求上 图的一个最小f2 一控制数。根据前面的讨论，至少要设置6 家消防站才能满足上述 要求。 1 4 中国科学技术大学硕士学位论文 图2 2 树t 的p d c t 哪集 定义2 1 6 设图g 和日是两个顶点不交的简单图。g 和h 的直积图( d t m c p 耐 u c ) g 日是一个简单图，其中y ( g h ) = y ( g ) v ( ) ，并且对。1 、，1 y ( g ) ，z 2 、掣2 y ( g ) ，有( 0 l ，。2 ) ，( 1 ，掣2 ) ) e ( g h ) 错扛i ，z 2 ) e ( g ) 且( y l 抛) e ( 日) 。 图2 3 直积图p 3x 马 v i z i n g 猜想对于直积图是不成立的， 3 9 】给出了个反例。因此人们转而研究 通过其他参数来划定直积图控制数的上下界。d o r b e c 4 0 】等给出了直积图控制数的 一个关于 ) 控制数的下界： 定理2 1 7 r d o 而e c 等。腭驯 7 ( g 日) m a x 1 2 ) ( g ) ，1 f 2 ( 日) 通过最大顶点度数和 ) 一控制数划定笛卡尔乘积图控制数下界的结果将在本 2 2 有关晟大顶点度数和 ) 一控制数的下界 1 7 g 图2 4 类圈图函( 1 ，4 ) 而( 2 1 ，1 ) 和( 2 1 2 ) 分别给出，( g 口叫和( 打) 和7 ( g 口日) ，y ( 聊。因此( 2 2 1 ) 给 出了一个更好的下界。 定理2 2 2 设g 并口日为没有孤立顶点的图，且满足( g ) i g 卜- 1 ，( h ) 1 日卜- 1 ， 则 7 ( g 口日) 三m o z ，y 2 ( g ) ，7 ( 2 ( 日) ( 2 2 2 ) 证明设s 为g 口日的一个最小控制集，在y ( g ) 上定义实值函数， ，( ) = m 打a 2 ，i “日n s ) ，札y ( g ) 这里，函数，的值域为z + 。下面我们证明，是图g 的一个 女 一控制函数。 记y ( 日) = ”1 ，啦，) ，因为日不含孤立顶点，所以n22 。对g 中的任意 顶点u ，有下列三种情形： 情形j ，( ) 2 ，此时，( “】) 2 显然成立； 情形粤，( ) = 1 ，此时“打包含s 中唯一一个顶点( “，仇) 。因为( ) l且(g)m(日)，则m ( g 口日) 2 ( g ) 下面我们给出一个有关最大顶点度数的笛卡尔乘积图全控制数下界，证明思想和第二章基本相同。 定理3 1 1 0 对任意不舍孤立顶点的图g 和日，有m ( g 口日) 2m n z j 汀 署b m ( 日) ，j 玎 舅b m ( g ) ) (31，) 证明记矿(日)=”1，w2，)。设s是g口日的一个最小全控制集。对g中的任意一个顶点n ，我们证明下面的不等式成立：i ( u u g 舢】u 日) n sim(h) 显然，“日中的顶点被m日ns中的点全控制。下面我们通过遍历u日中所有n个 形： 第四章结束语 最后，我们总结下本文的主要结果。 在第二章，我们研究了笛卡尔乘积图控制数的下界问题，得到了三个下界： ( 2 - 1 ) 不含孤立顶点的图g 和日，有下界m n z ( 五* 黯7 ( 日) ，五d x 3 0 中国科学技术大学硕士学位论文 【1 4 j r j n o w 8 k o w s k ia n ddf r a l i ，a s s o c i a t i v eg r a p hp r o d u c t sa d 七h e i ri n c i e p e d e n c e ， d o l i l i n a t 沁l la n d l o r i l 晤n u i n b e r s ，d i 8 c u s sm a t hg r a p ht h r y l1 6 ( 1 9 9 6 ) 。5 3 7 9 15 】f h a r a r y c u b i c a lf a p h sa n dc u b i c a ld i m e s b 珊c o m p u t e r s8 n dm 札h e m a t i c sw i t ha p _ p u c a t i o m ，1 5 ( 1 9 8 8 ) ，2 7 1 2 7 5 f 1 6 】a ，m e i ra n dj wm o o n ，r e l a t l o i l sb e t w e e np 们k i n g 蚰d 叫v e r i “g u m b e r so fat r e e p a c j m a t h 6 1 ( 1 9 7 5 ) 2 2 5 2 3 3 【l7 】s g r 吖i e ra n dm m o l i ”d o nd o m m a t i o nn u m b e r so fc 盯t 郫i a np r o d u c to fp a t h s d b c r e t e a p p l - m a t h 8 0 ( 1 9 9 7 ) ，2 4 7 - 2 5 0 f 18 】s k i a a ra n dn s e i 此e r ，d 哪i n a t i l l gc a r t e 8 j a np r o d u c t so fc y c l e 8 d i s c r e t ea p p i m a t h 5 9 ( 1 9 9 5 ) 1 2 9 - 1 3 6 f 1 9 】l i a i l gs u n ，ar 船u i to nv j z i n g 6c o n j e c t u r e d i g c r e t em a t h ，2 7 5 ( 2 0 0 4 ) ，3 6 3 - 3 6 6 犯o 】s g r a v i e r 肿l da k h d l a d i ，o nt h ed o m h l a t i o nn u l b e ro f 0 8 sp r o d u c to ff a p h s d b c r e t e m a 啦，1 4 5 ( 1 9 9 5 ) ，2 7 3 2 7 7 【2 1 】s k l w t b r 明d b z m 龃e k ，o na v i z i n g - l i k e c m 巧e c t u r e d rd i r e c tp r 。d u c to f g 。a p l l s d 缸c r e t e m a t h ，1 5 6 ( 1 9 9 6 ) ，2 4 3 - 2 4 6 1 2 2 lp d o r b e c ，s g r a 们e r ，s k l a t a ra n ds p a c 印8 n s o m er 鹤u l t so nt o t a ld o m i n a t i o ni n d i r 比tp r o d u c bo fg r a p h 8d i 8 c u 晒m a t hg 。印ht h 。y 12 6 ( 2 0 0 6 ) ，1 0 3 1 1 2 辑删d h 姐s o n ，p w a i l g ，an o t eo ne x t r e m a l t o t a ld o m i n a t i 0 e d g ec m i c a lg r a p h s ，u t i l i t 硒 m a t h 6 3 ( 2 0 0 3 ) ，8 9 - 9 6 【2 4 1t ，wh a y n e s ，m a h e n i n g l c 竹nd e rm e r w e ，d o m i n a t i o na n dt o t a ld o m i n a j o “ c r i t i c a lt r e 既w i t hr 档p e c tt or e h t l l mc o p i 哪e t 8 ，a r bc o m b i n 5 9 ( 2 0 0 1 ) 1 1 7 - 1 2 7 【2 5 】d p s u m 矾r ，pb l i t c h ，d o m m a t j o nc r i t i c a lg r 叩h ，j c o m b i n 毗o r i b lt h r y3 4 ( 1 9 8 3 ) 6 5 - 7 6 【2 6 】w g o d d a r d ，t w h a y n e w ，m am n n i n g ，l ，c v 帅d e rm e r w e ，t h ed i 帅e t e ro ft 0 训 d o m i n a t i o nv e r t e xc r i t i c 柚g r 印h s ，d i s c r e t em a t h e m a t j c s2 8 6 ( 2 0 0 4 ) ，2 5 5 - 2 6 1 3 2 中国科学技术大学硕士学位论文 佟9 jrn o w a l c o 粥k i