一、唯一偶泛圈图的一个定理(英文)（论文文献综述）
高珊[1]（2018）在《若干互连网络的容错性与诊断性研究》文中进行了进一步梳理一个多处理器系统常被看成是互连网络图,它可能会包含成千上万个处理器.互连网络图的拓扑结构是一个简单无向连通图,处理器可以用图的点表示,处理器之间的通信情况可以用边来表示.随着互连网络图的点数增多,点的故障情况是不可避免的,因此互连网络图的容错性和故障诊断性越来越重要.条件故障集是一种特殊的故障集,它不能包含任意一个点的全部邻居.条件诊断度就是我们能准确判断出的一个互连网络图中最大的条件故障集合的顶点个数.g-好邻条件诊断就是假定任何无故障结点至少有g个无故障结点与之相邻.出于系统自行检测故障的目的,人们提出了很多不同的诊断模型,其中PMC模型和MM*模型有相当广泛的应用.容错性与诊断能力是衡量互连网络性能的极为重要的指标.本文主要研究了一些互连网络图的容错性与诊断性,并得到了以下结果:（1）主要研究焦薄饼图BPn的强匹配排除问题.我们确定了焦薄饼图BPn的强匹配排除数,并证明了焦薄饼图BPn的每一个最优强匹配排除集都是平凡的,其中n ≥ 3.（2）如果故障边或故障点的数目不超过n-2,那么n-维扭立方体Hn存在一个无故障的哈密尔顿圈;如果故障边或故障点的数目不超过n-3,那么n-维扭立方体Hn在任意无故障点对之间存在一条无故障的哈密尔顿路.（3）我们先研究n-维扭立方体Hn的Rg-点连通度,然后分别确定在PMC模型和MM*模型下n-维扭立方体Hn的g-好邻条件诊断度.（4）我们先研究局部交换扭立方体LeTQ（s,t）的Rg-点连通度,然后分别确定在PMC模型和MM*模型下局部交换扭立方体LeTQ（s,t）的g-好邻条件诊断度.
邹艳梅[2]（2018）在《关于图的Hamilton性的禁用子图条件》文中进行了进一步梳理禁用子图是图论中一类特殊的图,在图的Hamilton性研究中有着重要的应用.图的圈和路是图论中的一个重要分支,图的哈密尔顿性更是图论中研究的难题.本文对其过去以及最近的研究情况进行文献综述.本文介绍了与禁用子图哈密尔顿性相关的一些重要概念,结论及一个新的结果的证明.主要内容如下,第一章介绍基本知识点以及一般图的哈密尔顿性.第二章详细介绍了无爪图在大次和条件下的哈密尔顿性,大次和主要包括最小度条件,Fan条件,独立集条件以及Ore条件.第三章介绍了连通度下的哈密尔顿性,在这一章中将连通的定义进行了推广,给出了局部连通,N2-连通的概念及在该新条件下的主要结论.第四章给出多个禁用子图的哈密尔顿性.第五章介绍了几类比无爪图更大的图类（半无爪图,几乎无爪图,爪重图）的哈密尔顿性.在第六章中我们得到了一个邻域交条件下的Hamilton图,并给出了一个简单的证明过程.
谷梅梅[3]（2017）在《网络的连通性和诊断》文中研究指明用图来表示互连网络拓扑结构已被计算机和工程技术人员广泛运用.在本文中,"图"和"互连网络"不作区分.网络的可靠性通常用图的连通度来表示.外连通度是传统连通度的推广,更能准确的分析各种互连网络的可靠性.哈密尔顿性是设计网络时最基本的要求之一.网络故障不可避免,具有故障元素的哈密尔顿路和圈嵌入问题具有实际意义.诊断度是测量网络容错性的重要参数.本文主要研究图的外连通度,网络的容错哈密尔顿性以及故障诊断.本文的结构如下:第一章是引言部分,主要介绍图的条件连通度,网络容错哈密尔顿性以及故障诊断的研究背景.第二章,给出了本文所用到的图论的基本概念.第三章,研究了k-元立方体Qnk的外连通度.当n ≥ 3时,证明了 3-元n-立方体Qn3的3-外连通度是8n-12,其结果大概是传统连通度的4倍.当n ≥ 3和k≥4时,证明了k-元n立方体Qnk的3-外连通度是8n-9,此结果与k的取值无关.这一结论扩展了 Zhao等人关于Qn3的2-外连通度以及Hsieh等人关于Qnk的2-外连通度的结果.第四章,研究了平衡超立方体的容错哈密尔顿性.关于平衡超立方体的容错性,已知的结果大多都是只考虑故障点或者故障边.我们考虑同时具有故障点和故障边的容错性.首先证明了平衡超立方体具有故障点和故障边数目不超过2n-2并且故障点数目不超过n-1情况下的哈密尔顿圈的存在性.令Fv和Fe分别表示BHn（n≥2）中的故障点和故障边的集合.如果|Fe| + |Fv| ≤ 2n-2且|Fv|≤n-1,则BHn中存在一个无故障的长度为22n-2|Fv|的圈.其次证明了平衡超立方体在故障边数目不超过n-1的情况下具有强哈密尔顿交织性.设x和y是BHn中同一部中的任意两点.令Fe是一些故障边的集合.如果|Fe|≤n-1且n≥1,那么在BHn中存在一条无故障的长度为22n-2的从x到y路.也就是说,BHn是（n-1）-边容错强哈密尔顿交织的.第五章,主要研究网络的诊断,包括悲观诊断,条件诊断以及g-好邻诊断.第一节研究了 PMC模型下的悲观诊断.首先得到了 k-正则k-连通图类Gn在满足某些条件下的悲观诊断.作为应用,我们导出了交错群图AGn,交错群网络ANn,k-元n-立方体网络Qnk,星图Sn以及匹配组合网络MCN的悲观诊断.这些图类具有共同的特点,相邻两个点的最大公共邻点的个数小于等于2.其次,考虑了没有公共邻点个数限制的几类网络的悲观诊断,包括（n,k）-排列图An.k,（n,k）-星图Sn,k,平衡超立方体BHn,泡沫排序星图BSn,增广k-元n-立方体AQn,k以及数据中心网络Dk,n等.第二节研究数据中心网络Dk,n的条件诊断.通过分析Dk.n在至多删去n +4k-5个点后所得连通分支的情况,得到了Dk,在PMC模型和MM模型下的条件诊断分别是n + 4k-3 ≥ 2,n≥4)和n + 3k-3（k ≥ 2,n≥2）.第三节研究g-好邻诊断.令tc（G）和tg（G）分别表示图G的条件诊断度和g-好邻诊断度.对于大多数的网络,1-好邻诊断度与条件诊断度并不相等.本节主要考虑平衡超立方体BHn,得到了 BHn的1,2-好邻诊断度.并证明了其1-好邻诊断度与条件诊断度相等.第六章,总结全文并提出一些待研究的问题.
杨大伟[4]（2016）在《图的对称性和容错性分析》文中研究表明称图Γ是对称图或弧传递图,如果r的全自同构群作用在r的弧集上传递.对称图,特别是小度数对称图,常被用来设计互连网络.互连网络投入使用过程中出现故障是不可避免的,这就要求互连网络应该具有一定的容错性.而图的一些定义和性质可以用来有效的评估互连网络的容错性.本文主要研究五度对称图的分类和构造,以及讨论两类基于对称图设计的互连网络的容错性.论文结构组织如下.第1章绪论部分,主要介绍了本文所要用到的有限群论和图论的基本概念,以及与图的对称性和容错性研究相关的背景知识和本文的主要研究工作.第2章研究二倍素数阶连通五度对称图的正则覆盖.称一个连通图的正则覆盖为循环覆盖或二面体覆盖,如果其覆盖变换群分别是循环群或二面体群.如果保簇自同构群作用在覆盖图上弧传递,则称此覆盖为弧传递覆盖或对称覆盖.本章给出了二倍素数阶连通五度对称图的弧传递循环覆盖和二面体覆盖的完全分类.所有的覆盖图都是以凯莱图的形式构造出来,而且它们的全自同构群也被完全决定.第3章研究小整数倍素数幂阶五度对称图.一个连通的素数度对称图是Basic图,如果其全自同构群不包含非平凡的正规子群作用在顶点集合上有多于两个轨道.设p是一个素数.首先,我们给出了2p3阶连通五度对称图的完全分类.所有的2p3阶连通五度对称图都是某个2p3阶群上的正规凯莱图,而且其全自同构群也被完全决定.证明了当p=3时,不存在2p3阶连通的五度对称图；当p=2或5时,在同构意义下只有一个2p3阶连通的五度对称图；当p≥7时,有七个无限类图,其中六类当且仅当5 |（p-1）时存在而且为1-正则图,另外一类当且仅当5 |（p士1）时存在而且为1-传递非1-正则图.其次,我们给出了4pn阶和6pn阶连通五度Basic图的完全分类,其中n是一个非负正整数.证明了在同构意义下,只有两个4pn阶连通五度Basic图,阶分别为16和36；有五个6pn阶连通五度Basic图,阶分别为6,42,66,114和162.作为应用,我们给出了4p2,4p3和6p2阶连通五度对称图的完全分类.4p阶和6p阶连通五度对称图在[Discrete Mathematics,2011 （311）:2259-2267]中已经被分类.第4章给出了无平方因子阶连通五度对称图的一个刻画.作为应用,2pqr阶连通五度对称图被完全分类,其中r<q<p是三个奇素数.第5章研究n-维超立方体网络Qn和n-维平衡超立方体网络BHn的容错性分析.首先,我们从容错圈嵌入方面分析Qn的容错性.设F是Qn的一个错误集,fv,和fe分别是F中错误顶点和错误边的个数.称一条边e是自由边,如果e以及其两个端点均不在F中.图Γ的一个圈是无错圈,如果它既不包含F中的点又不包含F中的边.我们证明了当n≥3时,如果fv+fe≤2n-5,fe≤n-2且每个无错顶点至少关联两条自由边,那么Qn的每条自由边都位于长从6到2n -2fv的无错偶圈中.这一结论证实了Tsai在[Information Processing Letters,2007（102）:242-246]中提出的一个猜想.最后,我们从外连通度方面分析BHn的容错性,其中n≥2.连通图Γ的h-外、连通度,记为Kh（Γ）,是指去掉最少的顶点的个数使得Γ不连通且每个连通分支至少含有h+1个顶点Yang在[Applied Mathematics and Computation,2012（219）:970-975]中证明了K1（BHn）=4n-4.本章,我们推广了Yang关于BHn的外连通度的结论,证明了κ2（BHn）=κ3（BHn）=4n-4,κ4（BHn）=κ5（BHn）=6n-8,以及给出了κh（BHn）的一个上界,其中h≤2n-1.第6章讨论一些有待研究的问题.
高晓慧[5]（2016）在《环面网络关于圈嵌入的边容错性》文中认为计算机或通信系统中各个元件之间不同的连接方式被称为该系统的互连网络。人们一般将互连网络看作一个图,图中顶点代表网络中的处理器,边代表处理器之间的通信线路。随着大型网络中处理器的不断增加,故障的出现也变得越来越频繁,保证信息仍然能够在故障系统的不同处理器之间顺利传递的容错性便成为了一个非常关键的问题。因此,研究新的故障模式对设计互连网络拓扑以便容纳更多的故障通信单元是十分必要的。在网络拓扑中,圈作为结构最基础的类别之一,它的可嵌入性对解决一些优化问题是至关重要的,因为它代表了许多并行算法的数据流结构。本文针对两类特殊的环面网络,研究其边容错性与圈嵌入问题。对于二维环面网络,主要研究了边容错和最长圈嵌入问题。并得到结果:在具有至多4条故障边的二维环面网络Torus（m,n）（其中m,n≥5是整数）中,如果满足两个容错条件（1）任意一个顶点的度至少是2,与（2）不存在禁止4圈,那么它是哈密尔顿的。对于二元n维环面网络（即n维超立方体,记为Qn,其中整数n≥2）,考虑了边容错和偶圈嵌入问题。并得到结果:在具有至多3n-8条故障边的Qn（n≥5是整数）中,如果满足两个容错条件（1）任意一个顶点的度至少是2,与（2）不存在禁止4圈,那么Qn中存在长度从4到|V（Qn）| 的无故障偶圈。此外,对于n维超立方体的容错哈密尔顿圈嵌入方面,将n维超立方网络保持哈密尔顿性所允许的故障边数从3n-8提升到3n-7。证明了具有至多3n-7条故障边的n维超立方体Qn（n≥6是整数）,在满足两个容错条件（1）任意一个顶点的度至少是2,与（2）不存在禁止4圈和禁止6圈下,仍然是哈密尔顿的。
樊昊[6]（2013）在《拟阵圈图的性质和图的染色问题》文中指出图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象。一个连通图的树图能够反映该图的不同支撑树之间的变换关系。因此,研究一个图的树图有助于我们更好地了解该图的性质。同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系。因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质。近些年来,树图和拟阵的基图被推广得到了一些新的图。为了研究拟阵中圈图的性质,P.Li和G.Liu提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中的路、圈的性质。我们继续对拟阵圈图的性质进行了研究,着重研究了拟阵圈图的边、点容错哈密尔顿性。一个拟阵M就是对于一个有限集E,令C为集合E中非空子集族,它满足如下的公理：（C1）（?）C.（C2）若C1,C2∈C且C1（?）C2,则C1=C2。（C3）若C1≠C2,C1,C2∈C并且存在e∈C1∩C2,则恒有C3∈C满足C3（?）（C1（?） C2）-e.那么我们称M=（E,C）为定义在元素集E上的拟阵。当C∈C（M）,我们称C为M的一个圈。如果M的一个圈只有一个元素,则称之为M的一个环。如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元。如果M既没有环也没有平行元,则称M是一个简单拟阵。如果一个元素含在M的任一基中,则称之为M的一个反圈。如果S是E的一个子集,且对任意的圈C,都有C（?）S或者C（?）E＼S.则称S为M的一个分离集.显然E和（?）都是M的分离集。^M的极小分离集称为M的一个分支。如果拟阵M只有一个分支,则称"为连通拟阵.设e∈E,则M／e和M＼e分别表示由拟阵M经过收缩和约束e后所得到的拟阵。拟阵M=（E,B）的基图是这样的一个图G,其中V（G）=B,E（G）={B1B2|B1,B2∈B,|B,＼B2|=1},这里图G的顶点和M的基用同样的符号表示。设G是一个图,图G的点集和边集分别记为V（G）和E（G）,令v（G）=|V（G）|。包含G的每个点的路称为G的一条哈密尔顿路；同样的,包含G的每个点的圈称为G的一个哈密尔顿圈。如果一个图存在一个哈密尔顿圈,则称之为哈密尔顿的。如果对于一个图G的任意两个顶点来说,G都有-条哈密尔顿路连接他们,则称G是哈密尔顿连通的。如果对一个图G的任意一条边来说,G都有一个含这条边的哈密尔顿圈,则称G是边哈密尔顿的,或者称G是正哈密尔顿的,写作G∈H+。如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密尔顿圈,则称G是负哈密尔顿的,写作G∈H-。如果G既是正哈密尔顿的,又是负哈密尔顿的,我们称G是一致哈密尔顿的。如果对于图G的任意两条边,均存在一一个哈密尔顿圈包含他们,这个图G就被称为Ez-哈密尔顿的。一个图G被称为k-点容错哈密尔顿的,如果在任意删除不多于k个顶点以后,图仍然是哈密尔顿的,即在余图中仍然存在哈密尔顿圈。类似的,个图G被称为k-边容错哈密尔顿的,如果在任意删除不多于k条边以后,图仍然是哈密尔顿的。现在我们给出拟阵圈图的概念。定义拟阵M的圈图G=G（M）的顶点集V（G）=C,边集E（G）={CC′|C,C′∈C,|C∩C′|≠0}。这里C和C′既代表G的顶点,也代表M的圈。对于一个图G=（V,E）,它的一个t-顶点染色,或者t-染色,是指图G的一个从顶点集V到颜色集{1,2…,t}的映射c。如果染色c对于G中的每一条边uu都满足c（u）≠c（u）,则称染色c是G的一个正常t-顶点染色且G是可t-染色的.在染色c下,具有相同颜色的顶点构成的集合称为一个色类。如果图G的某个t-顶点染色c的每个色类在G中都能导出一个最大度至多为k的森林,则称c是图G的一个k-森林t-染色。如果G的一个正常t-顶点染色c的任意两个色类的基数之差的绝对值至多为1,则称c是图G的均匀t-顶点染色。图的强均匀染色数χeq*（G）是这样一个整数t的最小值,它使得图G对于每个不小于t的整数t’,都具有一个均匀t’-染色。关于图的强均匀染色数,有一个着名的Chen-Lih-Wu猜想（又称为均匀△-染色猜想）,它认为,如果图G是一个连通图,并且G既不是完全图,也不是奇圈,还不是完全二分图K2m+1,2m+1,则χeq*（G）≤△（G）。本文主要研究的是拟阵圈图的边容错哈密尔顿性,点容错哈密尔顿性以及一般图的森林均匀染色问题,全文共分为四章。第一章给出了一个相对完整的简介。首先介绍一些图论中的基本术语和定义,然后给出了关于树图,拟阵基图以及森林图的一个简短但相对完整的综述,最后,给出了本文的主要结论。第二章我们研究了拟阵圈图中的哈密尔顿圈性质。首先我们给出了一个对于拟阵圈图的简短的介绍。然后我们证明了拟阵圈图的E2-哈密尔顿性。在这一章的最后,我们讨论了拟阵圈图的边容错哈密尔顿性。第三章主要讨论拟阵圈图的点容错哈密尔顿性。同样的,首先,给出了对于拟阵圈图容错哈密尔顿性的一个简短的介绍。然后我们讨论了拟阵圈图的点容错哈密尔顿性,并给出证明。第四章主要讨论一般图的森林均匀染色问题。在这一章里,我们首先给出了对于均匀染色的一个简短的介绍。之后,我们讨论了一般图的森林均匀染色问题,并且给出了一个多项式时间算法去构建这样的染色。
刘敏[7]（2012）在《Enhanced Hypercube的容错性质研究》文中指出随着并行计算机互联网络规模的不断扩大，互联网络中处理器或处理器链路发生故障的情形是不可避免的，这就要求网络具有一定的容错性．网络容错性是指当网络中若干结点和（或）连线发生故障时网络仍能继续有效的工作，因此计算机互联网络的容错性研究变得越来越重要．容错泛圈，容错直径，容错哈密顿性等都是度量网络容错性的参数．本文主要研究加强超立方体Enhanced Hypercube的点边容错性质，讨论容错加强超立方体中路和圈的嵌入情况.论文主要分为四章，研究加强超立方体的某些容错性质：条件情况下和标准情况下的边容错性质、点容错性质、超哈密尔顿脆弱性质等.第一章主要介绍图相关的基本概念，几个着名的互联网络以及泛连通性，哈密尔顿连通性，容错泛圈性，容错哈密尔顿性，强哈密尔顿性限制连通度的定义以及目前已经取得的一些结果.第二章主要研究了加强超立方体的条件边容错奇偶泛圈的嵌入问题以及边容错超哈密尔顿脆弱问题，得到了以下两个结论：（1）给出了加强超立方体Qn,k的条件边容错泛圈性，证明了加强超立方体Qn,k（n≥3）有至多（2n-3）条故障边，其中每一个点至少与两条非故障边相连，且n和k有相同（不同）的奇偶性，那么在Qn,k中存在偶长为4到2n的的容错圈（存在偶长为4到2n的的容错圈以及奇长为n-k+2到2n-1的的容错圈）.这就将折叠超立方体的条件边容错泛圈性进行了推广.（2）证明了加强超立方体Qn,k的边容错超哈密顿脆弱性：加强超立方体Qn,k（1≤k≤n-1），当n （≥3）和k （1≤k≤n-1）有相同的奇偶性时，是（n-2）-边容错超哈密顿脆弱的.第三章主要研究了加强超立方体的点容错泛圈性以及点容错最长路的嵌入问题，进一步地，研究了其点边容错路和圈的嵌入，得到了以下几个结果：（1）2-点容错泛圈嵌入加强超立方体和（n2）-点容错最长圈嵌入加强超立方体；（2）点边容错情况下最长路嵌入和容错圈嵌入加强超立方体.第四章我们对全文的工作进行了总结，并且提出了一些仍需要进一步研究的问题.
邓爱华[8]（2011）在《交叉立方体的容错泛圈性研究》文中研究说明对简单图G=（V,E）, F是图G中边或者点的子集。F为图中出现的错误数,确定一个网络结构中出现错误的最大值为多少时剩余子网络（即由VF与EF构成的子网络）任意一个顶点或边之间还能进行有效通信,就是对这个网络容错泛圈性的研究,即如果此时图中任意顶点或边还能找到围长至顶点个数的圈,那么这个图抽象出的网络结构就具有容错泛圈性,记fv为错误的顶点数,fe为错误的边数。研究图的容错泛圈性在很多领域具有广泛的应用,例如不影响通信的情况下去掉某些设备以节省资源；分布式系统中多任务消息传输的有效性问题等等都可以转化为图的容错泛圈性问题。一个大型网络在投入使用的过程中,它的某些组件和连线难免会发生故障。鉴于其理论和实际意义,本文通过计算机构造和数学推理证明相结合的方法,研究了交叉立方体CQn的边容错点泛圈性和容错点泛圈性质,给出了交叉立方体网络结构可以保证正确设备正常通讯时出现错误的上界。设fe是CQn中错误边的个数,fv,是CQn中错误点的个数,我们得到了以下结论：（1）当fe≤n-3时,对交叉立方体CQn任意顶点u都可以找到长度为6到2n的圈,且顶点u落在这些圈上。（2）当fe+fv≤n-3时,对交叉立方体CQn任意顶点u都可以找到长度为8到2n-fv的圈,且顶点u落在这些圈上。
薛占军[9]（2010）在《几类互连网络的容错哈密顿性》文中研究说明将互连网络中的每个处理器抽象成一个点,把处理器之间的信道抽象成两点之间的连线,那么一个互连网络就可以抽象成一个图,称之为互联网络拓扑结构,网络的拓扑结构决定着该网络的性能.由于互联网络的拓扑结构就是图,所以图论是设计和分析互连网络的最基本且强有力的数学工具.可嵌入性是衡量网络优劣的一个重要性能.由于用含有圈拓扑结构的图设计出来的网络通讯成本低,而且泛圈性和泛连通性也可以看成是图的哈密顿性研究的扩展,因此圈嵌入是一个重要问题.由于网络的节点和链接都可能发生故障,所以需要研究网络的容错性,这是评估网络性能时所考虑的主要因素之一交替群图作为计算机系统的一种互联网络拓扑结构,具有许多比超立方体和星图更好的性质,也符合网络设计高性能、低成本的原则要求.本文研究了交替群图等几类着名互联网络的容错圈嵌入、最大边连通、网络设计等问题,主要研究工作如下：（1）研究了交替群图的容错哈密顿性和容错哈密顿连通性.对于一个n-维交替群图AGn,证明了当n≥4时,AGn是（2n-6）-容错哈密顿和（2n-6）-容错泛圈的,并且是（2n-7）-容错哈密顿连通的.本文所给的结果关于交替群图的正则度是最优的,也是对以前J.-M.Chang等人所给结果的改进.（2）定义了匹配组合网络G=G（V1UV2,E1UE2UM）,其中M是V1和V2之间的一个完全匹配.研究了G的限制连通度,G的直径的上下界与G1的直径、G2的直径和完全匹配M的关系,通过G1和G2的阶确定了几类特殊匹配组合网络G直径的上下界,最后讨论了G1和G2的泛圈性和泛连通性与G的泛圈性和泛连通性之间的关系.（3）用凸函数的性质和数论知识研究了连通图的倒数度的上界,给出了一个连通图是最大边连通的条件,为研究超连通或超边连通图提供了新的方法,通过例子说明所给结果用于判断一个连通图是否是最大边连通图是有效的.（4）线图方法、笛卡儿乘积方法和代数方法是互联网络设计常用的三种方法.本文用代数方法对任何含有最小元素的偏序集P,定义了其相关联零因子图G（P）,证明了如果G（P）的色数X（G（P））和团数ω（G（R））是有限的,那么χ（G（P））=ω（G（P））=n+1,其中n是P的极小素理想的个数.
李萍[10]（2010）在《拟阵圈图的一些性质》文中指出图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不同支撑树之间的变换关系.因此,研究一个图的树图有助于我们更好地了解该图的性质.同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系.因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质.近些年来,树图和拟阵的基图被推广得到了一些新的图.为了研究拟阵中圈图的性质,我们提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中圈的性质,路的性质,并且把圈图的概念推广为n阶圈图,并得到了n阶圈图的一些性质。设E是一个有限集.如果S1,S2（?）E,那么S1-S2={χ（?）χ∈S1和x（?）S2}.一个拟阵M就是一个有限集E以及E的一个非空子集族（?）,且满足以下条件：（C1）若C1,C2∈（?）且C1（?）C2,则C1=C2.（C2）设C1,C2∈（?）并且a,b∈E.若a∈C1∩C2且b∈C1-C2,则存在C3∈（?）满足b∈C3（?）（C1∪C2）-{a}.当C∈（?）（M）,我们称C为M的一个圈.如果M的一个圈只有一个元素,则称之为M的一个环.如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元.如果M既没有环也没有平行元,则称M是一个简单拟阵.如果一个元素含在M的任一基中,则称之为M的一个反环.如果S是E的一个子集,且对任意的圈C,都有C（?）S或者C（?）E＼S.则称S为M的一个分离集.显然E和（?）都是M的分离集.M的极小分离集称为M一个分支.如果拟阵M只有一个分支,则称M为连通拟阵.设e∈E,则M·e和M△e分别表示由拟阵M经过收缩和删除e后所得到的拟阵.拟阵M=（E,（?））的基图是这样一个图G,其中V（G）=（?）,E（G）={B1B2：B1,B2∈（?）,且|B1＼B2|=1},这里图G的顶点和M的基用同样的符号表示.设G是一个图,图G的点集和边集分别记为V（G）和E（G）,令v（G）=|V（G）|.包含G的每个点的路称为G一条哈密顿路；同样地,包含G的每个点的圈称为G一个哈密顿圈.如果个图存在一个哈密顿圈,则称之为哈密顿的.如果对一个图G的任意两个顶点来说,G都有一条哈密顿路连接它们.则称G是哈密顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密顿圈,则称G是边哈密顿的,或者称G是正哈密顿的,记为G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密顿圈,则称G是负哈密顿的,记为G∈H-.如果G既是正哈密顿的,又是负哈密顿的,我们称G是一致哈密顿的。一个有n个顶点的图G称为顶点泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一个顶点,G都存在一个过该顶点的长度为k的圈.一个有n个顶点的图G称为边泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一条边,G都存在一个长度为k的圈包含这条边.现在我们给出拟阵圈图的概念.定义拟阵M的圈图G=G（M）的顶点集V（G）=（?）,边集E（G）={CC′|C，C′∈（?）,|C∩C′|≠0}。这里C和C′既代表G的顶点,也代表M的圈.定义拟阵M的k阶圈图Ck（M）的顶点集为V（Ck（M））=（?）（M）.两个顶点C,C′∈（?）（M）在Ck（M）中相邻当且仅当在M中|C∩C′|≥k.为了符号表示方便,我们既用C表示Ck（M）的顶点,也用C表示M中的圈.本文分为五章.第一章给出关于树图,拟阵基图以及森林图的一个简短但相对完整的综述.第二章给出拟阵圈图的概念,并讨论拟阵圈图的连通度和边连通度.第三章我们深入讨论了拟阵圈图的哈密顿性,边泛圈性以及圈图中顶点不交圈的性质.第四章讨论了拟阵圈图中路的性质.第五章我们给出了拟阵的圈图的定义,并讨论了它的直径和连通度.下面列出本文的主要结果.结论1设G=G（M）是一个连通拟阵M的圈图,而且B是M的一个基,则G的连通度k（G）≥2|E-B|-2.结论2设G=G（M）是一个连通拟阵M的圈图,而且G的最小度是δ（G）,则δ（G）≥2|E-B|-2.结论3设G=G（M）是一个连通拟阵M的圈图,而且G的最小度是δ（G）,则G的边连通度k′（G）=δ（G）.结论4设G=G（M）是一个连通拟阵M的圈图,而且M含有至少三个圈,则G=G（M）是边泛圈的.结论5设G=G（M）是一个连通拟阵M的圈图,而且M含有至少四个圈,则G是一致哈密顿的.结论6设G=G（M）是一个连通拟阵M的圈图,如果|V（G）|=n并且k1+k2+…+kp=n（ki为整数,ki≥3,i=1,2,…,p）,则G有一个2-因子F包含p个顶点不交的圈D1,D2,…,Dp而且圈Di的长度为ki（i=1,2,…,p）.结论7设G=G（M）是一个连通拟阵M的圈图,而且M含有至少三个圈,则G的直径不超过2.并且,d（G（M））=2当且仅当M中有两个没有公共元素的圈.结论8设G=G（M）是一个连通拟阵M的圈图,如果|V（G）|=n并且C1,C2∈V（G）,则对于任意的k满足2≤k≤n-1,存在一条长度为k的路连接C1和C2.结论9设M是一个连通简单拟阵.则如下结论成立.（ⅰ）C2（M）是连通的.（ⅱ）如果M没有一个约束子拟阵同构于U2,6,则在C2（M）中任何两个不相邻的顶点C1和C2有一个公共邻点C3.（ⅲ）C2（M）的直径不超过2当且仅当对于任何边集合X（?）E,M在X上的约束子拟阵都不同构于U2,6.结论10设M是一个包含至少两个圈的连通简单拟阵,且M不是一条线,则C2（M）是2-连通的.
二、唯一偶泛圈图的一个定理(英文)（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、唯一偶泛圈图的一个定理(英文)（论文提纲范文）
（1）若干互连网络的容错性与诊断性研究（论文提纲范文）
| 摘要 |
| ABSTRACT(英文摘要) |
| 第一章 综述 |
| §1.1 基本概念和符号 |
| §1.2 图的匹配排除 |
| §1.3 图的容错哈密尔顿性 |
| §1.4 图的R~g-点连通度 |
| §1.5 网络的诊断模型 |
| 第二章 焦薄饼图的强匹配排除 |
| §2.1 焦薄饼图的简介 |
| §2.2 图的强匹配排除 |
| §2.3 焦薄饼图的性质 |
| §2.4 确定smp(BP_n)的值 |
| 第三章 扭立方体的容错哈密尔顿圈与路 |
| §3.1 扭立方体的简介 |
| §3.2 主要引理 |
| §3.3 定理3.1的证明 |
| 第四章 扭立方体的g-好邻条件诊断 |
| §4.1 t-可诊断的充分必要条件 |
| §4.2 扭立方体的子图的性质 |
| §4.3 扭立方体的R~g-点连通度 |
| §4.4 扭立方体的g-好邻条件诊断度 |
| §4.4.1 PMC模型下,t_g(H_n)的值 |
| §4.4.2 MM~*模型下,t_g(H_n)的值 |
| 第五章 局部交换扭立方体的g-好邻条件诊断 |
| §5.1 局部交换扭立方体的简介 |
| §5.2 局部交换扭立方体的性质 |
| §5.3 局部交换扭立方体的R~g-点连通度 |
| §5.4 局部交换扭立方体的g-好邻条件诊断度 |
| §5.4.1 PMC模型下,t_g(LeTQ(s,t))的值 |
| §5.4.2 MM~*模型下,t_g(LeTQ(s,t))的值 |
| 参考文献 |
| 博士期间完成的论文 |
| 致谢 |
（2）关于图的Hamilton性的禁用子图条件（论文提纲范文）
| 中文摘要 |
| 英文摘要 |
| 第一章 绪论 |
| §1.1 引言 |
| §1.2 基本概念与符号 |
| §1.3 禁用子图 |
| §1.4 一般图的Hamilton性 |
| §1.5 本文主要内容 |
| 第二章 禁用子图在大大次和条件下的Hamilton性 |
| §2.1 无爪图在最小度条件下的Hamilton性 |
| §2.2 无爪图在Fan条件下的Hamilton性 |
| §2.3 无爪图在独立集条件下的Hamilton性 |
| §2.4 无爪图在Ore条件下的Hamilton性 |
| 第三章 连通,局部连通条件下的Hamilton性 |
| §3.1 连通度下的Hamilton性 |
| §3.2 局部连通下的Hamilton性 |
| 第四章 多禁用子图图条件下图的Hamilton性 |
| 第五章 几类无爪图的推广图的Hamilton性 |
| §5.1 半无爪图的Hamilton性 |
| §5.2 几乎无爪图的Hamilton性 |
| §5.3 爪重图的Hamilton性 |
| 第六章 一个Hamilton图邻域交条件 |
| §6.1 主要结论 |
| §6.2 主要证明过程 |
| 参考文献 |
| 致谢 |
（3）网络的连通性和诊断（论文提纲范文）
| 致谢 |
| 摘要 |
| 英文摘要 |
| 1 绪论 |
| 1.1 引言 |
| 1.2 研究背景 |
| 1.3 主要结论 |
| 2 基本概念 |
| 2.1 图的基本概念和符号 |
| 2.2 图的连通度 |
| 2.3 图的可诊断度 |
| 3 k-元n-立方体的条件连通度 |
| 3.1 预备知识 |
| 3.1.1 k-元n-立方体的定义 |
| 3.1.2 k-元n-立方体的性质 |
| 3.2 3-元n-立方体的3-外连通度 |
| 3.3 k-元n-立方体的3-外连通度 |
| 4 平衡超立方体网络的容错哈密尔顿性 |
| 4.1 预备知识 |
| 4.1.1 平衡超立方体的定义 |
| 4.1.2 平衡超立方体的性质 |
| 4.2 平衡超立方体的(2n-3)-点和边容错哈密尔顿性 |
| 4.3 平衡超立方体的(2n-2)-点和边容错哈密尔顿性 |
| 4.4 平衡超立方体的(n-1)-边容错强哈密尔顿交织性 |
| 5 网络的诊断 |
| 5.1 某些图类的悲观诊断 |
| 5.1.1 预备知识 |
| 5.1.2 某些正则图类G_n的悲观诊断 |
| 5.1.3 (n,k)-排列图A_(n,t)的悲观诊断 |
| 5.1.4 (n,k)-星图S_(n,k)的悲观诊断 |
| 5.1.5 平衡超立方体BH_n的悲观诊断 |
| 5.1.6 增广k-元n-立方体的悲观诊断 |
| 5.1.7 泡沫排序星图BS_n的悲观诊断 |
| 5.1.8 数据中心网络D_(k,n)的悲观诊断 |
| 5.2 数据中心网络的条件诊断 |
| 5.2.1 预备知识 |
| 5.2.2 数据中心网络D_(k,n)的容错性 |
| 5.2.3 数据中心网络D_(k,n)的条件诊断 |
| 5.3 g-好邻诊断 |
| 5.3.1 预备知识 |
| 5.3.2 平衡超立方体BH_n的1,2-好邻诊断 |
| 6 结论 |
| 参考文献 |
| 作者简历及攻读博士学位期间取得的研究成果 |
| 学位论文数据集 |
（4）图的对称性和容错性分析（论文提纲范文）
| 致谢 |
| 中文摘要 |
| 英文摘要 |
| 1 绪论 |
| 1.1 引言 |
| 1.2 基本概念 |
| 1.3 研究背景 |
| 1.3.1 图的对称性 |
| 1.3.2 图的容错性分析 |
| 2 倍素数阶五度对称图的弧传递循环覆盖和二面体覆盖 |
| 2.1 预备知识 |
| 2.2 几类凯莱图的构造 |
| 2.3 Dip_5的弧传递覆盖 |
| 2.4 二倍素数阶连通五度对称图的弧传递Z_n-覆盖 |
| 2.5 二倍素数阶连通五度对称图的弧传递D_n-覆盖 |
| 2.6 覆盖的全自同构群 |
| 2.7 小结 |
| 3 小整数倍素数幂阶五度对称图 |
| 3.1 预备知识 |
| 3.2 几类小整数倍素数幂阶连通五度对称图 |
| 3.3 二倍素数立方阶五度对称图 |
| 3.4 四倍素数幂阶五度对称图 |
| 3.5 六倍素数幂阶五度对称图 |
| 3.6 小结 |
| 4 无平方因子阶五度对称图 |
| 4.1 预备知识 |
| 4.2 几类无平方因子阶五度对称图的构造 |
| 4.3 无平方因子阶五度对称图的刻画 |
| 4.4 2pqr阶五度对称图的完全分类 |
| 4.5 小结 |
| 5 两类对称图的容错性分析 |
| 5.1 预备知识 |
| 5.1.1 超立方体的概念和性质 |
| 5.1.2 平衡超立方体的概念和性质 |
| 5.2 超立方体的划分和无错圈的构造 |
| 5.3 低维超立方体的容错圈嵌入 |
| 5.4 条件错误模型下超立方体的容错边偶泛圈性 |
| 5.5 平衡超立方体的外连通度 |
| 5.6 小结 |
| 6 结论 |
| 参考文献 |
| 作者简历及攻读博士学位期间取得的研究成果 |
| 学位论文数据集 |
（5）环面网络关于圈嵌入的边容错性（论文提纲范文）
| 中文摘要 |
| ABSTRACT |
| 第一章 引言 |
| 1.1 应用背景 |
| 1.2 图论中的基本概念、记号和术语 |
| 1.3 三类边容错模型 |
| 1.4 本文研究的主要内容和结果 |
| 1.4.1 二维环面和超立方体网络的容错哈密尔顿性 |
| 1.4.2 超立方体网络的容错偶泛圈性 |
| 第二章 二维环面网络的边容错哈密尔顿性 |
| 2.1 相关概念和性质 |
| 2.2 Row-Torus(m,2n+1)的边容错哈密尔顿性 |
| 2.3 二维环面网络Torus(m,n) 的边容错哈密尔顿性 |
| 第三章 超立方体的边容错偶泛圈性 |
| 3.1 相关概念和性质 |
| 3.2 长为4到2~(n-1)+2的偶圈构造 |
| 3.3 长为2~(n-1)+ 到 2~n-2的偶圈构造 |
| 第四章 具有3n -7 条故障边的超立方体的哈密尔顿性 |
| 4.1 相关概念与性质 |
| 4.2 预备工作 |
| 4.3 边容错超立方体的哈密尔顿性 |
| 第五章 结论 |
| 5.1 主要内容与结论 |
| 5.2 下一步工作 |
| 参考文献 |
| 致谢 |
| 攻读学位期间发表的学术论文目录 |
（6）拟阵圈图的性质和图的染色问题（论文提纲范文）
| 目录 |
| 中文摘要 |
| 英文摘要 |
| 第一章 绪论 |
| 1.1 基本概念 |
| 1.2 拟阵的基图 |
| 1.3 树图和其他衍生图 |
| 1.4 拟阵的基关联图 |
| 1.5 图的均匀染色 |
| 1.6 本文的主要结果 |
| 第二章 拟阵圈图的边可攻击哈密尔顿性 |
| 2.1 相关定义及背景介绍 |
| 2.2 引理 |
| 2.3 主要定理 |
| 第三章 拟阵圈图的点可攻击性 |
| 3.1 相关定义及背景介绍 |
| 3.2 引理 |
| 3.3 主要定理 |
| 第四章 图的松弛均匀染色 |
| 4.1 图的松弛均匀染色 |
| 4.2 当d=1时,关于定理4.1.10(a)的一个多项式时间算法 |
| 参考文献 |
| 致谢 |
| 攻读博士学位期间完成论文情况 |
| 作者简介 |
| 学位论文评阅及答辩情况表 |
（7）Enhanced Hypercube的容错性质研究（论文提纲范文）
| 内容摘要 |
| Abstract |
| 引言 |
| 1 绪论 |
| 1.1 图的相关基本概念 |
| 1.2 超立方体网络及其变型简介 |
| 1.3 图的容错性的研究意义 |
| 2. Enhanced Hypercube 的边容错性研究 |
| 2.1 引言 |
| 2.2 相关定义及引理 |
| 2.3 Enhanced Hypercube 的条件边容错泛圈性 |
| 2.4 Enhanced Hypercube 的超哈密顿脆弱性 |
| 2.5 本章小结 |
| 3 Enhanced Hypercube 的点边容错性研究 |
| 3.1 引言 |
| 3.2 相关概念和引理 |
| 3.3 Enhanced Hypercube 的点容错泛圈性 |
| 3.4 Enhanced Hypercube 中点边容错最长路的嵌入 |
| 3.5 本章小结 |
| 4 全文总结与展望 |
| 4.1 全文总结 |
| 4.2 展望 |
| 参考文献 |
| 后记 |
| 附录：攻读硕士学位期间发表的部分学术论着 |
（8）交叉立方体的容错泛圈性研究（论文提纲范文）
| 摘要 |
| 英文摘要 |
| 引言 |
| 1 基本概念和预备知识 |
| 1.1 图论的基本概念 |
| 1.2 图的嵌入 |
| 1.3 联网络及其背景 |
| 1.3.1 互联网络拓扑结构 |
| 1.3.2 互联网络与图 |
| 1.3.3 容错问题和研究现状 |
| 1.4 本章小结 |
| 2 几种常用的网络 |
| 2.1 超立方体网络 |
| 2.2 折叠立方体网络 |
| 2.3 M(?)bius立方体网络 |
| 2.4 增广立方体网络 |
| 2.5 局部扭立方体 |
| 2.6 本章小结 |
| 3 交叉立方体的容错泛圈性 |
| 3.1 数学归纳法及搜索算法 |
| 3.1.1 数学归纳法 |
| 3.1.2 搜索算法 |
| 3.1.3 图的存储 |
| 3.2 交叉立方体定义及其性质 |
| 3.3 交叉立方体两点之间距离的一个重要公式 |
| 3.4 定理证明 |
| 3.4.1 交叉立方体边容错点泛圈性的证明 |
| 3.4.2 交叉立方体容错点泛圈性的证明 |
| 3.5 本章小结 |
| 结论 |
| 参考文献 |
| 攻读硕士学位期间发表学术论文情况 |
| 致谢 |
（9）几类互连网络的容错哈密顿性（论文提纲范文）
| 符号说明 |
| 摘要 |
| Abstract |
| 第一章 绪论与预备知识 |
| 1.1 组合网络容错分析研究的背景 |
| 1.2 组合网络容错研究的现状 |
| 1.3 群论和图论的基本概念 |
| 1.4 本文内容的结构安排 |
| 第二章 交替群网络的容错性分析 |
| 2.1 引言 |
| 2.2 交替群图AG_n的定义和性质 |
| 2.3 交替群图AG_n的容错哈密顿连通性和容错哈密顿性 |
| 2.4 交替群图AG_n的容错泛圈性 |
| 2.5 交替群图AG_n与排列图A_(n,k)的关系 |
| 第三章 匹配组合网络的容错性与传送延迟 |
| 3.1 引言 |
| 3.2 匹配组合图的连通度与容错性 |
| 3.3 匹配组合图直径的上下界与传送延迟 |
| 3.4 匹配组合图的泛圈性和泛连通性 |
| 第四章 关于图最大边连通的条件 |
| 4.1 引言及预备知识 |
| 4.2 连通图是最大边连通的条件 |
| 第五章 关于偏序集相关联图的性质 |
| 5.1 引言及预备知识 |
| 5.2 相关联零因子图的定义及例子 |
| 5.3 偏序集的相关联零因子图的理想、色数和团数 |
| 5.4 偏序集上的零因子图的判定 |
| 结束语 |
| 致谢 |
| 参考文献 |
| 在读博士期间撰写(发表)的论文 |
| 参加的科研项目 |
（10）拟阵圈图的一些性质（论文提纲范文）
| 中文摘要 |
| 英文摘要 |
| 符号说明 |
| 第一章 绪论 |
| 1.1 基本定义和符号 |
| 1.2 拟阵基图 |
| 1.3 树图及其它图 |
| 1.4 拟阵基关联图 |
| 1.5 与拟阵相关的图的染色数 |
| 第二章 拟阵圈图的连通度 |
| 2.1 简介 |
| 2.2 预备知识 |
| 2.3 拟阵圈图的连通度与最小度 |
| 2.4 拟阵圈图的边连通度 |
| 第三章 拟阵圈图中的圈 |
| 3.1 简介 |
| 3.2 预备知识 |
| 3.3 拟阵圈图的边泛圈性 |
| 3.4 拟阵圈图中的哈密顿圈 |
| 3.5 拟阵圈图中的顶点不交圈 |
| 第四章 拟阵圈图中的路 |
| 4.1 简介 |
| 4.2 定理4.2.3的证明 |
| 第五章 拟阵2阶圈图的连通度和直径 |
| 5.1 简介 |
| 5.2 预备知识 |
| 5.3 定理5.3.3的证明 |
| 参考文献 |
| 致谢 |
| 作者简介 |
| 学位论文评阅及答辩情况表 |
四、唯一偶泛圈图的一个定理(英文)（论文参考文献）
- [1]若干互连网络的容错性与诊断性研究[D]. 高珊. 湖北大学, 2018(04)
- [2]关于图的Hamilton性的禁用子图条件[D]. 邹艳梅. 华东师范大学, 2018(01)
- [3]网络的连通性和诊断[D]. 谷梅梅. 北京交通大学, 2017(09)
- [4]图的对称性和容错性分析[D]. 杨大伟. 北京交通大学, 2016(10)
- [5]环面网络关于圈嵌入的边容错性[D]. 高晓慧. 太原科技大学, 2016(12)
- [6]拟阵圈图的性质和图的染色问题[D]. 樊昊. 山东大学, 2013(10)
- [7]Enhanced Hypercube的容错性质研究[D]. 刘敏. 三峡大学, 2012(01)
- [8]交叉立方体的容错泛圈性研究[D]. 邓爱华. 大连理工大学, 2011(07)
- [9]几类互连网络的容错哈密顿性[D]. 薛占军. 西安电子科技大学, 2010(05)
- [10]拟阵圈图的一些性质[D]. 李萍. 山东大学, 2010(09)