● 摘要
为了衡量网络（图）被破坏的难易程度或网络（图）遭受破坏的程度，我们有两种完全不同的方式方法。一种方法基于确定性理论，称为确定性方法;另一种方法基于概率性理论，称为概率性方法.两种方法引起各种各样的图和网络的理论问题。其中确定性方法利用图的一些参数不变量，来衡量图或网络的脆弱性，而图或网络的可靠性的研究，则多采用概率性的方法。 量化一个图或网络的脆弱，开始于图的连通性研究和Menger,Whitney的理论。正是由于图或网络的脆弱性具有很大的理论和实际意义，许多图论学者纷纷致力于这方面的工作，提出了很多衡量图或网络脆弱性的参数。除了许多连通性方面的参数，如点连通度，边连通度，局部点、边连通度等，还有其它一些新的确定性度量参数，如坚韧度，离散数，粘连度，完整度等。 本文在前人工作的基础上，主要研究一个新的衡量图或网络的脆弱性的参数--图的邻域完整度（neighbor_integrity）。1994年,Margaret B.Cozzens和Shu_shih Y.Wu将一个图看作是一个间谍网的模型，并以此为背景提出了图的邻域完整度的概念。这是一个在图的完整度和图的邻域连通这两个概念的基础上发展起来的一个新的图的连通性参数。它从邻域的观点刻划了如何以最小的代价使图或网络遭受到最严重的破坏。 本文的主要工作分为以下四个部分： 第一部分介绍了图的邻域完整度的研究现状及进展，指出本文的选题背景及意义。 第二部分研究了图的邻域完整度。首先给出了图的邻域完整度的基本概念，讨论了图的邻域完整度和图的其它一些参数之间的关系；给出了图与其子图的邻域完整度之间的大小关系；其次讨论了图的邻域完整度的Nordhaus-Haddum问题，给出了一些笛卡尔乘积图和联图的邻域完整度，并给出了图的邻域完整度与图的最大边数的关系；最后给出了阶数和邻域完整度已知条件下树图的构造方法。 第三部分研究了图的邻域完整度的推广--图的边邻域完整度。在给出图的边邻域完整度的概念的基础上，讨论了图的边邻域完整度和图的其它一些参数之间的关系，给出了图与其子图的边邻域完整度之间的关系并讨论了图的边邻域完整度的Nordhaus-Haddum问题；其次给出了圈和圈的平方的边邻域完整度，并讨论了一个图的线图和全图的边邻域完整度，最后研究了边邻域完整度给定条件下图的最大﹑最小边数的界。 第四部分提出了图的纯边邻域完整度的概念。由于图的边邻域完整度是一个混合性的概念，研究起来不太方便，促使本人提出了一个新的衡量图的脆弱性的参数。这一参数仅仅包含图的边，故称之为图的纯边邻域完整度。本文在给出图的纯边邻域完整度的概念的基础上，首先讨论了图的纯边邻域完整度的基本性质，其次给出了这一参数基于边邻域完整度，边控制数，边独立数，点覆盖数的上下界，最后给出了一些特殊图类的纯边邻域完整度。