（应用数学专业论文）乘积图的覆盖pebbling数.pdf

摘要 本文主要讨论关于圈的覆盖p e b b l i n g 数的若干婀题 全文共分两章，第一章介绍一些图论中的基本概念和四种主要乘积图的定义 为后面要用到的一些名词和符号进行必要的说明 第二章是本文的主要结果首先第一节介绍p i b b 硒g 的背景和一些已知的 结果，并将定义一个图的新参数然后第二节将给出字典乘积图和某些强乘积图 的覆盖p e b b l i n g 致，即，y ( g0 日) = n ( ，y ( g ) + 3 ) 一2 6 ( n ) 一3 ，- f ( j 园g ) = m ( 7 ( g ) + 1 ) 一1 ，7 ( r ，园回= p ( a ) + 7 1 2 ”1 ，以及 假一馏：黧，霎臻釜 最后第三节对子直径的长度固定的图，给出了关键点与直径端点之同的关系 a b s t r a c t i nt h i sd i s s e r t a t i o n w 8m a i n l yd i g z u s st h ep r o b l e m s 蛆c o v o rp e b b l i n gg r a p h s i tc o n s i s t so ft w oc h a p t e r s i nc h a p t e r1 ，w ew i l li n t r o d u c es o m er e l e v a 础t e r m i n o l o g ya n db a c k g r o u n db y 触g s o m eb a s i cc o n c e p t si ng r a p ht h e o r ya n dt h ed e f i n i t i o no ff o u rm a i nk i n d s o fp r o d u c tg r a p h s c h a p t e r2c o n t a i n st h em a i nr e s u l t s i ns e c t i o n1w ew i l lr e v i e wt h eb a c k - g r o u n do f g r a p hp e b b l i n ga n d8 0 m ek n o w nr e s u l t s ，t h e nan e wp a r a m e t e r 妒o ( t l ，七) w i l lb ed e f i n e d i ns e c t i o n2w ew i l lo b t a i nt h ec o v e rp e b b u n gn u m b e ro ft h el e x - i c o g r a p h i cp r o d u c tg r a p h sa n ds o m es t r o n gp r o d u c tg r a p h b ，n a m e l y7 ( go 日) = 再“( g ) + 3 ) 一筋( 日) 一3 ，7 ( j o 园g ) = m h ( g ) + 1 ) 一l ，y ( 翰区g ) = 烈固+ 靠2 m + 1 ， a n d ， 7 c 囟回= 妻回g ) + + 。3 n 。- t w 列2 柏, ，毗w h 匝e am m 缸i s 。e 酣, m n ， f i n a l l y , s e c t i o n3a d d r e s s e 目t h er e l s t i o n s h i pb e h 煳k e yv e r t e x e 8a n de n d so f d i a m e t e r sf o r 觚a r b i t r a r yg r a p hw i t hf i x e dd i a m e t e r ， 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：弛轻 1 矾订年岁月f z 日 第一章图论中的概念介绍 图论的产生和发展历经了二百多年的历史，大体上可以划分为三个阶段：从 1 7 3 6 年到1 9 世纪中叶的萌芽阶段，从1 9 世纪中叶到1 9 3 6 年的基本形成阶段和 1 9 3 6 年以后的快速发展阶段进入7 0 年代以后，由于大型电子计算机的出现。使 大规模问题的求解成为可能图的理论及其在物理、化学、运筹学、计算机科学、 电子学、信息论、控制论、网络理论、社会科学及经济管理几乎所有学科领域中各 方面应用的研究都得到“爆炸性发展” 在现实世界中，用图形来描述某些事物之问具有某种特定关系常常感到特别 方便例如用工艺流程图来描述某项工程中各工序之间的先后关系，用原理电路图 来描述某电器内各元件导线连接关系，等等图形中的点表示对象，两点之间的连 线表示某种特定的关系由于我们感兴趣的是两对象之间是否有某种特定关系，所 以图形中两点间连接与否甚为重要，而连接线的曲直长短则无关重要由此数学抽 象产生了图的概念【2 0 1 1 1 基本概念 所谓无向图g 是指一个有序三元组( y ( g ) ，e ( q ，妒台) ，其中y ( g ) 是非空的 顶点集，e ( c ) 是不与v ( a ) 相交的边集，而犁i 。是关联函数，它使g 中每条边对 应于g 的无序点对( 不必相异) 若e 是一条边，而u 和”是使得妒b ( e ) = 伽的 顶点，则称e 连接t 和口，顶点和 称为e 的端点【1 】 此外，i 矿( g ) j 称为图g 的顶点数或阶数，而i e ( g ) l 称为图g 的边数边与 它的两个端点称为关联的，与同一条边关联的两端点或者与同一个顶点关联的两 条边称为相邻的两端点相同的边称为环有两个公共端点的两条边称为平行边 或者重边无环并且无平行边的图称为简单图 任何不同两项点之间都有边相连的简单无向图称为完全图，在同构意义下，t ， 阶完全图是唯一的，记为凰若无环图的顶点集可以划分为两个非空子集x 和 l 2 中国科学技术大学硕士学位论文 l ，使得x 中任何两顶点之间无边相连并且y 中任何两顶点之间也无边相连，则 称改图为2 部分图，x ，y 称为2 部划分如果x 中每个顶点与y 中每个顶 点之间均有边相连，则简单2 部分无向图uy e ) 称为完全2 部分图如果 i x i = l i f t ，i y i = n ，那么在同构意义下，完全2 部分图是唯一的，记为k i ，。特别 地，凰。一1 称为星图 设g 是无向图，则g 中顶点z 的顶点度定义为g 中与z 关联的边的数 日，记为d 口( ) g 的最大顶点度和最小顶点度分别用( g ) 和6 ( v ) 表示即 ( g ) = m a x d o ( 功：v z v c g ) ，6 ( o ) = m i d o ( 卫) ：v 善y ( g ) 图g 中连接顶点z 和y 且长度为k 的链w ，是指顶点和边哪交错出现 的序列w = x t o ( = 习以。魏，啦。ef ) ，其中与边相邻的两顶点铂一，和 戤，是的两个端点z 和y 称为w 的端点，其余的顶点称为内部点w 中边 的数目毒l ：为的长度内部点互不掘同的链称为路两端点相同的路称为f j l 路或者圈在同构意义下，长度为仇的路和阶数为n 的圈均是唯一的，分别记为 p m 和g 需要注意的是扁。的阶数为m + 1 ，即j f - m + 1 ； 图g 的线图l ( g ) 是以e ( 研为顶点集的图，并且对于e ( g ) 中任意的两个 元素岛和勺，自和勺在l ( g ) 中相邻当且仅当白和勺在g 中相邻 设z ，为圈g 中顶点，着g 中存在连接2 和y 的路，则称z 和y 是连 通的若g 中任意两个顶点都是连通的，则称g 为连通图设z ，y 为g 中顶 点，图g 中所有从z 到y 的路的最短长度称为从z 到y 的距离，记为d i s t ( x ，f ) 瑚x d i 8 t ( 为y ) ：v z ，口y ( g ) ) 称为g 的直径，记为d i m ( g ) 如不加特殊说明， 本文所涉及的图均为连通图 1 2 两个例子 下面我们看两个例子：p e t e r s e n 图p 和三维立方体图铲 1 3 四种主要的乘积圈 3 容易看出对于p e t e m e n 图p ，有 i y ( p ) i = 1 0 ，l e ( p ) f = 1 5 ，( p ) = 6 ( p ) = 3 ，d i a m ( p ) = 2 而对于三维立方体图驴，则有 i y ( 驴) i - 8 ，f e ( 驴) i = 1 2 ，( 驴) = 6 ( 驴) = 3 ，出眦( q 3 ) = 3 1 2 2 三维立方体图 1 3 四种主要的乘积图 在实际网络设计当中，为了得到更大的图，通常会使用由几个较小的图的乘 积来得到一个较大的图这种构图方法这些乘积构图法中四种最主要的乘积分别 是：笛卡儿乘积( c a r t e s i a np r o d u c t ) ，直接乘积( c a t e g o r i c a lp r o d u c t ) ，字典乘积 ( l e x i c o g r a p h i c p r o d u c t ) 和强乘积( s t r o n g p r o d u c t , ) 4 中国科学技术大学硕士学位论文 图1 2 三维立方体图驴 下面我们来介绍一下这四种不同的乘积图的定义( 在【1 2 】中有对乘积图的各 个方面的介绍) 更直观地，从图1 3 给出的2 阶完全图j 岛与长为2 的路b 的 四种乘积的例子可以明显看出它们的不同 尔 1 3 1 笛卡咒乘积图 纭 笛卡苑乘积臣g = g i o g s 图g 的点集是图g i 的点集y ( g 1 ) 和图g 2 的点 集v ( a 2 ) 的笛卡毙乘积v ( a 1 ) y ( g ；) ，图g 中两点札= ( l ，抛) 和 = h ，现) 在图g 中相邻，当且仅当t l = 。l 并且坳和地相邻，或者“1 和”i 相邻并且 地= t 1 2 ，其中i t , 1 ， 0 1 v ( c 1 ) ，坳，砚y ( ( b ) 1 3 2 直接乘积图 直接乘积图g = g l g 2 图g 的点集是图g l 的点集v ( a 1 ) 和图g 2 的点集 v ( a 2 ) 的笛卡儿乘积v ( a 1 ) x v ( a 2 ) ，图g 中两点让= ( u 1 ，u s ) 和口= ( t 1 1 ，地) 在图 g 中相邻，当且仅当乜1 和 u 1 相邻并且仳2 和地相邻，其中让1 ，i r a v ( a 1 ) ，t 2 ，吨 y ( 岛) 1 3 3 字典乘积图 字典乘积图g = 国o g 2 图g 的点集是图g 1 的点集v ( a 1 ) 和图g 2 的点 1 3 四种主要的乘积图 5 集v ( g 2 ) 的笛卡儿乘积y ( g 1 ) v ( g 2 ) ，图g 中两点缸= ( u l ，地) 和口一0 1 ，也) 在图g 中相邻，当且仅当b l = 研并且t 2 和地相邻，或者t l 和铆相邻，其中 t l ，班y ( ( 五) ，t 2 ，地y ( g 2 ) 1 3 4 强乘积图 强乘积图g = g i 囟( b 圈g 的点集是图g 1 的点集v ( g 1 ) 和图g 2 的点集 v ( g 2 ) 的笛卡几乘积y ( g 1 ) y ( g 2 ) ，图g 中两点乱= ( u “t 2 ) 和可= ( 口l ，t 】2 ) 在图 g 中相邻，当且仅当“1 = 砚并且铆和吨相邻，或者l 和饥相邻并且坳= 也， 或者t l 和t ，1 相邻并且t 2 和地相邻，其中l ，地v ( c 1 ) ，t 1 2 ，地v ( g 2 ) k 2 凸b 图1 3 四种鲍和忍的乘积图 园马 搿网辫田 第二章 图的覆盖p e b b l i n g 数 2 1 引言 p e b b l i n g 这一概念首先是由l a g a r i a s 和s a k s 作为试图解决e r d 6 s 在数论中 的一个猜想的工具而提出的后来c h u n g 成功地用p e b b l i n g 证明了g r d 6 s 的猜 想并得到了一些关于图的p e b b l i n g 数的结果1 2 】从此，人们正式开始了对图的 p e b b l i n g 数的研究 最近几年，许多人对图的p e b b l i n g 数傲了大量的研究工作，得到了很多的结 果h u r l b e r t 就是其中之一，他还在1 9 9 9 年【9 】和2 0 0 5 年【1 0 】分别写了一篇综 述，介绍了当时关于p e b b l i n g 的研究进展下面我们先来介绍一下图的p e b b l i n g 数的定义和一些已知的结论 2 1 1 图的p e b b l i n g 数 给定一个图g ，在g 的每个顶点上放置一定数目的p e b b l e s ( 可以在某些顶 点一个都不放) ，则在图g 上傲一次p e b b l i n g 移动是指从一个顶点上取走两个 p e b b l e s 并在它的一个相邻顶点上加上一个p e b b l e 图g 的p e b b l i n g 数是指无论 顶点上的p e b b l e s 如何分布，都能够使得经过一系列的p e b b l i n g 移动，最终在g 的任取的某个目标顶点上至少有一个p e b b l e 的最小的p e b b l e s 个数，记为7 r ( g ) 设埘为图g 中顶点，如果我们在g 中除目标顶点“之外的每个顶点上 都仅仅放置一个p e b b l e ，那么就没有办法经过p e b b l i n g 移动使得u 上至少有一 个p e b b l e 另外，如果从埘到t 的距离为d ，而我们只在t ，上放置2 d 一1 个 p e b b l e s ，那么目标顶点也不可能经过p e b b l i n g 移动得到至少一个p e b b l e 于 是，有丌( g ) m 麟 | 刎，2 d l a m ( 。) ) 满足丌( g ) ；l g i 的一类图包括n 阶完全图j 毛，d 维立方体图【2 】，完全 二部分图，。【3 j ，等等，而r ，【2 1 ，p e t e r s e n 图p1 3 ，偶圈c k1 1 4 ，完 全图玩的线图k 【1 8 j 等另外一类图满足丌( g ) = 2 血m 此外，奇圈q “l 6 2 1 引言 7 【1 4 】和树【1 3 】则代表了其p e b b l i n g 数不等于这两个下界中任何一个的一类图 对于笛卡尔乘积图的p e b b l i n g 数，有一个重要的猜想 猜想2 1 1 1r ( 托胁) r ( g l 口g 2 ) 丌( g 1 ) 7 r ( 6 k ) 目前，g r a h a m 猜想在树与树的乘积【1 3 】，圈与圈的乘积【7 ，8 ，1 4 】，完全二部 分图与完全二部分图的乘积【6 | 等情形下均得到了验证 下面我们来介绍一下图的覆盖p e b b l i n g 数的定义和一些已知的结果 2 1 2 图的覆盖p e b b l i n g 数 若给定一个图g ，在g 的每个顶点上放置一定数目的p e b b l e s ( 可以在某些 顶点一个都不放) ，则图g 的覆盖p e b b l i n g 数是指无论顶点上的p e b b l e s 如何分 布，都能够使得经过一系列的p e b b l i n g 移动，最终在g 的每个顶点上都至少有一 个p e b b l e 的最小的p e b b l e s 个数，记为，y ( g ) 更一般地，给定权函数0 , 3 ，使得对于g 的任意一个顶点u ，u ( u ) 都对应于一 个整数如果对于g 的任意一个顶点u 都有u ( “) 1 ，则称权函数，是正的图 的加权覆盖p e b b l i n g 数是指无论顶点上的p e b b l e s 如何分布都能够使得经过一 系列的p e b b l i n g 移动，最终在g 的任意一个顶点“上都有u ( u ) 个p e b b l e s 的最 小的p e b b l e s 个数，记为( g ) 【4 】 设t 为g 中顶点，定义 5 ( ) = 2 赫， s e v ( o ) 并令 s ( g ) 5 鼢s ( t t ) 同样地，若给定了权函数“，。则 钆( ：u 函2 d i g 扣神 8 中国科学技术大学硕士学位论文 而 钆( g ) 2 崖轧( t e y - “j 定理2 1 2 1 设g 为简单图，u 为正的权函数，则( g ) = 轧( g ) 这一定理开始是在立方体图的情形下得到了验证【1 1 】，后来【1 6 ，1 9 l 中又 考虑了其他的情形，最后该定理分别在【1 5 】和【1 7 1 中独立地得到了证明由定 理2 1 2 1 ，很容易得到一个关于笛卡尔乘积图的加权覆盖p e b b l i n g 数的结果 1 如 定理2 1 2 2 设g 1 ，g 2 为简单图，q 为正的权函数，则 o t 4 1 , , c 臼- , o 柚；( 鳓魄c 劬， 茹甾4 k 谚= 枣强啊扩 基辛囔寺亍鼠d 乳钥i 磕顶点c ；，功， d p ，c 嵋，功；：m 慨f 功 在下面第二节中，我们将依据定理2 1 2 1 来求字典乘积图和强乘积图的覆盖 p e b b l i n g 数我们之所以不考虑直接乘积图，是因为两个连通图的直接乘积会产生 不连通的图比如第一章的图1 3 中的鲍恳，娲和尼均为连通图，而k 2 b 却并不连通 由于根据定理2 1 2 1 ，求，y ( g ) 实际上就是找图g 中满足s ( ) = s ( g ) 的点 因此，计算一个图g 的覆盖p e b b l i n g 数的问题实际上就转化为了寻找图g 中满 足条件s ) = s ( g ) 的点本文中，我们按照【1 6 】中的定义，称这样的点为关键点 为了后面的证明易于表述，下面我们再引入一个新的定义 定义2 1 2 3 令g 为一个简单无向图，u 为g 中一个顶点，定义q o a ( u ，的 为图g 中所有到顶点“的距离为k 的顶点的个数，即 p a ( u ，k ) = i z l z y ( g ) ，t i i s t ( z ，h ) = k l ， 其中1 k d i 锄( g ) 若k = 1 ，则简记为妒g ( “) 显然，对于图g 中任意一个顶点有 d i a m ( o )魄 ( ) = i 斫 ( 2 1 ) 2 2 乘积图的覆盖p e b b l i n g 数 9 另外，根据定理2 1 2 1 和定义2 1 2 3 ，我们可以得到 ( 2 2 ) 7 ( g ) 2 m a x “】 8 ( u ) ) ( 2 3 ) 2 2 乘积图的覆盖p e b b l i n g 数 2 2 1 字典乘积图的覆盖p e b b l i n g 数 为便于主要结果的证明，我们首先来证明个引理 引理2 2 1 1 令g ，日为两个简单无向图，则对于g o 口中任意给定的两个 顶点0 ，! ，) 和( t ，”) ，有 酬刚m m 卜k 毗娶b 证明我们分别考虑下面四种情形 情形l ：当z = u ，扩= 口时，显然d 诎( ( 写，f ) ，0 ，口) ) = 0 情形2 ：当卫= ，d i s t ( y ，口) = 1 时，因为! ，和口在口中相邻，根据字典乘积 图的定义，此时d i 8 t ( p ，) ，( u ，t ，) ) = 1 ，即0 ，暑，) 和( u ，口) 在g o 日中相邻 情形3 ：当z = u ，d i 8 t ( 玑t ，) 2 时，因为! ，和口在日中不相邻，根据字 典乘积图的定义，( 茁，) 和( ，口) 在go 日中不相邻，即d 龇( 0 ，耖) ，( 让，t ，) ) 2 ； 另一方面，我们取g 中与2 相邻的顶点奶则由字典乘积图的定义，) 既和 ，! ，) 耜邻，又和( u ，相邻这说明在图go 日中存在一条连接点( z ，) 和点 中国科学技术大学硕士学位论文 “，口) 的长为2 的路，而两点之间距离的定义是连接两点的最短路的长度，因此， d m ( ( 毛) ，( t ，口) ) 2 结合这两个不等式，我们碍到d i s t ( ( z ，) ，( u ， ) ) = 2 情形4 ：当z 时，首先我们证明d i b t ( ( z ，) ，( u ，t ，) ) 出础p ，q ) 设 d i s t ( 仁，f ) ，( 让，口) ) = n ，则在图go 日中存在一条连接( 为y ) 和( u ，t ，) 的长为 n 的路，记为 r = ( ( 毛曲= ( 知，珈) ，( z l ，1 ) ，( 互，1 ，一1 ) ，( ，) = ( “，口) ) 根据字典乘积图的定义，图go 日中两点，执) 和( x d - i - 1 ，鼬，1 ) 相邻，当且 仅当和坼l 在图g 中相邻或者弘和鼽+ 1 在图日中相邻并且= 2 件l ，其 中i = 0 ，1 ，”一1 由此可知点序列( x 0 ，岳l ，) 具有礼和2 件1 在图g 中相邻或者= z d - , i - 1 这样的性质，其中f = o ，l ，n 1 因此我们可以在点序列( 卸，旬，) 中 找到一条连接点z = 知和t = 长为的路，记为 足= 0 = ，。，“= “) ， 其中序列中连续的两点在图g 中相邻，序列( 伽，m ，m ) 是序列( 1 ，2 ，呐 的一个子序列于是我们有嚣又由两点之闯距离豹定义，是d i s t 0 ，因 此，我们得到d i 8 t ( ( z ，| ，) ，( t ，口) ) ( 饿( z ，砷 下面我们来证明a i s t ( ( = ，f ) ，( 牡，t ，) ) d i 8 t 扛，) 设d i 8 t ) = f 则在图g 中存在一条连接z 和“的长为2 的路，记为 只一0 = 轴，2 l ，盈一l ，却= 由字典乘积图的定义可知，们和( z 件1 ，们在图go 日中相邻，其中i = 0 ，1 ，l 一1 这说明在图go 日中存在一条连接( 铷，) 和( z l - l ，暑，) 的长为 七一1 的路，又由于汹一l ，f ) 和国，口) 在图g o 日中也相邻，于是我们找到了一条 连接( 士，) = ( 知，) 和( 让，t ，) = ，口) 的长为f 的路，记为 毋= ( ( z ，= ( 蜘，鲈) ，0 l ，f ) ，( 研一l ，f ) ，( 却，铆) = ( 口，嘞 2 2 乘积图的覆盖p e b b l i n g 教 1 1 因此，d i 8 t ( ( 霸，) ，( “， ) ) f ，也即d i 8 t ( 0 ，暑，) ，“，口) ) 出s 乞扛，u ) 综合这两个不等式，可得d j 8 t ( “| ，) ，( “，) ) = d i 8 t ( z ，u ) 口 引理2 2 1 2 令g ，h 为两个简单无向图，其中的阶数为”，则对于g o h 中任意给定的顶点( “，”) ， s ( “，t ，) ) = n ( s ) - 4 - 3 ) 一2 蛳( 口) 一3 证明首先根据引理2 2 1 1 ，对于g o h 中的任意两个顶点( 尘，f ) ，( “，口) ，有 d 1 酣( ( 茹，f ) ，( 钍，口) ) = 0 ，着= 让，| ，= 口， 1 ，若d j 8 t 0 ，口) = l ，z = 或者d i 8 t ( $ ，) = 1 ， 2 ， 若d i s t 白，口) 2 ，z = 让 或者d i s t ( = ，= 2 ， d i s t 缸，钍) ，其他情况 然后我们固定( u ，t ，) ，则由定义2 1 2 3 ，有 l 1 ， 七= 0 ， 妒g o 日( ( 训) ，) ： n 恤( ”) + 船( ”) ， k - - - - l , in ( 2 ) - 4 - ( n 一1 一似扣) ) ，k = 2 ， i 竹( ，) ，3 k d i a m c c ) 最后，根据本章第一节的等式( 2 2 ) ，可得 d i a m s ( ( ，口) ) = 灿日( ( ”) ，后) 2 = 1 + 加o o ( u ) + 恤和) ) 2 + ( n 扣，2 ) + ( 竹一l 一妒盯0 ) ) ) 2 2 d j a m ( g ) + n 似m ，动2 = ，l ( s ( ) + 3 ) 一2 妒日( t ，) 一3 中国科学技术大学硕士学位论文 定理2 2 1 3 令g ，日为两个简单无向图，其中日的阶数为n ，则 7 ( g o 哪= n h ( g ) + 3 ) 一2 6 ( h ) 一3 证明根据本章第一节的等式( 2 3 ) ，我们有 7 ( g 。娜= 。嘏紧y ( 研 s ( ( u ，。) ) ) 于是由引理2 2 1 2 ，可得 ，y ( g o 叨= 一，j 要瞰 n ( s ( t ) + 3 ) 一2 妒日p ) 一3 ) 一 蚝y ( g ) ，, e v ( h 3 。 n l n a x ，州+ 3 ) 一，。恤 ) 一3 = 仃( ，y ( g ) + 3 ) 一2 6 ( n ) 一3 d 另一方面，如果伽是g 的个关键点，并且t ，d 是日的一个最小度点，则 a ( ( u o ，如) ) = n ( ，y ( g ) + 3 ) 一2 j ( h ) 一3 ，于是有7 ( g o h ) t l ( ，y ( g ) + 3 ) 一2 6 ( n ) 一3 综上可得7 ( g o 日) = n ( ，y ( g ) + 3 ) 一2 6 ( h ) 一3 证毕 口 注记定理2 2 1 3 告诉我们顶点( “，口) 是goh 的一个关键点当且仅当t 是g 的一个关键点同时钌是目的一个最小度点这也说明，跟笛卡尔乘积的情 形不同的是，字典乘积图goh 的覆盖p e b b l i n g 数只取决于g 的覆盖p e b b l i n g 数和日的最小点度，而跟日的覆盖p e b b l i n g 数没有任何关系 2 2 2 强乘积图的覆盖p e b b l i n g 数 对于任意选取的两个因子图的强乘积，其覆盖p e b b l i n g 数的计算公式并不像 笛卡尔乘积或者字典乘积那样容易得到因此我们固定其中一个因子，给出一些 这样的强乘积的覆盖p e b b l i n g 的计算公式 下面先证明一个引理，为后面定理的证明做准备 2 2 乘积图的覆盖p e b b l i n g 教 引理2 2 2 1 令g 。日为两个简单无向图，财对于g 囟日中任意的两个顶点 0 ，掣) ，“t ，) ，有 d i 8 t c ( x ，) ，( t ， ) ) = m x 出酊0 ，“) ，西础0 ，口) ) 证明首先，我们证明强乘积圈中，任何两点的距离，都不小于两个因子图分 剔对应的两点的距离中的较大值，即对于g 园日中任意的两个顶点( z ，耖) ，( 1 ，口) ， d i 贰( ( 。，暑，) ，( 口，副) ) 丑 区 d i s t ( $ ，t ) ，m 8 t ( 掣，口) ) 设d 斌( ( z ，! ，) ，( t ，t ，) ) = n ，则在图g 区日中存在一条连接点( 毛! ，) 和心冒) 的长为n 的路。记为 尸忭= ( ( $ ，f ) = ( x o ，珈) ，忙l ，讥) ，( 一1 ，枷一1 ) ，( ，) ；( ，口) ) 根据强乘积图的定义，图g 园日中两点向，鼽) 和( 铂1 ，摒1 ) 相邻，当且仅 当z i 和蜀【+ l 相邻并且鼽撕1 或者奶和1 相邻并且弘和撕1 相邻或者 4 = 戤+ l 并且弘和鼬1 相邻 因此我们可以知道点序列扛= 知，茁1 ，- 1 ，= 具有锄= 坼l 或 者如和霸降l 相邻这样的性质，其中i = 1 ，2 ，f l 一1 于是，我们可以在点序列 ( x o , z 1 ，) 中找到一条连接点z = 知和点u = 的长为j 的路，记为 最= 0 = ， = ， 其中序列中连续的两点在图g 中相邻，序列( 伽，n l ，m ) 是序列( 1 ，2 ，n ) 的一个子序列由此易知n z ，又由两点之间距离的定义，有z d i s t ( $ ，t ) ，于是 我们得到d j s t ( 0 ，) ，( “，口) ) d i 8 t ( z ， 同理，我们可以通过点序列( 妒= 珈，饥，鲰= 可) 在日中找到一条连接 暑，= 珈和鼽= 口的长不大于n 的路，从而得到d 斌( ( z ，y ) ，( 口) ) d i s t ( f ，) 这样，我们结合这两个不等式，就有 d i s t ( ( 茁，们，( q ，t o ) m a x d i b t ( 毛，d i b t ( ! ，) 1 4中国年莘学技术大学硕士学位论文 下面我们来证明 d i 8 t ( ( 。，口) ，( u ， ) ) m x d i 8 t ( 善，t ) ，d i 8 t ( ! ， ) 设d i s c = ，t ) = m ，如酊( f ，t ，) = n ，并且m n 根据距离的定义，我们可以在 圈g 中找到一条连接z 和u 的长为m 的路，记为 昂= 扛= x o ，z 1 ，而，卜l ，= 而在图日中我们可以找到一条连接和口的长为n 的路，记为 r = ( y = 跏，托，弘，一l ，；t ，) 在图g 囟日中考虑点对，珧) 和( 缸 l ，l “1 ) ，以及点对( 。，鲫) 和( ，珊+ 1 ) ， 其中 = 1 ，2 ，m 一1 ，j = m ，m + 1 ，n 一1 根据强乘积图的定义，由于 点缸和点雄 1 在图g 中相邻，点挑和点“l 在图日中相邻，敢点( ，乳) 和慨+ 1 ，执+ 1 ) 在图g 园日中相邻，其中i = 1 ，2 ，仇一1 又因为点协和 点纷+ l ：盔l l th 中相邻，故点( ，珊) 和( 丑m ，弘件1 ) 在图g 园h 中也相邻，其中 j = m ，m + 1 ，n 1 通过这些相邻点对，我们可以在图g 园日中构造一个首尾顶点分别是( 霉，) 和( t ，口) 的点序列如下： ( 0 ，功= ( 知，妫，缸i ，飒) ，( 锄，蜘；) ，弘衅1 ) ，( 而。，铷) = ( ) 记此点序列为魏，显然吼是图g 囟h 中一条连接点( $ ，暑，) = ( 跏，珈) 和点 ( 口) = ( , x m ，) 的长为n 的路， 因此，由两点之间距离的定义，有d j s t ( ( z ，3 ，) ，( u ，口) ) n ，也即 d i s t ( ( z ，们，( ，t 哆) 眦 d i 8 t ( z ，t ) ，d i 8 t ( ! ，锄) 综上所述，可得 d i 8 t ( ( z ，f ) ， ，口) ) = = n l a x d i b t 0 ，u ) ，d i 8 t 0 ，口) ) 2 2 乘积图的覆盖p e b b l i n g 数 1 5 下面我们首先考虑m 阶完全图。和任意图g 的强乘积的情形 定理2 2 2 2 令g 为简单无向图则 ，r ( k 嘉囟g ) = m ( ，y ( g ) + 1 ) 一1 证明根据引理2 2 2 1 ，对于图k m 因g 中的任意一个顶点( 珏，口) 有 酏咄卟 m j 一。，：竺 【m 似( 功， 2 詹d i 锄( g ) 然后由本章第一节的等式( 2 2 ) ，可得 d i e m ( o ) s ( ( 口，) = 附( ( 刚) ，七) 2 d i m n ( g ) = l + ( m ( - t - r n - - 1 ) 2 + f ，i o a ( v ，) 2 d i s m ( 。) = m 一1 + m 似( 仉七) 2 最后，根据本章第一节的等式( 2 3 ) ，有 7 ( 因回=畦y ( z 搿。y s ( ( 让，训) 州。m s , xy m - 1 + 警吣h ) =m k 偿r i m ( g ) 寸1 ) 一 = 仇荆+ ，) 一 = m ( 7 ( g ) + 1 ) 一1 口 1 6 中国科学技术大学硕士学位论文 口 注记定理2 2 2 2 说明对于图k 。囟g 中的任意一个顶点( t ，) ，点口) 是图墨。园g 的一个关键点当且仅当口是图g 的一个关键点 下面我们考虑顶点个数为m 的圈c k 和任意简单无向图g 的强乘积的情形， 其中【m 2 j d i d ( c ) 为了能够确定强乘积图c m 园g 的关键点，我们引入一 个关于图g 的新参数，定义如下 定义2 223 令g 为简单无向图，定义 卵，= 黝 管( - 黯- 3 脚谚) “g ) 2 嚣橘 薹) 州动堙 图g 中任意满足 一( 2 k 一3 ) ( 缸，七) 2 k = c ( g ) 的顶点口记为图g 的一 个弘顶点 脚 定理2 2 2 4 令g 为简单无向图，i g i = l r l , ，c m 为顶点个数为仇的圈如果 【m 2 j d i 岫( g ) ，则 7 c 囟回= 夏g g ，) + + n 3 n 。, 2 _ “倒1 2 , 帕，萎：凳罢萋： 证明( 若m 为偶数，令m = 2 p ，其中p d i 眦( g ) 根据引理2 2 2 1 ，对 于图c 知囟g 中任意一个顶点( 让，口) ，有 酬n 眵。， 2 2 乘积图的覆盖p e b b l i n g 数 然后由本章第一节的等式( 2 1 ) 和( 2 2 ) ，可得 8 ( ( 让，口) ) = 瞰( ( 1 ) ，七) 2 k k = 0 d i a m ( c o = l + ( ( 2 七一1 ) 妒a ( 1 ，砷+ 2 妒g ( 1 ， ) ) 2 k k f f i l , - - 0 p - 1 + f2 n 2 + g l , 垆 b d i a m + l t f m m ( c od ；m r a ( c od i a m c c o = ( 2 k - 1 ) 2 i ，a a ( 1 ，砷+ 2 “船( 弘七) k f f i l 神 j f f i k 2 n f 穸一2 d i a m c c o + 1 ) + n 2 ，一1 d i a m ( c od i a n a ( c o = ( 2 七一1 ) 2 自g 扣，女) + 2 m 锄( g ) + 2 ，口( 口，) i = l脚 d i m ( c o 一炉+ 1 似( 口，k ) + 3 n 2 p - n 2 妇( g + 2 1 k - - - 0 d i a m ( c o = ( 2 詹一3 ) 2 妒a ( 1 ，的+ 3 n 2 p 一3 k f f i l d i m ( c o = ( 2 k - 3 ) p a ( v ，) 2 + 3 ，l 2 p 最后，根据本章第一节的等式( 2 3 ) 以及定义2 2 2 3 ，有 7 ( c v 园g 】2 y ( c l ：雾瓷y 。g 如( ( t ，付) ( d i a m t c o、 2 酬然啪 丕( 2 k - 3 ) 恤岍1 k ) “3 n 矿 2 删m a x 篆( 2 k - 3 ) 嘶_ ) 2 + 孙妒 ( b ) 若m 为奇数，令m = 2 p 一1 ，其中p 一1 d i 啦( g ) 根据引理2 2 2 1 ，对 1 8 中国科学技术大学硕士学位论文 于图c o l 囟g 中任意一个顶点( u ， ) ，有 吼b一。日gccu，”，t，=：七三兰：竺二p一。 然后由本章第一节的等式( 2 1 ) 和( 2 2 ) ，可得 s ( ( 刚) ) = 妒一，( “口) ， ) 2 k - - - - - o d i a m ( o 口七 = 1 + ( ( 2 七一1 ) 船扣，七) + 2 扣， ) ) 2 k 1瑚 p l +f2 n 2 k k f f i d i a m ( 研+ l c l i a m ( a ) = ( 2 k - 3 ) 似) 炉+ n 矿1 k - - - - - o 最后，根据本章第一节的等式( 2 3 ) 以及定义2 2 2 3 ，有 7 ( ? 乌p 1 囟g ) 2 。y ( c l ：髫5 ：【。e y ( g ) t 8 ( 0 ，。) ) ) ( d a m ( 固 1 2 倒珊酬“篆( 2 k - 3 ) 洲弘砷堙_ 加 2 嚣褊 篆( 2 k - 3 ) 。，砷堙 蜘扩1 综上所述。可得 7 c 一 篙：耋：黧，霎：篡 2 2 乘积图的覆盖p e b b l i n g 数 证毕口 注记定理2 2 ，3 4 说明如果圈g ，的顶点数m 满足b 2 j 觑m ( g ) ，那 么对于图c 园g 中的任意一个顶点( t ，( t i ，是c k 园g 的一个关键点当且 仅当口是g 的一个c l 顶点 最后我们考虑长为m 的路户l 仇和任意简单无向图g 的强乘积的情形，其中 m d i d ( c 3 为了能够确定强乘积图f ，m 因g 的关键点，我们再引入一个关于图 g 的新参数。定义如下 定义2 2 2 5 令g 为简单无向图，定义 pc回一罐am(；)(k-1)，oo(u,k)-2ku。v(e-1) “啦一 函 图g 中任意满足 。( 七一1 ) ( t ，砷2 k = p ( g ) 的顶点让记为图g 的一 个只一顶点 引理2 2 2 6 令g 为简单无向图，i g i = 亿p 竹。为长为m 的路，其中m d i a m ( g ) ，并记足产( 撕，鬈i ，) ，设啦为图f ：，i 中一个非端点的顶点，其中 t = 1 ，2 ，m 一1 ，口为图g 中任意一个顶点，则 8 ( ( t 0 ，口) ) 5 ( ( 啦，t ，) ) 证明不妨设t m 一友即l m 2 j ，首先，根据引理2 。2 2 1 可得 书盹卅弘删，虽竺，觚 我们分别考虑下面三种情形 2 0 中国科学技术大学硕士学位论文 情形1 ：当1 d i a m ( g ) t m t 0 即s ( ( t o ，t ，) ) s ( ( 铆，口) ) 疗 “回。州僦 + 讲 扣船 。：l + 砷pd 一 “ 回 州埘 ：考 = n 妻一 b 2 2 中国科学技术大学硕士学位论文 情形2 ：当1 出口m ( 回m t 0 2 2 乘积圈的覆盖p e b b l i n g 数 2 3 即s ( ( t 0 ，口) ) s ( ( t t ， ) ) 情形3 ：当1 巩一d i 8 旺( g ) 0 若k = l ，则正2 ”件1 ( 2 一2 ) + 2 0 着k = 2 ，则乃2 ”t + 1 ( 2 t 一2 ) 0 若七3 ，则噩2 ”t + 1 ( 一2 ) 一o 一2 ) 2 卜t + 1 = 2 ，卜蚪1 ( 2 t 一幻 0 ( b ) 当t + 1 k ，竹一t 时，由七 2 “。+ 1 ( 一( 1 + t ) ) 0 2 3 关键点