论文部分内容阅读
本文将介绍一个用刷子逐点清理一个网络的问题,我们将其转化为清理图的问题。首先清理一个顶点是指把该顶点清扫的同时将其所有被污染的邻边都恰好用一个刷子清理,且已经被清理的边不能让刷子再次清理。清理完此顶点后,这些刷子都通过它们所清理的边到达这个点相应的邻点处。而我们通过逐步清理图中的顶点来达到清理整个图的目的。现实中,人们在清理一个网络时常常遇到的问题就是被清理过的地方过一段时间后会变的不整洁,本文研究这个问题中,考虑到现实情况,因此我们要求清理能够无限的进行下去。
以上为本文所依据的规则背景,接下来本文共分三个章节。第一章是本文综述,给出图论的基本概念和清理的定义,而后综述相关的研究成果;第二章来解决无限清理的问题并给出清理一个一般无向简单图所需最少刷子数的下界d/2,其中d为该图奇度点的个数,以及关于图的卡氏积下所需刷子数的上限问题;第三章为本文的重点章节,根据前面结论,解决卡氏积下清理Pm×Pn,Cm×Pn,Cm×Cn所需的最少刷子数,分别为m+n-2,m+2n-2,2m+2n-4;另外求出超立方体最少刷子数的一个递推下界。