张启龙[1]2006年在《几类特殊图的脆弱性参数》文中进行了进一步梳理在设计计算机网络和通讯网络时,为了避免和最大限度减少因网络通讯中断而带来的损失,设计者必须考虑网络的稳定性。因此网络设计的基本思想之一便是使其在受到外部攻击时,不容易被破坏,更进一步,如果真的受到破坏,它们也比较容易被修复重建。一个计算机网络或者通讯网络,可以用一个连通图来表示,其中图的顶点表示通讯站,边表示两个通讯站之间可以直接通讯的通讯线路。对于一个网络,它的稳定性常用它所对应的图的脆弱性参数描述。 早期在脆弱性参数方面的研究,主要是围绕连通度和边连通度展开的。这两个参数被广泛的使用来描述图的脆弱性,而且已被证明,存在多项式时间算法计算一个图的连通度和边连通度。由于这两个参数在描述图的脆弱性方面具有局限性,近来人们陆续引入了一些其它的脆弱性参数,主要包括了坚韧度和边坚韧度,离散数,完整度和边完整度,粘连度和边粘连度,毁裂度,邻域连通度和边邻域连通度,邻域完整度和边邻域完整度,邻域离散数和边邻域离散数。与连通度和边邻域连通度不同,这些参数不仅考虑了破坏网络的难易程度,还考虑了网络遭受破坏的程度。 但已被证明的是计算一般图的这些参数是NP-困难问题。因此研究特殊图类的这些参数就十分有意义。在本文中,我们主要讨论了叁类图:分割图,刺图和路和圈笛卡尔积的脆弱性参数。 本文第一章首先介绍了这些脆弱性参数,并总结了一些基本图类(路,圈,星状图,彗星图,完全k-部图等)关于这些参数的研究结果以及本文的研究成果。 第二章简要介绍了分割图的性质,讨论了分割图的脆弱性参数的计算问题。 第叁章介绍了特殊图类刺图及其性质,讨论某些特殊的刺图的脆弱性参数,改正了Kirlangic的几个错误,并研究了单圈图的离散数计算问题。 第四章我们介绍了特殊图类:路和圈笛卡尔积,对其粘连度和毁裂度进行了一些讨论,介绍了我们的研究成果。 第五章介绍了关于图的脆弱性参数研究进一步可以做的研究工作。
武建[2]2007年在《处处h-可断图的若干问题研究》文中指出图的连通性理论是图论学科重要而基础的研究领域。通过该领域的研究，人们对图的结构和性质有了进一步的认识，并且将所得到的结果应用于网络设计等实际问题中，取得了很多应用成果。图的连通性研究所具有的理论和实际意义，激发了很多图论专家的兴趣。长期以来，人们围绕图的点连通度、边连通度、局部点(边)连通度开展了大量的研究工作，也取得了许多深刻的理论成果。但随着研究的深入，人们发现上述参数仅反映了系统被毁坏的难易，而很难准确反映系统被毁坏的程度。于是，人们开始摸索研究图的连通性的新途径。在1988年，贾晓峰等人提出了一个新的图类——处处h-可断图。设h是一个正整数。若S是图G的一个(顶点)极小割集，且|S|≤h，则称S是图G的一个下h-割集。若对于每个顶点v∈V(G)，至少存在一个下h-割集S，使得顶点v∈S，则称图G是一个处处h-可断图。新图类的提出为广泛图类中图的最大边数，最大团等问题的解决提供了新的途径。从处处h-可断图的提出到目前为止，贾晓峰等人对该类图进行了较深入的研究，尤其是在最大团问题方面，取得了较好的结果。本文对处处h-可断图的(顶点)极小割集进行了分类：设G是一个处处h-可断图，S是G的下h-割集，且G中无其它下h-割集与S交叉，则称S是图G的A类割集。否则称其为图G的B类割集。在此分类及前人研究结果的基础上，文章讨论了与处处h-可断图连通性及递归证明相关的新问题——可加边问题，并在这个问题的启发下引入了刻画处处h-可断图的连通性的新参数——图的完整度。它既反映了将处处h-可断图从(顶点)极小割集拆分开的难易，又反映了该图被拆分的程度。而在一个网络中，这个参数不仅反映了网络被毁坏的难易，而且也能反映网络被毁坏的程度。所以，对处处h-可断图的可加边问题及其完整度的研究有比较重要的理论和实际意义。本文的主要工作：第一部分在阐述图的连通性问题的研究现状及进展的同时，分析了以往图的连通性研究方法的局限性，论证了处处h-可断图和处处h-可断图的完整度两个概念的提出对图的连通性研究的理论意义。第二部分给出了关于图的(顶点)极小割集的一些研究结果。这些结果是我们对处处h-可断图的连通性展开研究的基石。第叁部分主要讨论了在A类割集是割点和A类割集不是割点且不是完全图两种情况下处处h-可断图的可加边问题，论证了处处h-可断图可加边的存在性，给出了刻画处处h-图的结构特性的两个充分条件。第四部分研究了处处h-可断图的完整度及其与图的其它一些参数的关系，并对处处h-可断图的完整度进行了界的估计。第五部分在总结全文的基础上，探讨了进一步的研究工作。
李峰伟[3]2002年在《关于图的完整度》文中认为图的连通性理论是图论中非常重要的一个研究领域，通过对图的连通性的研究，人们对图的结构和性质产生了进一步的认识，并且将所得到的结果应用于可靠通讯网络设计等实际问题中，取得了很好的效果。正是由于图的连通性具有很大的理论和实际意义，许多图论专家纷纷致力于这方面的研究工作，得到了很多有意义的结果。而这些研究工作主要是围绕点连通度，边连通度，局部点、边连通度来做的，但随着图的连通性研究的不断深入，人们越来越觉得仅用点连通度，边连通度，局部点、边连通度来描述图的连通性存在很大的局限性。对于两个具有相同点(边)数，具有相同点连通度(边连通度)的图，从图中分别去掉使图不连通的点(边)集后，所得图的结构可能完全不同，这是因为点连通度、边连通度和局部点、边连通度等连通性参数仅反映了系统被破坏的难易程度，而对系统遭受破坏的程度并没有明确的反映。另一方面，在实际中，我们常考虑这样一个问题：如何以较小的代价使一个系统遭到较大的破坏；反之，当我们营建一个系统——特别是一个通讯系统时，总要设法使在破坏该系统时需要付出较大的代价而系统遭受破坏的程度又不很严重。正因如此，在图的连通性研究中，迫切需要一个既能反映系统被破坏的难易程度又能反映系统遭受破坏程度的参数，而图的完整度正是符合这样要求的一个参数。本文在前人工作的基础上，对图的完整度进行了更为深入的研究。 本文的主要工作为： 第一部分介绍了图的完整度的研究现状及进展，指出本文的选题背景及意义。 第二部分主要讨论了完整度与图的其它参数之间的关系；给出了完整度给定条件下完整数的最大可能值及完整数给定条件下，完整度的最大最小可能值；给出了图的完整度与此图的删点子图的完整度之间的关系。 第叁部分研究了一种特殊图——置换图的完整度，给出了圈及路置换图的完整度及相关的一些结果。 第四部分主要讨论了完整度给定条件下，满足一定要求的最大网络的边数及其构造问题；给出了完整度给定条件下最小网络图的边数；并且研究了在完整度和连通度已知的条件下最大网络图的边数。 第五部分研究了图的完整度的推广—一图的边完整度。给出了几类特殊图，如格子图、线图、复合图等的边完整度；研究了图的边完整度与其线图的完整度之间的关系；研究了图的边完整度与图的其它参数之间的关系；研究了边完整度给定条件下的最大网络图。 第六部分研究了阶数及最大度数给定的树图可能具有的最大及最小完整度；给出了一类特殊树图的完整度算法。
齐楠楠[4]2007年在《图的脆弱性参数研究》文中认为在设计计算机网络和通讯网络时，为了避免和最大限度减少因网络通讯中断而带来的损失，设计者必须考虑网络的稳定性．因此，网络设计的基本思想之一便是使其在受到外部攻击时，不容易被破坏；更进一步，如果真的受到破坏，它们也比较容易被修复重建．一个计算机网络或者通讯网络，可以用一个连通图来表示，其中图的顶点表示通讯站，边表示两个通讯站之间可以直接通讯的通讯线路．对于一个网络，它的稳定性常用它所对应的图的脆弱性参数描述． 早期在脆弱性参数方面的研究，主要是围绕连通度和边连通度展开的．这两个参数被广泛用来描述图的脆弱性，而且已被证明，它们的计算存在多项式时间算法．由于这两个参数在描述图的脆弱性方面具有局限性，近年来人们陆续引入了一些其它脆弱性参数，主要包括了坚韧度和边坚韧度，离散数，完整度和边完整度，粘连度和边粘连度，毁裂度，邻域连通度和边邻域连通度，邻域完整度和边邻域完整度，邻域离散数和边邻域离散数．与连通度和边连通度不同，这些参数不仅考虑了破坏网络的难易程度，还考虑了网络遭受破坏的程度． 本文主要研究了图的(边)邻域离散数、毁裂度、完整度和弱完整度等几个脆弱性参数，分五章讨论了以下几个问题： 第一章主要介绍了这些脆弱性参数的定义以及它们的研究背景、研究现状和本文的一些研究成果． 第二章主要讨论了一般图及连通二部图的邻域离散数的上下界，并证明了二部图邻域离散数的计算是一个NP-完全问题． 第叁章主要讨论了一般图的边邻域离散数的界并给出了计算公式，构造了边邻域离散数意义下的最大网络，还证明了二部图边邻域离散数的计算是一个NP-困难问题． 第四章主要讨论了其它一些脆弱性参数如完整度、边完整度、弱完整度和毁裂度，给出了一些特殊图的脆弱性参数的计算公式及相互之间的关系，给出了顶点数和边数一定时毁裂度的最大值并构造了此时对应的网络图． 第五章主要介绍了关于图的脆弱性参数研究进一步可以做的研究工作．
麦安婵[5]2003年在《关于图的邻域完整度》文中指出为了衡量网络(图)被破坏的难易程度或网络(图)遭受破坏的程度，我们有两种完全不同的方式方法。一种方法基于确定性理论，称为确定性方法；另一种方法基于概率性理论，称为概率性方法。两种方法引起各种各样的图和网络的理论问题。其中确定性方法利用图的一些参数不变量，来衡量图或网络的脆弱性，而图或网络的可靠性的研究，则多采用概率性的方法。 量化一个图或网络的脆弱，开始于图的连通性研究和Menger,Whitney的理论。正是由于图或网络的脆弱性具有很大的理论和实际意义，许多图论学者纷纷致力于这方面的工作，提出了很多衡量图或网络脆弱性的参数。除了许多连通性方面的参数，如点连通度，边连通度，局部点、边连通度等，还有其它一些新的确定性度量参数，如坚韧度，离散数，粘连度，完整度等。 本文在前人工作的基础上，主要研究一个新的衡量图或网络的脆弱性的参数——图的邻域完整度(neighbor_integrity)。1994年,Margaret B．Cozzens和Shu_shih Y．Wu将一个图看作是一个间谍网的模型，并以此为背景提出了图的邻域完整度的概念。这是一个在图的完整度和图的邻域连通这两个概念的基础上发展起来的一个新的图的连通性参数。它从邻域的观点刻划了如何以最小的代价使图或网络遭受到最严重的破坏。 本文的主要工作分为以下四个部分： 第一部分介绍了图的邻域完整度的研究现状及进展，指出本文的选题背景及意义。 第二部分研究了图的邻域完整度。首先给出了图的邻域完整度的基本概念，讨论了图的邻域完整度和图的其它一些参数之间的关系；给出了图与其子图的邻域完整度之间的大小关系；其次讨论了图的邻域完整度的Nordhaus-Haddum问题，给出了一些笛卡尔乘积图和联图的邻域完整度，并给出了图的邻域完整度与图的最大边数的关系；最后给出了阶数和邻域完整度已知条件下树图的构造方法。 第叁部分研究了图的邻域完整度的推广——图的边邻域完整度。在给出图的边邻域完整度的概念的基础上，讨论了图的边邻域完整度和图的其它一些参数之间的关系，给出了图与其子图的边邻域完整度之间的关系并讨论了图的边邻域完整度的Nordhaus－HaddUm问题；其次给出了圈和圈的平方的边邻域完整度，并讨论了一个图的线图和全图的边邻域完整度，最后研究了边邻域完整度给定条件下图的最大、最小边数的界。 第四部分提出了图的纯边邻域完整度的概念。由于图的边邻域完整度是一个混合性的概念，研究起来不太方便，促使本人提出了一个新的衡量图的脆弱性的参数。这一参数仅仅包含图的边，故称之为图的纯边邻域完整度。本文在给出图的纯边邻域完整度的概念的基础上，首先讨论了图的纯边邻域完整度的基本性质，其次给出了这一参数基于边邻域完整度，边控制数，边独立数，点覆盖数的上下界，最后给出了一些特殊图类的纯边邻域完整度。
李银奎[6]2003年在《图的连通参数的相关研究》文中认为在计算机网络或通讯网络的设计与维护过程中，网络的抗毁性是一项重要的性能指标。网络设计的基本思想之一就是使其在受到外部攻击时不易被破坏，而且，在万一遭到破坏时也能够容易得到修复。我们通常用无向连通图来表示网络，其中图的顶点代表网络站点，边代表网络站点间的直通线路。在此数学模型之下，人们开始讨论抗毁性的有关测度，早期的研究主要是围绕图的连通度和边连通度展开的。伴随着研究的深入，人们发现用这两个参数刻画图的抗毁性存在明显不足之处。后来，人们引入了一些其它的参数，如坚韧度、离散数、完整度、粘连度。这些参数不仅考虑了网络被破坏的难易程度，而且还考虑到了网络遭受的毁坏程度，相比图的(边)连通度而言，是一些较为合理的刻画网络抗毁性的参数。 本论文在总结和比较以上连通性参数的基础上，引入了能比较客观、相对简单的刻画图的连通性的一个新参数——图的相对粘连度，并对这个参数进行了初步的研究。论文第一章分析了图的连通性参数的研究背景和实际意义，并介绍了论文所需的一些相关知识和本论文的主要结果。论文第二章介绍了图的连通度、边连通度、坚韧度、边坚韧度、离散数、完整度、边完整度、粘连度、边粘连度等图的连通性参数，对它们做了比较归纳和系统分析。论文在第叁章详细研究了一些特殊图(完全图、圈、路、星、彗星、完全二部图、完全k-部图)的相对粘连度，讨论了图的相对粘连度的界，图的运算的相对粘连度，树的相对粘连度的算法，相对粘连度与其他参数的关系。第四章讨论了图的相对粘连度意义下的最值网络的构造以及关于图的相对粘连度的Nordhaus-Gaddum型问题的结果。第五章对图的边相对粘连度进行了定义并做了一些简单研究。第六章讨论了相对粘连度的计算问题，证明了图的相对粘连度的计算是NP完全问题。最后，在结束语里我们对图的连通参数的定义进行了归纳统一，并提出了进一步研究的问题。
王玉珏[7]2007年在《几类特殊图的可靠性研究》文中研究表明网络的可靠性作为衡量网络性能的一个重要指标，一直是各国的研究者研究的热点问题。近年，网络的可靠性理论已经在现实世界中得到了充分的应用，如计算机系统、通信系统、电力传输系统、交通运输系统等。因此，网络的可靠性理论在我们现代社会中扮演着举足轻重的作用。包括上述诸多现实系统都可以用网络(图)作为模型进行研究。所谓网络(图)是由节点和边组成，其中节点和边是广义的，节点表示系统中的元素，两节点间的边表示元素之间的相互作用关系。尽管定义看似简单，但是网络(图)能够呈现高度的复杂性。目前对网络(图)的可靠性的研究主要有两种方法。一种方法基于确定性理论，其基本思想是利用某些被认为合理的参数来衡量网络(图)的可靠性。另一种方法基于概率性理论。本文所采用的是第一种方法。早期使用确定性理论对网络(图)的可靠性的研究主要是针对(点)连通度和边连通度，但随着研究的不断深入，人们发现这两个参数仅考虑了网络(图)遭到破坏的难易程度，却没有考虑被破坏的程度。基于此，人们又引入了其它的一些可靠性参数，其中(点)坚韧度和(点)粘连度被普遍认为是刻画可靠性较好的参数。显然，网络(图)的拓扑结构对其可靠性具有至关重要的影响，同时绝大部分网络可靠性问题都是NP-难的，在一定程度上不亚于许多标准的组合优化问题，因此计算出具体特殊图的可靠性参数具有重要的价值。本文在总结现有前人结论的基础上，计算并证明了几类特殊图的(点)坚韧度和(点)粘连度。
胡曦茜[8]2014年在《职前数学教师对导数知识的SMK及PCK水平研究》文中进行了进一步梳理近来，越来越多的研究表明教师的知识与技能影响着学生的课堂经历及数学认知结果.因此，职前教师的教育越来越受到研究者们的关注.本研究选择导数知识作为研究教师知识的切入点，调查了职前教师导数部分的学科知识（SMK）和学科教学知识(PCK)，希望为职前教师教育的发展提供反思的资料和建议的方向.研究以马立平“基础知识的深刻理解”框架为依据，用测试卷和概念图从深度、宽度和完整度叁个方面测试样本职前教师对于导数知识的SMK水平，又根据Ball的MKT模型中PCK部分，通过结构式的访谈和教案分析探究样本职前教师导数部分的PCK水平.研究的得到以下结论：（1）职前教师导数部分知识在深度、宽度和完整度上均存在不足，其中深度上的不足体现在对导数概念理解不够深刻.宽度的不足体现在与导数相关知识上的缺失，完整度的不足体现在职前教师在绘制概念图的过程中，对重要概念的遗漏以及概念之间的关系和层级上的错误.（2）职前教师导数部分的学科教学知识的缺失主要体现在对导数部分教材理解的不够深刻；对于学生学习困难的把握不够准确，不能正确认识学生出现的错误和给出针对性的纠正方案；以及教学设计中概念的引入、例题的选择和活动的设计均存在不合理之处.（3）影响职前教师学科教学知识的因素包括中学和大学学习经历和实习经历对其影响、学科知识对学科教学知识的影响以及学科教学知识个成分之间的相互影响.最后笔者针对职前教师在学科知识和学科教学知识中缺失的原因给出了对于师范生自身学习和师范类院校改进教学的具体建议.
孙立新[9]2007年在《图的连通度和分离度的研究》文中提出量化一个图或网络的脆弱程度，始于图的连通性研究和Menger，Whitney等人的理论，他们提出很多衡量图或网络脆弱性的参数。与连通度和边连通度不同，这些参数不仅考虑了破坏网络的难易程度，还考虑了网络遭受破坏的程度，在整体上能刻画网络与图的连通性，但也在不同程度上存在不足，使得提出更为细致的参数成为必要。本文在前人工作的基础上，主要研究一个新的衡量图或网络的脆弱性的参数—图的分离度(separativity)。1988年Jia Xiao_feng提出一个相当广泛的图类—处处(?)可断图，其中出现了分离集的概念，我们以此为背景提出了图的分离度的概念。连通图G的分离度定义为：这里S是G的割集，ω(G-S)是图G—S的连通分支数，m(G-S)是图G—S的最大连通分支的阶数。连通图G的边分离度定义为：这里S是G的边割集，ω(G-S)是图G-S的连通分支数，m(G-S)是图G—S的最大连通分支的阶数。本文的主要内容为：第一部分介绍了图的连通度和分离度的研究现状及进展，指出本文的选题背景及意义。第二部分主要讨论了分离度与图的其它参数之间的关系；给出了特殊图的分离度；同时对星状拓扑网络图的分离度问题进行了讨论。第叁部分引入了一类(h，f)-分离图，研究了其存在性问题与其上下界，并简单探讨了其判定问题的NP完全性。第四部分就边分离的问题进行了简单的探讨。由分离度的定义我们给出了边分离度的定义，探讨了(h，f)-边分离图的存在性，给出了边分离度和(h，f)-边分离图的一些结论。
魏宗田[10]2003年在《关于网络稳定性参数的研究》文中认为在网络的设计与建造过程中，稳定性是一个必须考虑的重要因素。一个网络可以模拟成一个连通图，其中图的顶点表示组件，边表示连接组件的信道。因而图的连通性与稳定性一直是图论的一个热点。围绕这个问题，除了早期的点(边)连通度外，人们后来又相继引入了一些新的连通性参数，主要有联结数，离散数，完整度和边完整度，粘连度和边粘连度，坚韧度等。这些参数同时反映了一个网络可能遭到的最大程度的破坏和被最大程度破坏后剩余部分的工作状态，因此更好地刻画了图的连通性。 然而考虑一些特殊网络，比如间谍网的上述性质时，情况完全不同了。因为倘若某个间谍被捕了，与其相邻的间谍必然会全部失去作用。以此为背景，G．Gunther于1991年引入图的邻域连通度概念，S．-S．Y．Wu和M．B．Cozzens于1994年，1996年分别引入图的邻域完整度和边邻域完整度概念，于是又出现了一系列研究成果，使网络稳定性研究迈进了一大步。本文在前人工作的基础上，着重研究了邻域场合下图的稳定性，得到一些相关结果，在一定程度上丰富了已有图的稳定性理论。 本文的主要内容是： 第一章绪论部分介绍图的连通性和稳定性方面的研究现状，指出本文研究工作的背景及意义。 第二章集中讨论复合图的邻域完整度，给出了一般情形下复合图邻域完整度的上下界，路状，圈状等特殊复合图的邻域完整度，还纠正了Pinar Dundar的几个错误。 第叁章引入图的邻域离散数概念，给出几类基本图的邻域离散数值，并就树的邻域离散数进行较为深入的研究。 第四章主要定义图的边邻域离散数，给出一些基本图的边邻域离散数值，图的边邻域离散数的界，树的边邻域离散数的一个多项式算法。
参考文献：
[1]. 几类特殊图的脆弱性参数[D]. 张启龙. 西北工业大学. 2006
[2]. 处处h-可断图的若干问题研究[D]. 武建. 太原理工大学. 2007
[3]. 关于图的完整度[D]. 李峰伟. 陕西师范大学. 2002
[4]. 图的脆弱性参数研究[D]. 齐楠楠. 西北工业大学. 2007
[5]. 关于图的邻域完整度[D]. 麦安婵. 陕西师范大学. 2003
[6]. 图的连通参数的相关研究[D]. 李银奎. 西北工业大学. 2003
[7]. 几类特殊图的可靠性研究[D]. 王玉珏. 南京信息工程大学. 2007
[8]. 职前数学教师对导数知识的SMK及PCK水平研究[D]. 胡曦茜. 苏州大学. 2014
[9]. 图的连通度和分离度的研究[D]. 孙立新. 太原理工大学. 2007
[10]. 关于网络稳定性参数的研究[D]. 魏宗田. 西北工业大学. 2003