1 概述
1.1 Graph Pebbling
Graph pebbling是一种在给定图上进行的数学游戏。首先我们需要开发一些标记，以便理解Graph pebbling游戏的相关知识。
Graph：由边相连的顶点集合
Pebble：离散计数的可消耗资源，在顶点上具有非负整数权重
Pebbling Distribution D：将给定数量的Pebbles分配到图上各顶点的函数。举个例子：如果图G中的顶点v在分布D下有两个Pebbles，则D(v)=2
Pebbling Move：将Graph中某顶点A上的两个Pebbles经由路径B移动到其相邻的顶点C，路径B权重为一个Pebble，后将一个Pebble放在顶点C上。由于路径B的权重为一个Pebble，每一次经由路径B的移动将消费一个Pebble
Pebbling Sequence：一组Pebbling moves序列，以期Graph达到给定分布
Reachable：在给定分布下，经由一定Pebbling sequence，可以将一个Pebble防止在给定顶点，则称该顶点Reachable
Solvable：给定图分布下，如果任意顶点都是Reachable，则称该分布Solvable
Unsolvable：存在顶点不能Reachable的图分布
在本论文中，我们在第一章节定义了一系列必要的术语术语，并介绍基础知识，以方便理解Graph pebbling游戏。在第二部分，我们将会给出一些该领域中不证自明的结论。第三部分，我们首先叙述Graph pebbling游戏的历史，然后讨论Graph pebbling在数学领域的一些应用。在第四部分，我们将会描述对于特定类型的Graph，如树、超方体、径-2-Graph，找到Solvable的Pebbling numbers的方法。第五部分，我们创建了一些有用的工具，用于研究Graph的优化Pebbling number解，并讨论本领域的最新进展。第六第七部分，在学习了一些拓扑学的基础之后，我们将在Pebbling的上下文中讨论拓扑图论。第八部分，我们将讨论Pebbling问题的复杂度，他们通常是NP-瓦全问题，或者比NP-完全问题更难。第九部分，我们将研究对于特定的Pebbling问题，结构参数，如domination number(此处不知道怎么翻译)和Graph直径对于复杂度的影响。第十部分，我们将给出Graph pebbling游戏的新复杂度结果。为得出我们的主要结论，我们在第十部分推导出了两条引理。我们的结论是：对于嵌入在固定表面上的给定径-2-Graph，决定其是否Solvable的算法具有多项式时间复杂度。在第11部分，我们将以我们队Graph pebbling的研究作为论文结束，并建议了一些遗留问题的讨论渠道。
网友评论