超立方图论文-石玲娟

超立方图论文-石玲娟

导读:本文包含了超立方图论文开题报告文献综述及选题提纲参考文献,主要关键词:(3,6)-富勒烯图,n维超立方图,强迫数,反强迫数

超立方图论文文献综述

石玲娟[1](2015)在《(3,6)-富勒烯图与超立方图的匹配强迫和反强迫数》一文中研究指出图的强迫问题出现在各种子结构及相关应用问题中,如:完美匹配,控制集和染色等.设M是图G的一个完美匹配.如果S(?)M且G的其它完美匹配都不包含S,那么S叫做M的一个强迫集,其最小强迫集的大小叫做M的强迫数.如果S∈E(G)M且G-S有唯一完美匹配M,那么S叫做M的一个反强迫集,最小反强迫集的大小叫做M的反强迫数.G的所有完美匹配的强迫数的最小值叫做G的最小强迫数,记为f(G).G的所有完美匹配的反强迫数的最小值叫做G的反强迫数,记为af(G).G的所有完美匹配的反强迫数的集合叫做G的反强迫谱.(3,6)-富勒烯图是一类连通叁正则的平面图,它的每个面的边界是3-长圈或者6-长圈.本文主要研究(3,6)-富勒烯图的强迫数和反强迫数以及超立方图Qn的反强迫谱.(3,6)-富勒烯图的连通度是2或者3,依据连通度对(3,6)-富勒烯图G进行分类讨论,本文证明了f(G)=1当且仅当G的连通度是2或者G同构于K4.f(G)≥2当且仅当G的连通度是3且G不同构于K4.进而证明了af(G)=2当且仅当G的连通度是2或者G同构于K4,af(G)≥3当且仅当G的连通度是3且G不同构于K4.特别地,本文确定出所有反强迫数达到下界3的(3,6)-富勒烯图.对n维超立方图Qn,当n≥3时,我们找到了它的反强迫谱的一个子集,这个子集构成一个公差为n-2的等差数列.特别地,本文表明了这样的子集构成3-维、4-维超立方图的反强迫谱.(本文来源于《兰州大学》期刊2015-03-01)

吕华众[2](2013)在《图的条件匹配排除问题的计算复杂性和平衡超立方图的若干网络性质》一文中研究指出决定超大型并行分布式系统性能最主要的因素是各个处理器之间连接的拓扑结构,称为互连网络,简称网络.网络的拓扑结构可以用图来表示:处理器或者存储器用顶点来表示,处理器或者存储器之间的连接用边来表示.因此图论在设计网络和分析网络性能方面的优势是自然的和有力的.本文主要用图论的方法研究了平衡超立方图的一些网络性质和匹配排除及其相关问题的计算复杂性.本文共分为六章.第一章首先介绍了互连网络和图论中的一些基本概念和符号.然后我们介绍了匹配排除集、条件匹配排除集和反凯库勒集的概念.接下来我们给出了计算复杂性的一些基本概念和术语.紧接着我们给出了平衡超立方的定义、研究背景和一些性质.最后我们给出了本文的主要研究结果.第二章我们研究了匹配排除问题、反凯库勒问题、条件匹配排除问题和s-限制匹配排除问题的计算复杂性.由定义,我们表明有完美匹配的二部图上的匹配排除问题和一类称作完美匹配最小障碍集问题(minimum blocker perfect matching problem)是等价的.根据二部图上的完美匹配最小障碍集问题是NP-完全的,我们证明了二部图上的匹配排除问题也是NP-完全的.我们将二部图上的匹配排除问题通过多项式时间归约为反凯库勒问题,从而证明了二部图上的反凯库勒问题也是NP-完全的.进而,我们得到条件匹配排除问题也是NP-完全的.作为条件匹配排除数定义的推广我们提出了s-限制匹配排除数(s是正整数)的概念.同时,我们也证明了二部图上的s-限制匹配排除问题是NP-完全的.在第叁章,我们研究了平衡超立方的匹配排除数和条件匹配排除数.我们得到了对于所有的正整数n,平衡超立方BHn的匹配排除数的大小均为2n,并且BHn的每个大小为2n的匹配排除集都是平凡的.进一步地,我们得到了平衡超立方的条件匹配排除数是4n-2.第四章提出了平衡超立方BEn的一个Cayley图模型,从而证明了BHn是Cayley图.这个结果推广了之前BHn是点传递的这一结果.基于此Cayley图模型,我们给出了BHn的一个最短路路由算法,第五章研究了平衡超立方BHn的限制连通性方面的一些性质.我们得到了当n≥2时,BHn的2-限制点连通度和2-限制边连通度分别为4n-2和4n-4.进一步地,我们得到了BHn的3-限制边连通度为6n-4.第六章研究了平衡超立方BHn的一类Hamiltonian路嵌入问题.由BHn是Hamiltonian laceahle的和双泛连通的,我们得到了BHn是超Hamiltonian laceable的.(本文来源于《兰州大学》期刊2013-03-01)

林翠琴[3](1992)在《超立方图和超立方有向图的同构因子分解》一文中研究指出图G=(V,E)的一个同构因子分解是边集E的一个划分:{E1,E2,…,Et},使得生成子图(V, E1),…,(V,Et)都彼此同构。若 H≌(V,E1),记为 H[G或 t]G.若对每个t≥2.当   时.均有:tG,则称G为有理图.文章证明了超立方图(hypercube)和超立方有向图都是有理图.(本文来源于《清华大学学报(自然科学版)》期刊1992年03期)

超立方图论文开题报告

(1)论文研究背景及目的

此处内容要求:

首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。

写法范例:

决定超大型并行分布式系统性能最主要的因素是各个处理器之间连接的拓扑结构,称为互连网络,简称网络.网络的拓扑结构可以用图来表示:处理器或者存储器用顶点来表示,处理器或者存储器之间的连接用边来表示.因此图论在设计网络和分析网络性能方面的优势是自然的和有力的.本文主要用图论的方法研究了平衡超立方图的一些网络性质和匹配排除及其相关问题的计算复杂性.本文共分为六章.第一章首先介绍了互连网络和图论中的一些基本概念和符号.然后我们介绍了匹配排除集、条件匹配排除集和反凯库勒集的概念.接下来我们给出了计算复杂性的一些基本概念和术语.紧接着我们给出了平衡超立方的定义、研究背景和一些性质.最后我们给出了本文的主要研究结果.第二章我们研究了匹配排除问题、反凯库勒问题、条件匹配排除问题和s-限制匹配排除问题的计算复杂性.由定义,我们表明有完美匹配的二部图上的匹配排除问题和一类称作完美匹配最小障碍集问题(minimum blocker perfect matching problem)是等价的.根据二部图上的完美匹配最小障碍集问题是NP-完全的,我们证明了二部图上的匹配排除问题也是NP-完全的.我们将二部图上的匹配排除问题通过多项式时间归约为反凯库勒问题,从而证明了二部图上的反凯库勒问题也是NP-完全的.进而,我们得到条件匹配排除问题也是NP-完全的.作为条件匹配排除数定义的推广我们提出了s-限制匹配排除数(s是正整数)的概念.同时,我们也证明了二部图上的s-限制匹配排除问题是NP-完全的.在第叁章,我们研究了平衡超立方的匹配排除数和条件匹配排除数.我们得到了对于所有的正整数n,平衡超立方BHn的匹配排除数的大小均为2n,并且BHn的每个大小为2n的匹配排除集都是平凡的.进一步地,我们得到了平衡超立方的条件匹配排除数是4n-2.第四章提出了平衡超立方BEn的一个Cayley图模型,从而证明了BHn是Cayley图.这个结果推广了之前BHn是点传递的这一结果.基于此Cayley图模型,我们给出了BHn的一个最短路路由算法,第五章研究了平衡超立方BHn的限制连通性方面的一些性质.我们得到了当n≥2时,BHn的2-限制点连通度和2-限制边连通度分别为4n-2和4n-4.进一步地,我们得到了BHn的3-限制边连通度为6n-4.第六章研究了平衡超立方BHn的一类Hamiltonian路嵌入问题.由BHn是Hamiltonian laceahle的和双泛连通的,我们得到了BHn是超Hamiltonian laceable的.

(2)本文研究方法

调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。

实证研究法:依据现有的科学理论和实践的需要提出设计。

定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。

定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。

跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。

模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

超立方图论文参考文献

[1].石玲娟.(3,6)-富勒烯图与超立方图的匹配强迫和反强迫数[D].兰州大学.2015

[2].吕华众.图的条件匹配排除问题的计算复杂性和平衡超立方图的若干网络性质[D].兰州大学.2013

[3].林翠琴.超立方图和超立方有向图的同构因子分解[J].清华大学学报(自然科学版).1992

标签:;  ;  ;  ;  ;  

超立方图论文-石玲娟
下载Doc文档

猜你喜欢