论文部分内容阅读
图论起源于十八世纪,是一门相对古老的学科。自二十世纪以来,得到了迅速的发展和广泛的应用。图论作为数学的一个分支,涉及许多学科,比如,化学、物理学、网络理论、计算机科学以及控制论等领域。图的pebbling数问题是由Chung最先将其引入到文献当中。在过去的二十多年中,pebbling数一直作为图论中的热门问题受到众多数学家的关注,同时也被应用于资源运输,网络优化配置等领域。 一个简单连通图上的pebbling移动是指:从一个顶点同时移走两个pebble,消耗掉其中一个pebble,另一个移到与其相邻的顶点上。图G的pebbling数是最小的正整数f(G),满足按照f(G)个pebble的任何一种分配方式开始,总可以通过一系列的pebbling移动把一个pebble移动到图G的任意目标顶点上。pebbling移动可以理解为,在交通运输的过程中,运送的货物为其中的一个pebble,资源损耗既为另一个pebble.本文研究了关于图Dn,G的pebbling数问题。图Dn,G指的是只有一个公共顶点的n个图G的并图。主要结果如下: 1)介绍了图论的背景及pebbling数的基本概念和已有结论;基于鸽巢原理,得到了关于图Dn,Cm的pebbling移动时的一个充分条件。 2)利用分类讨论的思想方法,计算出了奇圈的并图Dn,C2m+1的pebbling数;运用数学归纳法推广并证明了鸽巢原理的衍生引理,同时得到了一个关于图Dn,Cm的pebbling移动的结论。 3)计算出了偶圈的并图Dn,C2m的t-pebbling数和偶圈的q-t-pebbling数,证明了偶圈的并图Dn,C2m满足2t-pebbling性质。