几类变换有向图的连通性研究
发布时间：2019-05-14 01:31
【摘要】：在信息化时代,图论也被广泛的应用在人们的日常生活、生产中,尤其是计算机技术、大规模网络技术,图论与其更是有着密切的联系.图论中图的边连通度的问题就是来源于网络设计的稳定性与可靠性的分析.对于多处理机网络的分析,经常会涉及到某些图类模型,即用图中的点和边分别表示网络中的节点和连线,从而构成连通的网络的拓扑结构.一个重要的模型就是人们将网络模型化为一个连通有向(无向)图,图中的点集和弧集分别表示所有的处理机和系统中各处理机之间的通信联系.从而网络的可靠性,可通过有向图或无向图中的一些概念,比如连通度、边连通度、弧连通度等来刻画.因此,连通度成为反映网络稳定的重要参数,这也就促成了图的连通性成为图论研究中的热点.利用简单图的点连通度或边连通度来精确分析网络的稳定性还存在一些不足.经过研究,人们发现某些图类,比如说,线图、笛卡尔积、字典积、强积等变换图都是由已知图经过特殊构造而得到的更大的图的重要结果,而通过这些变换图可以得到各种各样的网络结构,从而,对各种变换图或有向图的连通性、边连通性、弧连通性的研究,可以从理论上为可靠性网络的设计提供科学的解决方法和手段.人们从对图的连通度的研究发展到对各种变换图的高阶连通性的研究.本文主要研究某些特殊变换图的连通性问题.论文的正文部分分为三章:第一章,主要介绍了图的连通性理论的研究背景和一些基本概念,给出了全变换有向图Dxyz、笛卡尔积和字典积等的定义.最后介绍了本文的研究内容以及罗列出本文的主要研究成果.第二章,根据全变换有向图的定义,可以得到27种全变换有向图,但在这篇文章中我们主要研究与符号′0′有关的10种全变换有向图的基本性质,例如:正则性、强连通性、λ-最优以及超弧连通性.证明了这些全变换有向图是强连通、λ-最优以及超弧连通的充要条件.第三章,首先介绍了两个有向图的线图、笛卡尔积和字典积有向图的研究历史及现状.其次,定义了有向图的bi-super性,并证明了线图是bi-super的充要条件.最后,在已有的笛卡尔积和字典积有向图的连通性研究的基础上,继续研究它们的bi-super性.
[Abstract]:In the information age, graph theory is also widely used in people's daily life, production, especially computer technology, large-scale network technology, graph theory is closely related to it. The problem of edge connectivity of graphs in graph theory comes from the analysis of stability and reliability of network design. For the analysis of multiprocessor networks, some graph models are often involved, that is, the points and edges in the graph are used to represent the nodes and connections in the network respectively, thus forming the topological structure of the connected network. An important model is that people model the network into a connected directed (undirected) graph, in which the point set and arc set represent the communication relationship between all processors and each processor in the system, respectively. Thus, the reliability of the network can be characterized by some concepts in directed graph or undirected graph, such as connectivity, edge connectivity, arc connectivity and so on. Therefore, connectivity has become an important parameter to reflect the stability of the network, which makes the connectivity of graphs become a hot spot in graph theory. There are still some shortcomings in the accurate analysis of the stability of the network by using the point connectivity or edge connectivity of a simple graph. After research, it is found that some graph classes, such as graph, Cartesian product, dictionary product, strong product and so on, are the important results of larger graphs obtained by special construction of known graphs. Through these transformation graphs, a variety of network structures can be obtained, thus, the connectivity, edge connectivity and arc connectivity of various transformation graphs or directed graphs can be studied. It can provide scientific solutions and means for the design of reliability network in theory. People have developed from the study of the connectivity of graphs to the study of higher-order connectivity of various transformation graphs. In this paper, we mainly study the connectivity of some special transformation graphs. The main body of the paper is divided into three chapters: in the first chapter, the research background and some basic concepts of the connectivity theory of graphs are introduced, and the definitions of Dxyz, Cartesian product and dictionary product of fully transformed directed graphs are given. Finally, it introduces the research content of this paper and lists the main research results of this paper. In chapter 2, according to the definition of total transformation directed graph, 27 kinds of total transformation directed graph can be obtained, but in this paper, we mainly study the basic properties of 10 kinds of total transformation directed graph related to symbol'0', such as regularity, strong connectivity, 位-optimal and super-arc connectivity. The necessary and sufficient conditions for these fully transformed directed graphs to be strongly connected, 位-optimal and super-arc connected are proved. In the third chapter, the research history and present situation of two directed graphs, Cartesian product and dictionary product directed graph, are introduced at first. Secondly, the bi- superability of directed graphs is defined, and the necessary and sufficient conditions for graphs to be bi-super are proved. Finally, on the basis of the existing studies on the connectivity of Cartesian products and dictionary product directed graphs, we continue to study their bi- superproperties.
【学位授予单位】：新疆师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
[Abstract]:In the information age, graph theory is also widely used in people's daily life, production, especially computer technology, large-scale network technology, graph theory is closely related to it. The problem of edge connectivity of graphs in graph theory comes from the analysis of stability and reliability of network design. For the analysis of multiprocessor networks, some graph models are often involved, that is, the points and edges in the graph are used to represent the nodes and connections in the network respectively, thus forming the topological structure of the connected network. An important model is that people model the network into a connected directed (undirected) graph, in which the point set and arc set represent the communication relationship between all processors and each processor in the system, respectively. Thus, the reliability of the network can be characterized by some concepts in directed graph or undirected graph, such as connectivity, edge connectivity, arc connectivity and so on. Therefore, connectivity has become an important parameter to reflect the stability of the network, which makes the connectivity of graphs become a hot spot in graph theory. There are still some shortcomings in the accurate analysis of the stability of the network by using the point connectivity or edge connectivity of a simple graph. After research, it is found that some graph classes, such as graph, Cartesian product, dictionary product, strong product and so on, are the important results of larger graphs obtained by special construction of known graphs. Through these transformation graphs, a variety of network structures can be obtained, thus, the connectivity, edge connectivity and arc connectivity of various transformation graphs or directed graphs can be studied. It can provide scientific solutions and means for the design of reliability network in theory. People have developed from the study of the connectivity of graphs to the study of higher-order connectivity of various transformation graphs. In this paper, we mainly study the connectivity of some special transformation graphs. The main body of the paper is divided into three chapters: in the first chapter, the research background and some basic concepts of the connectivity theory of graphs are introduced, and the definitions of Dxyz, Cartesian product and dictionary product of fully transformed directed graphs are given. Finally, it introduces the research content of this paper and lists the main research results of this paper. In chapter 2, according to the definition of total transformation directed graph, 27 kinds of total transformation directed graph can be obtained, but in this paper, we mainly study the basic properties of 10 kinds of total transformation directed graph related to symbol'0', such as regularity, strong connectivity, 位-optimal and super-arc connectivity. The necessary and sufficient conditions for these fully transformed directed graphs to be strongly connected, 位-optimal and super-arc connected are proved. In the third chapter, the research history and present situation of two directed graphs, Cartesian product and dictionary product directed graph, are introduced at first. Secondly, the bi- superability of directed graphs is defined, and the necessary and sufficient conditions for graphs to be bi-super are proved. Finally, on the basis of the existing studies on the connectivity of Cartesian products and dictionary product directed graphs, we continue to study their bi- superproperties.
【学位授予单位】：新疆师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【相似文献】
相关期刊论文 前10条
1 李炜,施永兵;有向图的有向圈长分布(英文)[J];上海师范大学学报(自然科学版);2003年02期
2 刘爱霞;杨爱民;;局部内(外)半完全有向图的可迹性[J];中北大学学报(自然科学版);2006年02期
3 白竹香;邵燕灵;;一类双色有向图的指数(英文)[J];山西大学学报(自然科学版);2007年01期
4 张彬;;局部半完全有向图中的王[J];太原师范学院学报(自然科学版);2007年02期
5 吴静;王鹏涛;魏国利;;带周期的强连通有向图的研究与应用[J];天津工业大学学报;2007年05期
6 刘爱霞;杨爱民;;扩张的局部内(外)半完全有向图的可迹性[J];中北大学学报(自然科学版);2008年05期
7 师海忠;;有向图语言[J];计算机工程与应用;2011年22期
8 周镇海;极小和极大线有向图[J];数学杂志;1984年03期
9 宋增民;有向图中的弧数和回路[J];自然杂志;1986年10期
10 陈仕洲;;半距离度正则有向图[J];韩山师范学院学报;1987年03期
相关会议论文 前4条
1 李刚;童，
本文编号：2476335
本文链接：https://www.wllwen.com/kejilunwen/yysx/2476335.html
