计算代数方法在图论中的几个应用

发布时间：2017-04-05 03:02

  本文关键词：计算代数方法在图论中的几个应用，由笔耕文化传播整理发布。

【摘要】：图论中许多计数问题一般涉及的都是求极小或极大值的问题,而且大多数是限制在某些特殊类型图的范围采用优化的方法来解决的.对于一般有限图G的支配集问题、边覆盖问题、强边着色问题、星着色问题和2距离着色问题,本学位论文首先引入κ-支配集问题,κ-边覆盖问题,κ-强边着色问题,κ-星着色问题,κ-2距离着色问题,并建立由多元多项式方程组给出的与每个κ-计数问题相对应的代数模型；其次,运用计算代数中的Grobner基方法给出每个多元多项式方程组模型的解的存在性的有效判别准则；在每个多元多项式方程组模型的解的存在性确定的前提下,用Grobner基方法给出具体的求解方案,并用计算机代数程序MAPLE给出验证实例；最后由此给出求解对应的极大与极小值问题的具体步骤. 由于计算代数原理,特别是关于多元多项式理想的Grobner基原理和方法,已经成为数学领域中处理涉及可交换多元多项式有关问题的强有力工具,而使用诸如MAPLE, CoCoA, MACAULAY中任何一个成熟的计算机代数系统,都可有效地计算出一个Grobner基,因此本学位论文的研究工作对于用计算代数方法解决图论中其它类似的计数问题也可提供进一步的可行性依据和可参考途径.
【关键词】：图 计算代数 支配集 边覆盖 强边着色 星着色 2距离着色 Gr(o|")bner基
【学位授予单位】：海南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-8
• 引言8-10
• 1 预备知识10-17
• 1.1 图论中的基本定义10-11
• 1.2 多项式理想的Grobner基11-17
• 2 图的κ-支配集问题与Grobner基求解17-26
• 2.1 支配集的预备知识17-18
• 2.2 κ-支配集问题的多项式方程组模型与Grobner基求解18-20
• 2.3 求图的支配数和极小支配集的计算方法20-21
• 2.4 MAPLE验证举例21-26
• 3 图的κ-边覆盖问题与Grobner基求解26-33
• 3.1 边覆盖集的预备知识26-27
• 3.2 边覆盖问题的多项式方程组模型27-28
• 3.3 κ-边覆盖存在性的Grobner基判别28-29
• 3.4 求图的κ-边覆盖,边覆盖数与极小边覆盖的Grobner基方法29-30
• 3.5 MAPLE验证举例30-33
• 4 图的κ-强边着色问题与Grobner基求解33-41
• 4.1 强边着色的预备知识33
• 4.2 κ-强边着色问题的多项式方程组模型33-36
• 4.3 求κ-强边着色的Grobner基方法36
• 4.4 求图的强边着色数的计算方法36
• 4.5 MAPLE验证举例36-41
• 5 图的κ-星着色问题与Grobner基求解41-47
• 5.1 星着色的预备知识41
• 5.2 κ-星着色问题的多项式方程组模型41-44
• 5.3 求κ-星着色的Grobner基方法44
• 5.4 求图的星着色数的计算方法44
• 5.5 MAPLE验证举例44-47
• 6 图的κ-2距离着色问题与Grobner基求解47-55
• 6.1 2距离着色的预备知识47
• 6.2 2距离着色问题的代数不等式方程组模型47-48
• 6.3 κ-2距离着色问题的多项式方程组模型48-50
• 6.4 κ-2距离着色存在性的Grobner基判别50-51
• 6.5 求κ-2距离着色的Grobner基方法51
• 6.6 求图的κ-2距离着色数的计算方法51-52
• 6.7 MAPLE验证举例52-55
• 参考文献55-57
• 硕士期间提交和发表论文情况57-58
• 后记58

【相似文献】

中国期刊全文数据库 前8条

1 刘桂真;邓小铁;徐常青;;系列平行图的除V*外的边覆盖划分[J];中国科学(A辑:数学);2006年06期

2 王纪辉;;关于近似二部图边覆盖染色的一个充分条件[J];山东大学学报(理学版);2006年01期

3 宋慧敏,刘桂真;边覆盖临界图的一些性质[J];数学进展;2004年01期

4 欧阳章东;黄元秋;任俊峰;;图的边覆盖数、围长和最大亏格[J];内蒙古师范大学学报(自然科学汉文版);2008年03期

5 张福基,林诒勋;图的两类一般多项式[J];数学学报;1985年01期

6 袁春华;冯立华;邢顺来;;关于图的bondage数的一点注记[J];山东大学学报(理学版);2006年04期

7 闵安共;;彼得松图的几个性质[J];数学学习与研究(教研版);2009年10期

8 ;[J];;年期

中国硕士学位论文全文数据库 前1条

1 尹杰杰;计算代数方法在图论中的几个应用[D];海南大学;2015年

  本文关键词：计算代数方法在图论中的几个应用，由笔耕文化传播整理发布。

，

本文编号：286340