图和有向图的局部边连通与局部点连通性研究

摘要

我们都知道图论是一门古老却又十分活跃的学科,也是一门很有实用价值的学科.作为组合数学和离散数学的重要分支,它是研究自然科学,工程技术等的重要数学工具,应用极为广泛.在经济发展的时代,其与计算机科学和网络理论等方面的联系也越来越密切.图论中图的边连通度问题就源于大规模网络的设计及可靠性分析,在实际问题中有着极其广泛的应用.目前,点连通度和边连通度己成为图论中的热点研究领域.
　　对网络的一个指标是希望它的可靠性要尽可能好,就是希望图的边连通度或者点连通度尽可能大.因此点连通度和边连通度成为衡量图的连通性质的一个重要参数,也就成为反映网络可靠性的关键参数.而要更精确地刻画图的连通性,经典边连通度仍存在一些不足.为了更好地刻画图的连通情况,Harary很早就于1983年提出了条件边连通度的概念,为该领域的研究开辟了新的道路.从而,网络的可靠性与容错性的分析快速发展成为图论研究中的热门课题.为此,许多新的参数相继被提出来,其中包括极大边连通性、极大点连通性、超级点连通性、超级边连通性、局部边连通度和限制边连通度、局部点连通性.目前,对于这一领域已有了广泛而深入的研究.本人将在前人工作的基础上,继续研究超级局部边连通和超级局部点连通性的相关性质.
　　本文讨论有限简单的有向图.在第一章中,主要介绍本文的研究背景,文中涉及的基本概念及术语符号,已有的一些结论.
　　在第二章中，主要讨论了K2,p-free图的超级局部(点)边连通性的充分条件，本文得到如下结果（公式略）.
　　在第三章中，主要讨论了K2,p-free子图且不以C4作为点导出图的图的超级局部点(边)连通性（公式略）.
　　在第四章中，主要利用无钻子图的超级局部边连通性的己有结论，再利用团数来限制从而得出依赖于团数的无钻导出图是超级局部边连通的充分性的判定条件，从而得到了下面的定理以及一些相应的推论（公式略）.

目录

封面

声明

目录

中文摘要

英文摘要

第一章 引言

第二章 K2,p-free图的超级局部（点）边连通性

第三章 K2,p-free子图且不以C4作为点导出图的图的超级局部点（边）连通性

第四章 依赖于团数的无导出钻图的超级局部（点）边连通性

参考文献

致谢