（应用数学专业论文）关于特殊图的pebbling数的研究.pdf

中文摘要 摘要 图的p e b b l i n g 数问题起源于组合数论和群论，最初是由l a g a r i a s 和s a k s 提出 来的，由c h u n g 第一次引入到文章中的。图的p e b b l i n g 问题是一个资源运送模型， 由在一个简单的连通图的点上的p e b b l e 分配开始，p e b b l i n g 移动是指从一个顶点移 走两个p e b b l e 而把其中一个移到与其相邻的一个顶点上。我们可以把p e b b l e 看做 是燃料罐，则在移动过程中的p e b b l e 损失可以看做为运输费用。图g 的p e b b l i n g 数i ( g ) 是指最小的正整数 ，使得n 个p e b b l e 无论如何放置在g 上，总可以通过 一系列的p e b b l i n g 移动把一个p e b b l e 移到任意一个顶点上。 本文针对图的p e b b l i n g 问题进行了研究，首先介绍了图的p e b b l i n g 的研究背 景及意义，发展和现状。其次，在前人研究的基础下，本文重点研究了齿轮图见。 及其更一般的情况q 2 。的p e b b l i n g 问题。求出了齿轮图见的p e b b l i n g 数，进而 求出了更一般的情况图见h 的p e b b l i n g 数及其它与图的p e b b l i n g 数有关的量，并 证明了或4 满足2 - p e b b l i n g 性质。 关键词：p e b b ii n g 数：最优p e b b li n g 数；覆盖p e b b li n g 数； r u b b li n g 数；齿 轮图； 英文摘要 a b s t r a c t t h eo r i g i n so fg r a p hp e b b l i n gr e s i d ei nc o m b i n a t o r i a ln u m b e rt h e o r ya n dg r o u p t h e o r y t h ei d e ao fp e b b l i n gw a sp r o p o s e db yl a g a r i a sa n ds a k s t h ec o n c e p tw a s i n t r o d u c e da tf i r s tt i m ei nt h ep a p e rb yc h u n g i ti sam o d e lf o rt h et r a n s p o r t a t i o no f r e s o u r c e s s t a r t i n gw i t hap e b b l ed i s t r i b u t i o no nt h ev e r t i c e so fas i m p l ec o n n e c t e d g r a p h ，ap e b b l i n gm o v er e m o v e st w op e b b l e sf r o mav e r t e xa n da d d so n ep e b b l ea ta l l a d j a c e n tv e r t e x w ec a t l l i i l l ( o ft h ep e b b l e sa sf u e lc o n t a i n e r s t h e nt h el o s so ft h e p e b b l ed u r i n gam o v ei st h ec o s to ft r a n s p o r t a t i o n t h ep e b b l i n gn u m b e ro f ag r a p hg ， s ( c ) ，i st h el e a s t ns u c ht h a t , n om a t t e rh o w 刀p e b b l e sa r ep l a c e d0 nt h ev e r t i c e so f g ，o n ep e b b l ec a n b em o v e d t oa n yv e r t e xb ya s e q u e n c eo f p e b b l i n gm o v e s i nt h i sp a p e r , w ef i r s t l yi n t r o d u c et h eb a c k g r o u n da n dt h ed e v e l o p m e n to ft h e g r a p hp e b b l i n g s e c o n d l y , b a s e do nt h ep r e 访。邯s t u d i e s ，t h i sp a p e rm a i n l yf o c 璐馏o n t h ep e b b l i n go fg e a rg r a p h 见4a n dt h em o r eg e n e r a lg r a p h 见细w ec o m p u t et h e p e b b l i n gn u m b e ro fg e a rg r a p h 见”m o r e o v e r , w ec o m p u t et h ep e b b l i n gn u m b e ra n d o t h e r sr e l a t e dp a r a m e t e r so ft h eg r a p hq 抽f i n a l l y , w ep r o v et h a t 见4s a t i f i e s 2 - p e b b l i n gp r o p e r t y k e yw o r d s ：p e b b l i n gn u m b e r ：o p t i m a lp e b b l i n gn u m b e r ；c o v e rp e b b l i n g n u m b e r ：r u b b b l i n gn u m b e r ；g e a rg r a p h 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博硕士学位论文= = 羞王挂殛图的登堂坠! i 篮数的婴宜：。除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体己经公开发表或 未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：羔象擎学位论文作者签名：垄氢1 1 于 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全 文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式出版发 行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密面( 请在以上方框内打“一) 论文储虢王新军导师虢脚 日期：o ? o ，口年6 月多6 日 关于特殊图的p e b b l i n g 数的研究 第1 章绪论 1 1 研究背景及意义 图的p e b b l i n g 数问题起源于组合数论和群论，图的p e b b l i n g 数问题是一个在 图的顶点上用p e b b l e 玩的有趣的数学游戏。游戏的玩法是由一系列的p e b b l i n g 移 动组成的。它是一个资源运输模型。我们可以把p e b b l e 看做是燃料罐。则在移动 过程中的p e b b l e 损失可以看做为运输费用。数学家研究它们的原因是他们可以把 游戏玩法的这种方法用来解决在数论和其它数学领域的问题。它在分解理论和 图论2 1 中都有广泛的应用。 在1 9 8 9 年，k l e i t m m 与蛐【3 1 合作，e r kc h u n g t 4 1 独立证明了如下定理： 设乙为厅阶循环群，且蚓为群乙中元素g 的阶。对于群乙f l on 个元素的每一个序 列( & ) 捌。，存在一个零和序列( ) 。r ，使得1 。 对于一个序列n 娜南舶的交叉数，交叉数在分解理论中肛俏陲要 的变量，在确保交叉数至多为1 的情况下，加强鸽巢原理的推广形式( g ) ， 并且当且仅当对每一个i 繇i = n 时。可以证明其等价形式成立。 图的p e b b l i n g 数的概念最早是l a g a f i a s 和s a k s 在尝试着给出相对于k l e i t m a n 与i , e l l l k e 的证明来说更自然更有结构的另一种证明时提出来的。g l e n nh u r l b e r t 作为在图的p e b b l i n g 问题方面的领军人物，在他的文章嘲中称l a g a r i a s 和s a k s 的 目的是把图的p e b b l i n g 问题作为一个能更直观的证明这个定理的工具介绍给大家。 1 9 8 9 年，f r k c h u n g 在她的关于图的p e b b l i n g 数的文章4 1 中第一次以文献 的形式介绍了p e b b l i n g 数并且给出了图的p e b b l i n g 的确切定义，并且证明了路的 笛卡尔积的p e b b l i n g 数的确定性。对图的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 问题的基本思想是简明易懂的。给定一个简单的连通图g ，选 第1 章绪 论 定目标定点1 ，。现在在g 的顶点上分配k n u 0 个p e b b l e 。在这个初始的分配 中，如果一个顶点上有两个或更多的p e b b l e ，则可以执行一次p e b b l i n g 移动，图的 p e b b l i n g 移动是指从一个顶点移走两个p e b b l e 而把其中一个移到与其相邻的一个 顶点上。p e b b l i n g 的观念是l a g a r i a s 和s a k s 作为一个证明工具而提出的。确切的 说，如果他们得到路的笛卡尔积的p e b b l i n g 数，他们的数论中的结论就可以得到 证明。1 9 8 9 年，c h u n g 在她的文章p e b b l i n g i nh y p e r c u b e s 中证明了路的p e b b l i n g 数， 还提出了2 - p e b b l i n g 性质以及g r a h a m 猜想：对任意的连通图g 和日，有 厂( g 日) 厂( g ) 厂( 日) 。 继这些结果之后，许多数学家都纷纷加入到了图的p e b b l i n g 数的领域的研究。 他们开始研究某些类图的p e b b l i n g 数以及涉及到这些p e b b l i n g 数的图的某些特 殊的性质。图的p e b b l i n g 数在很大程度上都被给出，1 9 9 2 年，d a v i dm o e w s 6 1 对 树的p e b b l i n g 数进行了研究，并且证明了树的g r a h a m 猜想成立。p a c h t e r l 等 人7 】在1 9 9 4 年求出了奇数环和偶数环的p e b b l i n g 数。1 9 9 8 年，d a v i d s h e r s c o v i c i 证明了c 5 满足2 - p e b b l i n g 性质哺1 ，且求出了厂( c 5 c 5 ) = 2 5 即c 5xc 5 g r a h a m 猜 想成立。g l e n nh u r l b e r t 【5 】在1 9 9 8 年出版了as u r v e yo fg r a p hp e b b l i n g 之后。 对图的p e b b l i n g 的发展起到了很大的推动作用。 我们已经得到了完全图，路，环，方体，树，完全二部图，完全，部图1 9 1 ，扇 图，轮图1 0 】，星图1 1 】，和其它类的图的p e b b li n g 数。许多图的笛卡尔积的p e b b l i n g 数，如团的笛卡尔积，树的笛卡尔积，路的笛卡尔积【4 1 ，星图的笛卡尔积j ，扇 图的笛卡尔积以及轮图笛卡尔积【m 1 的p e b b l i n g 数均被给出。 数学家们还研究了图的直径与图的p e b b l i n g 数的关系，p a c h t e r 在文献1 2 1 中 指出：n 个顶点的直径为2 的图g ，其p e b b l i n g 数只能为n 或者n + l 。更进一步， 1 9 9 7 年，c l a r k e 在文献0 1 3 】中指出了直径为2 且连通度尼( g ) 3 的图的p e b b l i n g 数 为n 。2 0 0 6 年，b u k h l l 4 1 研究了直径为3 的图的p e b b l i n g 数的性质。在文献f 1 2 】和文 献1 5 】中还对图的连通度与图的p e b b l i n g 数关系进行了研究。 随着图的p e b b l i n g 数的一些成果的出现，与图的p e b b l i n g 数相关的思想也得 关于特殊图的p e b b l i n g 数的研究 到了很好的发展和深入的研究。其中研究最多的两个与图的p e b b l i n g 数有关的问 题是图的最优p e b b l i n g 数与覆盖p e b b l i n g 数。图的最优p e b b l i n g 数是指最小的正 整数f o p t ( g ) 满足从g 的f o p t ( g ) 个p e b b l e 的某种放置方式开始，总可以通过一系列 的p e b b l i n g 移动把一个p e b b l e 移到任意的目标顶点上。一些图的最优p e b b l i n g 已 经被给出，如路，环【1 6 】，毛虫图1 7 1 ，完全m 一叉树等图的最优p e b b l i n g 数。d a v i d e b u n d e 还在文献中得出了一般图的p e b b l i n g 数的界。 图的覆盖p e b b l i n g 数是指最小的正整数厂( g ) 满足从gi 拘r ( g ) 个p e b b l e 的任 意放置方式开始，总可以通过一系列的p e b b l i n g ，g 中所有顶点上同时至少有1 个 p e b b l e 。b e t s yc r u l l 等在t h ec o v e rp e b b l i n gn u m b e r o fg r a p h s 冽中给出了完全图， 路的覆盖p e b b l i n g 数分别为厂( e ) = 2 n - 1 ，7 ( 只) = 2 力- 1 。g l e n nh u r l b e r t 等在 2 0 0 4 年2 1 得到了方体的覆盖p e b b l i n g 数为7 ( q d ) = 3 d 。2 0 0 4 年，m a g g y t o m o v a 等得到了环的覆盖p e b b l i i l g 数7 ( e ) = 2 7 + 2 卜，+ l 一3 ( 其中，= l 詈i ) 。n a t h a n i e l i i gw a s t o n 和c a r lr y t 唱所得到了完全多部图2 3 1 的覆盖p e b b l i n g 数为： 7 ( k 妒_ ) = 矽( k 妙) ( 其中矽( 蜒附耳) = 4 s 。+ 2 s 2 + + 2 墨一3 ) ，路图 的覆盖p e b b l i n g 数为，( ) = 4 n - 5 。 但是自从j o n a ss j 6s t r a n d 在他的t h e c o v e r p e b b l i n g t h e o r e m 中证明了当计 算任意一个图的覆盖p e b b l i n g 数时，只需考虑一个点的p e b b l e 分配就可以了，这 就可以很容易地计算任何图的覆盖p e b b l i n g 数了。 近些年来，其他的与图的p e b b l i n g 数有关的参数也被纷纷提出和使用，如图 的控制覆盖p e b b l i n g 数，p e g g i n g 数，r u b b l i n g 数等。 1 3 研究内容与结构 本文针对齿轮图和图或山，的p e b b l i n g 数以及其它与p e b b l i n g 数有关的量的问 题进行了研究，得到了一些研究成果。具体内容如下：第l 章介绍了图的p e b b l i n g 数的研究背景，并且简单的介绍了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 数、0 类图的相关定理，图与直径，连通度， 度之间的关系，图的2 - p e b b l i n g 性质及2 t - p e b b l i n g 性质。第3 章介绍了与图的 p e b b l i n g 数相关的量：图的最优p e b b l i n g 数，图的覆盖p e b b l i n g 数，图的r u b b l i n g 数等。第四章主要研究了齿轮图d n 的 问题，进一步研究了更一般的情况, 4 p e b b l i n g 见2 肿的p e b b l i n g 问题。给出了q 。4 的p e b b l i n g 数，证明了o n 满足性,4 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 数相关的量进行了研究。 第五章总结了本文的内容，概括了研究过程中需要进一步研究的问题，对未来的 工作进行了展望。 关于特殊图的p e b b l i n g 数的研究 第2 章图的p e b b l i n g 数与2 - p e b b l i n g 性质 本章介绍了本文所使用的基本概念，介绍了常见图的p e b b l i n g 数，关于0 类 图相关定理结论，及常见图的p e b b l i n g 数，还简单的介绍了图的2 - p e b b l i n g 性质 以及2 t - p e b b l i n g 性质。这些为后面研究其它特殊图的p e b b l i n g 问题奠定了基础。 2 1 基本概念和记号 一个图2 5 1g 是一个三元组，这个三元组包含一个顶点集v ( g ) ，一个边集 e ( g ) 和一个关系，该关系使得每一条边和两个顶点( 不一定是不同的点) 相关 联，并将这两个顶点称为这条边的端点。简单图是不含圈和重边的图。如果g 中 的每一对顶点都属于某一条路径，则图g 是连通的。本文所讨论的图都是简单的 连j 1 1 i ! 。i y ( g ) i = 以为图g 的顶点数。d 为图g 的直径。下面列出本文中所出现的 基本概念、记号等等。 图：一个图g 是一个三元组，这个三元组包含一个顶点集v ( g ) ，一个边集 e ( g ) 和一个关系，该关系使得每一条边和两个顶点( 不一定是不同的点) 相关 联，并将这两个顶点称为这条边的端点。 距离：在图g 中点u 与点v 的距离是指点u 与点y 之间的最短的路径的长度。 直径：在图g 中最长的距离，记为d ( g ) 。 连通度：使图g 不连通或者只剩下一个顶点需要删除的最少顶点个数，记 为茁( g ) 。 度：图g 中顶点y 的度，是指关联到v 的边的条数，记为叱( v ) 或d ( v ) 。图 的最大的顶点的度记为a ( g ) ，最小的顶点的度记为8 ( g ) 。 围长：i g 作- g i r t h ( g ) ，图g 中最短环的长度。 完全图：任两个顶点都是邻接的图。将含刀个顶点的完全图记为k 。 第2 章图的p e b b l i n g 数与2 - p e b b l i n g 性质 二部图：图g 称为二部图，如果y ( g ) 是两个互不相交的独立集( 可以是空集) 的并集，这两个集合称为图g 的部集。 正则图：图g 的最大的顶点度与最小的顶点度相等。即图g 的所有顶点的度 相同。如果所有顶点度是k ，则称g 是k 正则的。 完全二部图：记作e 一它的顶点集由2 个两两互不相交的子集巧和k ( 均 非空) 构成，这里l 巧i = 掰，i k i = 以，m ，刀2 ，每个k 都是疋，。的独立集，i = 1 ，2 。 完全，部图：e 一：坼，它的顶点集由，个两两互不相交的子集k ，k ，形组 成，其边集按下面方式生成：每个k 中的点与自身中的点不相邻，- 与所有5 ( j f ) 中的每一点均相邻若砚表示集k 中点的个数，则以e 用：，唧表示一个完全，部 图。 k n e s e r 图：记作k ( 万，k ) ，其顶点与n 个元素的集合的k 个元素的子集相对应。 两顶点相邻当且仅当与之对应的两个子集交为空。 图的笛卡尔积：记作g x h ，其顶点集为( d e s c a r t e s ) 积 v ( g h ) = y ( g ) y ( 日) = ( x ，y ) l x 矿( g ) ，y y ( 日) ) ， 且两个顶点( 五y ) 与( x ，y ) 相邻当且仅当x = z 7 且 y ，y 7 ) e ( h ) ，或 z ，x e ( g ) 且y = y 。 2 2 图的p e b b l i n g 数 2 2 1 图的p e b b l i n g 数的基本概念 连通图的一个p e b b l i n g 是一些p e b b l e s 在这个图的顶点上的一种放置方式。 定义2 11 4 一个p e b b l i n g 移动是从一个顶点上移走两个p e b b l e s ，扔掉其中的 一个而把另一个移到与其相邻的一个顶点上。为了更好的理解p e b b l i n g 移动，为 了更好的说明p e b b l i n g 移动，下面是p e b b l i n g 移动的一个例子。 关于特殊图的p e b b l i n g 数的研究 30 h _ 图2 1 一个p e b b l i n g 移动 f i g 2 1ap e b b l i n gm o v e 11 定义2 2 t 2 6 1 在一个初始的分配中，如果可以通过一系列的p e b b l i n g 移动将 一个p e b b l e 移到一个点上，则称该点是可达到的。 定义2 3 t 4 1 图g 的一个顶点v 的p e b b l i n g 数是最小的正整数厂( g ，v ) 满足从 g 的顶点上，( g ，1 ，) 个p e b b l e 的任意一种分配方式开始，总可以通过一系列的 p e b b l i n g 移动把一个p e b b l e 移到顶点1 ，上。图g 的p e b b l i n g 数记为s ( o ) ，是对g 的 所有顶点，来说( g ，) 的最大值。也可以说，图g 的p e b b l i n g 数是最小的正整数 s ( g ) ，满足g 的顶点上厂( g ) 个p e b b l e 的任意一种分配方式，总可以使g 中每 一个点都是可达到的。 下面举一个例子来说明下图的p e b b l i n g 数为4 。从这个例子，我们可以看出 尽管对于一个很基本的图来说，如何检查其所有的初始不同的p e b b l e 分配方式很 容易变成一件很复杂的事情 口 图2 2 ( g ) = 4 的一个图 f i g 2 ia g r a p h w h e r es ( g ) = 4 第2 章图的p e b b l i n g 数与2 - p e b b l i n g 性质 定义2 4 吲图g 的t - p e b b l i n g 数是最小的正整数z ( g ) ，满足从g 的项点上 z ( g ) 个p e b b l e 的任意一种分配方式开始，总可以通过一系列的p e b b l i n g 移动把f 个p e b b l e 移到图g 的任意一个目标定点顶点上。 2 2 2 常见图的p e b b l i n g 数及t - p e b b l i n g 数 对于图的p e b b l i n g 数厂( g ) ，显然有厂( g ) p ( g ) i ，这里旷( g ) l 表示图g 的 顶点个数，否则如果除了目标顶点外，其余各点均放一个p e b b l e ，则没有p e b b l e 可以通过p e b b l i n g 移动移到目标顶点。另外有( g ) 2 d ，d 为图g 的直径，否 则在长度为d 的路的一个端点上放2 d 一1 个p e b b l e ，则没有p e b b l e 可以通过 p e b b l i n g 移动移动到路的另一个端点。所以有厂( g ) m a x p ( g ) l ，2 。) 。此外由鸽 巢原理可以的到厂( g ) ( y ( g ) 一1 ) ( 2 。- 1 ) + 1 ，否则，由鸽巢原理，无论开始如 何放置p e b b l e ，至少有一个顶点的p e b b l e 个数不少于2 d ，则可以通过p e b b l i n g 移动移到任意目标顶点1 个p e b b l e 进一步，我们已经得到了一些初步的结果如： ( e ) = 咒，( 只) = 2 ”1 ，厂( 尸) = l o ，厂( q ”) = 2 4 ，厂( k ，。) = 聊+ 甩， 厂( 如卅：，卅，) = 码+ 鸭+ + 其中e 为栉个顶点的完全图，只为力个顶点的路， p 为彼得森图，q ”为n - 方体，如，。为完全二部图口，k m 2 。，为完全，部图9 1 。 对于树的p e b b l i n g 数的研究，c h u n g 提出利用最大路径分隔解决的思想，给 出了f ( t ，) 的公式，特别的给出了z ( r ，厂) 的求法。 定理2 1 川 设( ，如，乙) 为树丁的，最大路径分隔的路序列中每一个路的 ，卅、 顶点个数的一个数组，则有厂( 丁，厂) = i 2 l 一聊+ 1 。 i = l 1 9 9 5 年，m o e w s 利用其它的辅助性的结论给出了树的p e b b l i n g 数的另一种证 明。2 0 0 8 年，d a v i dp b u n d e l l 9 1 等人通过用权重函数讨论的方法给出了树的 p e b b l i n g 数的另种新的证明，并且说明了树的p e b b l i n g 数在线性时问中如何计 8 一 一 差量塑壁堕塑壁些! 垫墨墼堕塑窒 一一 ，_ - _ - - _ _ - _ _ _ 一一。 算。 对于刀个点的环e 的p e b b l i n g ，p a c h t e r , s n e v i l y 2 8 1 和v o x m a n 证明了如下 定理： 定理2 2 对于任意七1 ，偶数环厂( c 2 。) = 2 ，奇数环( g ) = 2 l 孚j + 1 。 d a v i dp b 吼d e 等人在2 0 0 8 年用不同的方法给出了定理2 2 更简洁的证明。 对于以个点的环e 的t - p e b b l i n g ，h e r s c o v i c i 2 8 1 利用图的a l p h a - p e b b l i n g 的原理证明了如下定理： 定理2 3 对于任意七1 ，偶数环z ( q 。) = f 2 ；奇数环 j c ( c 2 k + 1 ) ：掣村( f 一1 ) 。j c ( = 二半+ 2 ( 卜) 。 此外还有许多关于图的p e b b l i n g 数的定理和结论2 9 h 3 6 1 。对于图的t - p e b b l i n g 数已经得到了很多结果， 定理2 4 【3 7 1k n 为，1 个点的完全图，其中n 2 ，则z ( k ) = 2 t + n 一2 。 定理2 5 【3 8 1设墨= v ) ，设e 一，- ( u l ，“2 ，“州) 是长度为刀一1 的环。则轮 图( 甩5 ) 的t p e b b l i n g 数为z ( 形) = 4 f + 力一4 。 定理2 6 t 3 9 1设e 为咒个点的扇图( 甩4 ) ，则z ( c ) = 舢+ 刀一4 。 定理2 7 【删 设完全厂部图k 。i 册：，坼，其中铂朋2 聊，m a l ，则对于 图g = k m 。，则有： z ( g ) = 4 2 ，t + + 铂n - _ 2 ，2 , 2 2 t m 2 t + l 的k n e s e r 图k ( m ，t ) 是涉及到上面定理的有一个漂亮的图族， 当f = 1 时，k ( m ，t ) 为完全图k m 。当历= 5 且f = 2 时，k ( m ，t ) 为p e t e r s e n 图尸。 它们都是0 类图。当t 2 _ 且m 3 t - 1 ，我们可以得到d ( k ( m ，f ) ) = 2 且 - x ( k ( m ，f ) ) 3 ，由上面的定理可以得到k ( 册，t ) 为0 类图。进一步，结合b l c h e n 和k w l i h 4 4 1 的结论：k ( 聊，t ) 为连通的，边传递的且是正则的，l o v a s z 3 7 1 的结论：k ( 聊，t ) 的连通度等于它的度，以n 上n n g n ，h u r l b e r t 证明了如下结 论。 关下特殊图的p e b b l i n g 数的研究 定理2 1 3 4 6 1 对于任意常数c 0 ，如果存在一个整数岛，使得对任意， 乇， s _ c ( t l 0 9 2f ) “2 且聊= 2 t + s ，则有k ( 朋，f ) 为0 类图。 当考虑到不是0 类图的条件时，很容易得到如果图g 的围长 g i r t h ( g ) 2 1 0 9 n ，贝j jf ( g ) v ( o ) 。h u r l b e r t 在他的文章4 7 中提出这样的问 题：是否存在一个常数g ，使得如果满足砌( g ) g ，则有( g ) v ( o ) 。 c z y g r i n o w 等通过用定理2 4 和相似于e r d 的任意围长和色数图的构造法的概率排 除的方法给出了上面问题的否定答案。 设甄n ) 为最大的数g 使得存在一个0 类图g 至多船个顶点的且有限围长 g i r t h ( g ) g ，则对于任意的疗3 ，可以得到如下定理： 定理2 “l 厢莉一1 2 j - l m 2 j + l 。对于任意的 t n 3 3 6 ，有6 ( 朋) = 【- m 2 j + l 。 除了二部图，我们可以在其他图上考虑同样的问题。c z y g r i n o w 和h u r l b e r 在 随机图上证明了一个类似的结论。设g ( ，z ) 为最小的七使得任意的图g g ( ，z ，k ) 都是0 类图。有如下结论成立： 第2 章图的p e b b l i n g 数与2 - p e b b l i n g 性质 定理2 1 6 4 7 1 对于任意的，z 6 ，有ig ( n ) l ，满足2 t - p e b b l 崦性质5 2 1 ；完全，部图k 。啦埘r 满 足2 t p e b b l i n g 性质5 2 1 ；扇图c 满足2 t - p e b b l i n g 性质。 第3 章其它与图的p e b b l i n g 数相关的参数 第3 章其它与图的p e b bi n g 数相关的参数 本章介绍了与图的p e b b l i n g 数有关的问题是图的最优p e b b l i n g 数与覆盖 p e b b l i n g 数的重要理论。这些为后面研究其它特殊图的p e b b l i n g 问题奠定了基础。 3 1 图的最优p e b b l i n g 数 在研究图的p e b b l i n g 数的问题时，一个很重要要的任务是找到图的最大不可 解分配的大小。对于图的最优p e b b l i n g 数的研究，我们的主要任务转化为找到最 小的可解分配的大小。这样的模型可能会有助于一个公司去为他们的资源寻找最 佳的资源分配方案。下面介绍一下图的最优p e b b l i n g 数的基本内容和结论。 定义3 1 n 9 1 图的最优p e b b l i n g 数，记作厶( g ) ，是指最小的正整数厶( g ) 满足从g 的厶( g ) 个p e b b l e s d e 的某种放置方式开始，总可以通过一系列的 p e b b l i n g 移动把一个p e b b l e 移到任意的目标顶点上。 对于最优p e b b l i n g 数的研究最早开始于p a c h t e r ，s n e v i l y 和v o x m a n 【3 3 1 的一些 结论厶( 只) = i 孚i ， 厶( c 3 ，+ ，) - 2 h ，。 m o e w s 证明了 ( 参厶( 郇( 圹蚶，并且证明了对傩意的g 弛有g r a h a m 想成 立： 厶( g 日) = 厶( g ) 厶，( h ) 。 c l a r k 证明了求任意图的最优p e b b l i n g 数问题是一个n p 难问题。 d a v i d b u n d e 等人研究了，z 个顶点的图的最优p e b b l i n g 数的一般上界。 定理3 1 【5 3 1 图g 的最优p e b b l i n g 数的上界厶( g ) 罔。 对于一般图的界j e s s i c am u n t z 等人得出了如下结论： 定理3 2 t 5 4 1 如果图g 的直径为d ，则有以下结论成立： 关于特殊图的p e b b l i n g 数的研究 厶( g ) 要d + l 如果d 兰o ( m 。d3 ) 3 、 7 ；( d + 2 ) 如果d 基l ( m o d 3 ) 詈( d + 1 ) 如果d 三2 ( m o d 3 ) 定理3 3 【s 4 1对于每个自然数d ，则存在图g 的直径是d 且满足 厶( g ) = 2 d 。 由上面定理也可以看出对于任意的图g ，显然有厶( g ) i l l i n ( 2 d ，r 等 ) 对于直径为2 和3 的图，j e s s i c am u n t z 等人对最优p e b b l i n g 数与其控制集的 性质进行了研究。 定理3 4 【“1设图g 为直径是2j l n 个顶点的图，有如下结论成立： ( 1 ) 当且仅当图g 存在一个顶点为控制点时，厶( g ) = 2 ； ( 2 ) 当且仅当图g 的最小控制集为一对相邻点时，厶( g ) = 3 ； ( 3 ) 当且仅当图g 不存在有一个点或两个相邻的点组成的控制集时， 厶( g ) = 4 。 定理3 5 t 5 4 1设图g 为直径是3 且刀个顶点的图，如果有一个顶点的偏度为 2 ，则下结论中必有一个成立： ( 1 ) 当且仅当图g 存在一个控制集为一对相邻点时，f o p t ( g ) = 3 ； ( 2 ) 当且仅当存在一个顶点w ，使得d 2 【w 】= 矿并且不存在有两个相邻的顶点 构成的控制集时，f o p t ( g ) = 4 ； 3 2 图的覆盖p e b b l i n g 数 当我们谈及到可能的资源分配时，很自然的我们会想到同时移到每一个顶点 上一个p e b b l e 这种情况，而不是想p e b b l i n g 数中定义的那样只移个p e b b l e 到一 个目标顶点上，这就是我们要研究的覆盖p e b b l i n g 数，下面简单介绍一下有关覆 盖p e b b l i n g 数一些基本的概念和结论。 第3 章其它与图的p e b b l i n g 数相关的参数 定义3 2 瞬1 图的覆盖p e b b l i n g 数：记作7 ( g ) ，最小的正整数y ( g ) 满足从g 的7 ( g ) 个p e b b l e s 的任意放置方式开始，总可以通过一系列的p e b b l i n g 移动，把 一个p e b b l e 同时移到g 中所有顶点上。 更一般的形式是在g 中顶点上定义一个权重函数w ，定义g 的权重覆盖 p e b b l i n g 数如下： 定义3 3 明 图的权重覆盖p e b b l 堍数：记作凡( g ) ，最小的正整数( g ) 满 足从g0 0 r 。( g ) 个p e b b l e s 的任意放置方式开始，总可以通过一系列的p e b b l i n g 移动，对于所有的顶点1 ，能够把w ( v ) 个p e b b l e 移到，上。 特别的，对于所有的顶点，有w ( 1 ，) = 1 时，则为图g 的覆盖p e b b l i n g 数。 另外人们定义了覆盖p e b b l i n g 数和p e b b l i n g 数之间的一个量覆盖p e b b l i n g 率。 定义3 4 覆盖p e b b l i n g 率，记作尸( g ) ，为图g 的覆盖p e b b l i n g 数与p e b b l i n g 数的比。帅( g ) = 怒。对于一类图i 的覆盖p e b b l i n g 率柙) ，有 p ( r ) = s u p 甜p ( g ) 。 对于一类图的覆盖p e b b l i n g 率来说，可能是有界的，也可能是无界的。对于 完全图k ，星图s ，路尸的覆盖p e b b l i n g 率，我们有p ( k ) = p ( s ) = p ( p ) = 2 。 对于树丁的覆盖p e b b l i n g 率，我们有p ( 丁) = 。 研究了团和树的权重覆盖p e b b l i n g 数，并且证明了一类图的覆盖p e b b l i n g 率 可能是任意大的，并且给出了树的覆盖p e b b l i n g 率是任意大的。 定理3 6 设w 为1w l = 乏：w ( v ) 并且r a i nw = m i n ，w ( v ) ，对于每个正的权重 - i _ 1 ， ， 函数w ，有九( k ) = 2 1w i - m i n w 。 定理3 7 对于图g 定义j 。( g ) = m a x ，。w ( “) 2 d 儿”，这罩d ( “，1 ，) 为“与v 的距离。对于每个正的权重函数w ，对于任意的树丁，有。( k ) = s 。( r ) 。 关于特殊图的p e b b l i n g 数的研究 h u l b e r t 5 6 1 等得到了一个对于d 维方体的覆盖p e b b l i n g 数的很好的结果 7 ( q d ) = 3 d 。t o w y 研究了环和图的笛卡尔积的覆盖p e b b l i n g 数，w a t s o n m l 等研 究了轮图和完全多部图的覆盖p e b b l i n g 数。 对于任意图的权重覆盖p e b b l i n g 数的研究，主要的技巧是证明涉及最大的w 不可解分配是简单的，也就是集中考虑一个点。我们考虑一个重要的问题，对于 任意图和正的权重函数，w 不可解分配是简单的。j o n a ss j o s t r a n d 和a n n a l i e sv u o n g 独立的证明s t a c k i n g 定理，这就使得可以很容易的求出任意图的覆盖p e b b l i n g 。 定理3 8 澄1 任意图g 和正权重函数w ，则有凡( g ) = s 。( g ) 。 3 3 图的r u b b l i n g 数 图的p e b b l i n g 数是一个很好的资源分配模型，这里每传递一个p e b b l e 就相 应的损失一个p e b b l e 。图的r u b b l i n g 数是c h r i s t o p h e r b e l f o r d 5 9 1 等2 0 0 9 年提出 来的。目前还没有其他人对其做更深入的研究，图的r u b b l i n g 就是在保持原来 p e b b l i n g 移动每传递一个p e b b l e 就相应的损失一个p e b b l e 不变的基础上，将传 递方式放宽了限制。这样就出现了许多新的有趣的问题。 定义3 5 t 5 9 1r u b b l i n g 移动是一个放宽了移动方式的p e b b l i n g 移动。在原 有的p e b b l i n g 移动规则，有额外增