图的连通度和分离度的研究

摘要

量化一个图或网络的脆弱程度，始于图的连通性研究和Menger，Whitney等人的理论，他们提出很多衡量图或网络脆弱性的参数。与连通度和边连通度不同，这些参数不仅考虑了破坏网络的难易程度，还考虑了网络遭受破坏的程度，在整体上能刻画网络与图的连通性，但也在不同程度上存在不足，使得提出更为细致的参数成为必要。 本文在前人工作的基础上，主要研究一个新的衡量图或网络的脆弱性的参数—图的分离度(separativity)。1988年Jia Xiao_feng提出一个相当广泛的图类—处处h-可断图，其中出现了分离集的概念，以此为背景提出了图的分离度的概念。这里S是G的割集，ω(G-S)是图G-S的连通分支数，m(G-S)是图G-S的最大连通分支的阶数。这里S是G的边割集，ω(G-S)是图G-S的连通分支数，m(G-S)是图G-S的最大连通分支的阶数。主要内容为： 第一部分，介绍了图的连通度和分离度的研究现状及进展，指出本文的选题背景及意义。 第二部分，主要讨论了分离度与图的其它参数之间的关系；给出了特殊图的分离度；同时对星状拓扑网络图的分离度问题进行了讨论。 第三部分，引入了一类(h，f)-分离图，研究了其存在性问题与其上下界，并简单探讨了其判定问题的NP完全性。 第四部分，就边分离的问题进行了简单的探讨。由分离度的定义给出了边分离度的定义，探讨了(h,f)-边分离图的存在性，给出了边分离度和(h，f)-边分离图的一些结论。

目录

文摘

英文文摘

声明

第一章绪论

1.1连通度与分离度问题概述

1.2研究现状

1.3基本概念及术语

1.4本文主要结果

第二章图的连通性参数

2.1图的连通度及边连通度

2.2图的完整度及边完整度

2.3图的粘连度及边粘连度

2.4图的坚韧度及边坚韧度

2.5图的离散数

第三章图的分离度

3.1新参数的引入

3.2图的分离度与其它连通性参数的关系

3.3特殊图的分离度讨论

3.4星状拓扑图的分离度讨论

第四章一类(h，f)-分离图的性质

4.1引言

4.2一类(h，f)-分离图的存在性及其界的讨论

4.3一类(h，f)-分离图的判定问题

第五章图的边分离度

5.1引言

5.2特殊图的边分离度

5.3一类(h，f)-边分离图

进一步的工作

参考文献

致谢

攻读学位期间发表的学术论文目录