论文摘要：关于图的完整度

　　图的连通性理论是图论中非常重要的一个研究领域，通过对图的连通性的研究，人们对图的结构和性质产生了进一步的认识，并且将所得到的结果应用于可靠通讯网络设计等实际问题中，取得了很好的效果。正是由于图的连通性具有很大的理论和实际意义，许多图论专家纷纷致力于这方面的研究工作，得到了很多有意义的结果。而这些研究工作主要是围绕点连通度，边连通度，局部点、边连通度来做的，但随着图的连通性研究的不断深入，人们越来越觉得仅用点连通度，边连通度，局部点、边连通度来描述图的连通性存在很大的局限性。对于两个具有相同点（边）数，具有相同点连通度（边连通度）的图，从图中分别去掉使图不连通的点（边）集后，所得图的结构可能完全不同，这是因为点连通度、边连通度和局部点、边连通度等连通性参数仅反映了系统被破坏的难易程度，而对系统遭受破坏的程度并没有明确的反映。另一方面，在实际中，我们常考虑这样一个问题：如何以较小的代价使一个系统遭到较大的破坏；反之，当我们营建一个系统--特别是一个通讯系统时，总要设法使在破坏该系统时需要付出较大的代价而系统遭受破坏的程度又不很严重。正因如此，在图的连通性研究中，迫切需要一个既能反映系统被破坏的难易程度又能反映系统遭受破坏程度的参数，而图的完整度正是符合这样要求的一个参数。本文在前人工作的基础上，对图的完整度进行了更为深入的研究。 　　本文的主要工作为： 　　第一部分介绍了图的完整度的研究现状及进展，指出本文的选题背景及意义。 　　第二部分主要讨论了完整度与图的其它参数之间的关系；给出了完整度给定条件下完整数的最大可能值及完整数给定条件下，完整度的最大最小可能值;给出了图的完整度与此图的删点子图的完整度之间的关系。 　　第三部分研究了一种特殊图--置换图的完整度，给出了圈及路置换图的完整度及相关的一些结果。 　　第四部分主要讨论了完整度给定条件下，满足一定要求的最大网络的边数及其构造问题；给出了完整度给定条件下最小网络图的边数；并且研究了在完整度和连通度已知的条件下最大网络图的边数。 　　第五部分研究了图的完整度的推广--图的边完整度。给出了几类特殊图，如格子图、线图、复合图等的边完整度；研究了图的边完整度与其线图的完整度之间的关系；研究了图的边完整度与图的其它参数之间的关系；研究了边完整度给定条件下的最大网络图。 　　第六部分研究了阶数及最大度数给定的树图可能具有的最大及最小完整度；给出了一类特殊树图的完整度算法。