艺术画廊4-染色及联合看守问题研究

来源 :大连海事大学 | 被引量 : 0次 | 上传用户:applee911
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
艺术画廊问题来源于实际生活,与简单多边形三角剖分是密不可分的,多年来,已经引起越来越多的研究者的关注.现如今,它在现实生活许多领域中都有着重要的应用.因为艺术画廊4-染色方法可以减少大部分简单多边形需要的看守数目,因此,无论在理论上还是在实际应用中,对其研究都具有重要的意义. 本文主要在3-染色的基础上研究艺术画廊4-染色问题,以及联合看守问题中一类特殊简单多边形的联合看守上限问题. 首先,在艺术画廊看守问题中,因为对绝大多数的简单多边形来说,由3-染色方法得到的结果并不是最优的.所以,本文根据三角剖分与二叉树的对应关系,通过分析三角剖分中两相邻三角形的邻接关系,利用染色的方法,提出4-染色方法以及4-染色规则,并对4-染色后的情况进行了分析与说明.得出任一类颜色的点覆盖整个简单多边形的条件、至少一类颜色的点覆盖整个简单多边形的条件,以及对不能覆盖产生的原因进行分析. 其次,在联合看守问题中,Michael得出了联合看守集合的上限应为[3n-l/7 ].本文通过对Michael证明过程以及相关结论的分析,首先将一个三角剖分Tn划分为两个三角剖分然后对三角剖分Tm进行分析,最后利用归纳法,对一类特殊的简单多边形,即简单多边形三角剖分的对偶图为链状的情况,证明了联合看守集合至少需要[2n/5]个联合看守.
其他文献
本文对模糊k-拟传递阵以及可分解的模糊关系的性质进行了讨论。首先引入了模糊k-拟传递阵的概念,给出了它与其他传递性矩阵的关系,给出了k-拟传递阵的等价刻画,研究了它与其截矩
经典的交换经济核配置收敛定理是指经济核收敛到Walras均衡.本文将要讨论纯交换经济的背景下,以效用函数定义的近似核的效用收敛到需求集的效用.由于需求集的效用是最大的,因
一直以来,国内外很多学者对同宿轨,异宿轨分支问题的研究有很大的兴趣.研究奇异轨道分支问题,具有重要的理论和实际意义.本文主要研究两类奇异环的分支问题:三维空间中的同宿
在环面拓扑中,小覆盖是重要的研究对象之一,所谓小覆盖是指一个n维的闭流形,这个闭流形具有局部标准的((Z)2)n作用,并且该作用的轨道空间是一个简单凸多胞形.设Δn表示n维的单形,P
在研究磁场力对导电流体定常运动的过程中,我们得到的方程是非线性的,这就使磁流体动力学流动的数学分析复杂化,但可以用数值法求解.它们虽然是简化情况的解,然而清晰地阐明了基
在最近的50年中,机器排序已经成为组合最优化中最重要和最活跃的研究课题之一.在大多数经典的排序文献中,所有的工件都必须安排在机器上加工.也就是说,我们不允许拒绝任何工
现实中的许多过程都可以用广义系统来建模,例如,受限控制系统,电路系统,某些人口增长模型以及奇异扰动系统等。由于广义系统比正常系统可以更好地描述物理现象,所以广义系统
本文主要分为三章。第一章介绍文章的研究背景,研究动机和主要结果。  第二章介绍本文的主要概念如科斯居尔代数和科斯居尔过滤,有限格及由有限格定义的标准分次代数,即Hibi环