图多项式若干问题研究

发布时间：2017-09-24 03:49

  本文关键词：图多项式若干问题研究

  更多相关文章： 图多项式 Tutte多项式 子图分支多项式 确定性复杂网络模型 生成树

【摘要】：本文主要由五章构成。在本文的前半部分,我们主要研究了自相似复杂网络模型的Tutte多项式的计算。在本文的后半部分,我们研究由子图分支多项式确定的图不变量,由子图分支多项式确定的图以及子图分支多项式的区分度。在第一章,我们对图多项式研究现状和我们的研究动机进行了总述。在第二章,我们介绍了图论的一些基本知识,这些知识都是叙述我们工作的必要准备。在第三章,我们主要研究Tutte多项式的计算。(1).在文献[23]中,F. Comellas等人提出了一类自相似无聚类的小世界网络模型Mn,并在文献[24]中研究了这一类网络模型的生成树数。我们利用生成子图分类的办法,研究了Mn的Tutte多项式,得到了T(Mn;x,y)的一个递归表达式。利用这个递归表达式,我们解得图Mn的流多项式,色多项式,生成树数,强连通定向数,无圈定向数等图不变量的具体表达式。(2).在文献[82]中,章忠志等人首次将Farey图作为复杂网络模型来研究,并在文献[83]中利用矩阵树定理计算了Farey图的生成树数。我们利用Farey图Gn自相似的结构特点,得到了T(Gn;x,y)的一个递归表达式。在这个基础上,我们还研究了瓯的色多项式和可靠性多项式,并得到了Tutte多项式在某些特殊点(x,y)的值。(3).在文献[81,84]中,章忠志和张静远等人利用不同的方法分别计算了Apollonian网络的生成树数。我们没有直接计算Apollonian网络的Tutte多项式,而是研究其对偶图。利用Apollonian对偶图与Hanoi图的结构联系,我们得到了Apollonian对偶图的Tutte多项式的一个递归表达式。(4).我们发现,大部分确定性复杂网络模型都是通过模块组合得到的,而常见的模块组合方法就是粘合两个模块之间的顶点。于是,我们研究了两点连图G：H的Tutte多项式。研究发现,组合后的模块的Tutte多项式T(G:H;x,y)能由各个子模块的Tutte多项式表示。利用这个表示式,我们计算了拟分形无尺度网络和广义(2,2)-花图的生成树数,还得到了链环的Tutte多项式的一个递归表达式和书图的Tutte多项式的一个具体表达式。在第四章,我们研究子图分支多项式Q(G;x,y),这个双变量多项式是由Tittmann等人[75]在研究复杂网络的社团结构时提出的。与双变量的Tutte多项式类似,子图分支多项式也包含了图的很多信息,例如图顶点数,边数,连通分支数和独立数等。我们发现,还有其它的一些图不变量能由子图分支多项式确定,例如图的顶点连通度。在一些特殊的图类中,例如正则二部图中,长为4的圈数等也能由子图分支多项式确定。利用子图分支多项式的这一性质,我们发现一些特殊的图类能由子图分支多项式确定,例如完全二部图,轮图,友谊图,书图,超方体等。最后,我们还比较了子图分支多项式与一些其它的多项式的区分度,发现子图分支多项式与其他多项式在区分度上没有明显的关联。我们的这些结果,部分回答了Tittmann[75]等人提出的三个公开问题。在第五章,我们总结了本文的主要工作,提出了许多需要进一步展开研究的问题。
【关键词】：图多项式 Tutte多项式 子图分支多项式 确定性复杂网络模型 生成树
【学位授予单位】：湖南师范大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要3-5
• 英文摘要5-9
• 1. 绪论9-13
• 1.1 图多项式的发展及现状9-12
• 1.2 研究背景及意义12-13
• 2 预备知识13-22
• 2.1 基本概念和术语13-15
• 2.2 图运算和一些特殊图类15-19
• 2.3 一些图多项式19-22
• 3. 几类网络图的Tutte多项式22-61
• 3.1 Tutte多项式的定义及基本性质22-25
• 3.2 一类自相似图的Tutte多项式25-34
• 3.3 Farey图的Tutte多项式34-41
• 3.4 Apollonian图的Tutte多项式41-49
• 3.5 两点连图的Tutte多项式49-61
• 4. 子图分支多项式61-75
• 4.1 子图分支多项式的定义及基本性质61-63
• 4.2 由子图分支多项式确定的图不变量63-67
• 4.3 由子图分支多项式确定的图类67-72
• 4.4 子图分支多项式的区分度72-75
• 5. 结束语75-77
• 参考文献77-83
• 硕博连读期间发表的论文83-84
• 致谢84-85

【相似文献】

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

1 吴廷增;扈生彪;;完全图的两类生成子图是谱唯一确定的(英文)[J];华东师范大学学报(自然科学版);2012年01期

2 周怀鲁;;圈——书Ramsey数[J];曲阜师范大学学报(自然科学版);1988年02期

3 韩丛英,宁伟;具有约束的极小生成子图的一个算法[J];山东矿业学院学报(自然科学版);1999年04期

4 邱念慈;n阶无向完全图非同构生成子图的结构与作法[J];扬州教育学院学报;2004年03期

5 蔡小涛;;连通的欧拉生成子图[J];数学季刊;1990年Z1期

6 周怀鲁;奇圈对轮的Ramsey数[J];数学杂志;1995年01期

7 曹细玉,毛经中;生成子图与图的哈密顿性质[J];湖北大学学报(自然科学版);1996年04期

8 李霄民;李登信;雷澜;;一类用于寻找欧拉生成子图边数的收缩子图[J];数学的实践与认识;2010年20期

9 刘芝梅;曹炬;刘毅;;寻找2-边连通子图的一种近似算法[J];应用数学;2007年S1期

10 汤鸿鸣;;寻找哈密尔顿函数图形的周期[J];福建电脑;2012年06期

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

1 廖云华;图多项式若干问题研究[D];湖南师范大学;2015年

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

1 鲍旭东;图的BB-染色[D];浙江师范大学;2015年

2 周兰;图的BBC染色[D];浙江师范大学;2010年

3 丁哲衡;几类网络优化和改进问题的算法研究[D];中国计量学院;2013年

4 张水明;图的BB-染色[D];浙江师范大学;2011年

5 何梅芝;图谱的一些应用[D];湖南师范大学;2006年

6 王娜;关于图的分数因子的若干结果[D];曲阜师范大学;2007年

，

本文编号：909205