有向图的k-限制弧连通度
发布时间：2019-05-16 18:17
【摘要】：众所周知,多处理机网络的基础拓扑通常以图为数学模型,其中图中的顶点表示处理机,图中的边表示处理机间的直接通讯联系.很多网络间的通讯联系都具有方向,因此,以有向图为网络的数学模型并且用弧连通度来度量有向网络的可靠性.限制弧连通度作为比弧连通度更加精确的指标被提出.本文提出了 k-限制弧连通度的概念,它是弧连通度与限制弧连通度的共同推广.设D是强连通有向图且S是D的一个弧子集.若D - S包含一个顶点数至少为k的强连通分支D'使得D-V(D')包含一个顶点数至少为k的连通子图,则称S为D的一个k-限制弧割.若是这样的一个k-限制弧割存在,那么称D是λk_连通的.一个λk-连通有向图D的k-限制弧连通度λk(D)是指D中一个最小k-限制弧割所含弧数.为了研究k-限制弧连通度,本文提出最小k-度的概念.设D是有向图,k是一个正整数.对任意X(?)V(D),令Ω(X)={а+(X1)∪а(X\X1):X1(?)X},ζ(X) = min{|S| :S∈Ω(X}.定义D的最小k小度为ζk(为 =min{ζ(X):X(?)V(D),|X|=k,D[X]连通}.一个有向图D是λk-最优的,若λk(D)=ζk(D).近几年,λ2-连通有向图和λ2-最优有向图的充分条件是限制弧连通度领域的一大研究热点.本文主要研究有向图是λ3-连通和λ3-最优的最小度条件,并且给出了有向笛卡尔积图的k-限制弧连通度的上、下界.本文共分为四章.第一章首先介绍了本文用到的一些图理论概念和记号,然后介绍了k-限制弧连通度的研究背景.第二章研究了有向图是λk_连通的和λk-最优的最小度条件并用例子说明这些度条件是最优的.得到以下结论:对顶点数至少为2k的强连通有向图D,若D的最小出度δ+(D) ≥ 2k-1或D的最小入度δ (D) ≥ 2k - 1,那么D是λk-连通的且满足λk(D)≤ ζk(D).对顶点数至少为6的强连通有向图D,(1)若D的最小度δ(D)≥3,那么D是λ3-连通的.(2)若D的最小度δ(D) ≥ 4.那么D是λ3-连通的且满足λ3(D) ≤ ζ3(D).(3)若D的最小度δ(D)≥|V(D)+3|/2,那么D是λ3-最优的.第三章确定笛卡尔积有向图2-限制弧连通度的值以及k-限制弧连通度的上、下界,并且用例子说明这些结论是最优的.设D1和D2是两个分别以V1和V2为顶点集的强连通有向图.得到下述结果:(1)若λ(D1)≥ 2和λ(D2)≥2,则D =D1 × D2 是λ2-连通的且λ2(D)=min{ζ2(D) ,|V1|λ(D2),|V2|λ(D1)}(2)若|V1|≥ k和|V2| ≥ k,那么D=D1×D2是λk-连通的且满足λk(D) ≤ min{ζk(D),|V1|λ(D2),|V2|λ(D1)}(3)若|V1|≥ 3和|V2|≥3,那么D=D1×D2是λ3-连通的且满足λ3(D) ≥ min{|V1|λ(D2), |V2|λ(D1), 3λ(D2) + λ(D1), 3λ(D1) + λ(D2)}.强限制弧连通度λs是一个与限制弧连通度密切相关的概念.第四章主要研究有向笛卡尔积图的强限制弧连通度,并且用例子说明这些结论是最优的.设D1和D2是两个分别以V1和V2为顶点集的强连通有向图.得到下述结果:(1)若它们的顶点数分别为|V1| ≥ 2,|V2| ≥ 2,弧连通度分别为λ(D1),λ(D2),那么D=D1×D2 是λs-连通的且λs(D) ≤min{|V1|λ(D2),|V2|λ(D1)}.(2)若它们的顶点数分别为|V1|≥2, |V2|≥ 2,围长分别为g1,g2,弧连通度分别为λ(D1),λ(D2),则笛卡尔积有向图D = D1×D2是λs-连通的并且λs(D) ≥ min{|V1|λ(D2),|V2|λ(D1),λ(D1) +g1λ(D2),λ(D2) +g2λ(D1)}.
[Abstract]:It is well known that the basic topology of a multi-processor network is generally a mathematical model in which the vertices in the figure represent a processor, and the edges in the figure represent direct communication between the processors. Many of the communication links between the networks have the direction, so the reliability of the network is measured by using the digraph as the mathematical model of the network and using the degree of arc connectivity. The limit arc connectivity is proposed as an index that is more accurate than the arc-to-arc connectivity. In this paper, the concept of k-limit arc communication is presented, which is a common extension of the degree of arc communication and the limit arc. Let D be a strongly connected directed graph and S is an arc subset of D. If D-S contains a strong branch D 'having a number of vertices of at least k so that D-V (D') contains a communication sub-graph with a number of vertices of at least k, then a k-limit arc of S is called D. If such a k-limit arc-cut is present, then D is k _ connected. The k-limit arc communication degree of k (D) of a dik-connected digraph D refers to a minimum k-limit arc number in D. In order to study the k-limit arc connectivity, the concept of minimum k-degree is proposed in this paper. Let D be a directed graph, k is a positive integer. For any X (?) V (D), the 惟 (X) = {++ + (X1)} {\ expndtw-1 (XX1): X1 (?) X}, X (X) = min {| S |: S/ 惟 (X}). The minimum k degree of the definition D is the minimum k (for = min {1 (X): X (?) V (D), | X | = k, D[X] connected}. A directed graph D is k-optimal, if k (D) = "k" (D). In recent years, the sufficient condition of the 2-connected digraph and the 2-optimal directed graph is one of the research hotspots in the field of limiting arc connectivity. In this paper, the minimum degree condition of the digraph is the 3-and the 3-optimal, and the upper and lower bounds of k-limiting arc connectivity to the Cartesian product are given. This paper is divided into four chapters. The first chapter first introduces some of the concepts and marks used in the paper, and then introduces the research background of k-limit arc communication. In the second chapter, we study the minimum degree of the digraph, which is the k _ connected and the k-optimal, and the examples to illustrate these conditions are the best. The following conclusion is obtained: for a strongly connected directed graph D having a vertex number of at least 2 k, if D is a minimum of 2 k-1 or D's minimum degree of penetration (D) and 2 k-1, then D is k-connected and satisfies the Fk (D)-2k (D). For a strongly connected directed graph D having a number of vertices of at least 6, (1) if the minimum degree of D of the D is equal to (D) = 3, then D is in the range of 3-communicating. (2) if the minimum degree of D of D is equal to (D) -4. Then D is in-3-communicated and satisfies FIG.3 (D) and FIG.3 (D). (3) If the minimum degree of D of D is (D) + | V (D) + 3 |/2, then D is equal to 3-optimal. The third chapter is to determine the value of the 2-limit arc connectivity of the Cartesian product digraph and the upper and lower bounds of k-limit arc connectivity, and the examples show that these conclusions are optimal. Let D1 and D2 be two strongly connected digraphs with V1 and V2 as the set of vertices, respectively. The following results are obtained: (1) If the values of (D1), (D2) and (D2) = 2, D = D1 and D2 are 2-connected and 2 (D) = min {EMA2 (D), | V1 | IX (D2), | V2 | IX (D1)} (2) if | V1 | Hk and | V2 | Fisk, then D = D1 and D2 are k-connected and satisfy the[k (D)/ min {utk (D), | V1 | IX (D2), | V2 | IX (D1)} (3) if | V1 | -3 and | V2 | IX (3), then D = D1 and D2 are the {3-communicated and satisfy the} {3 (D)} min {| V1 | 1 (D2), | V2 | IX (D1), 3-(D2) + 1 (D1),3-(D1) + 1 (D2)}. The strong limit arc communication degree is a concept which is closely related to the limit arc communication degree. The fourth chapter mainly studies the strong limit arc communication degree to the Cartesian product graph, and the examples show that these conclusions are optimal. Let D1 and D2 be two strongly connected digraphs with V1 and V2 as the set of vertices, respectively. The following results are obtained: (1) If the number of their vertices is | V1 | 2, | V2 | 2, and the degree of arc communication is respectively 1 (D1) and (D2), then D = D1-D2 is the's-connected and's (D)/ min {| V1 | 1 (D2), | V2 | IX (D1)}. (2) If the number of their vertices is | V1 | 2, | V2 | 2, the girth is g1, g2, and the degree of arc communication is respectively 1 (D1) and (D2), then the Cartesian product digraph D = D1-D2 is the's-connected and's (D)/ min {| V1 |} (D2), | V2 | IX (D1), xt (D1) + g1 (D2), (D2) + g2 + (D1)}.
【学位授予单位】：山西大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
本文编号：2478471
[Abstract]:It is well known that the basic topology of a multi-processor network is generally a mathematical model in which the vertices in the figure represent a processor, and the edges in the figure represent direct communication between the processors. Many of the communication links between the networks have the direction, so the reliability of the network is measured by using the digraph as the mathematical model of the network and using the degree of arc connectivity. The limit arc connectivity is proposed as an index that is more accurate than the arc-to-arc connectivity. In this paper, the concept of k-limit arc communication is presented, which is a common extension of the degree of arc communication and the limit arc. Let D be a strongly connected directed graph and S is an arc subset of D. If D-S contains a strong branch D 'having a number of vertices of at least k so that D-V (D') contains a communication sub-graph with a number of vertices of at least k, then a k-limit arc of S is called D. If such a k-limit arc-cut is present, then D is k _ connected. The k-limit arc communication degree of k (D) of a dik-connected digraph D refers to a minimum k-limit arc number in D. In order to study the k-limit arc connectivity, the concept of minimum k-degree is proposed in this paper. Let D be a directed graph, k is a positive integer. For any X (?) V (D), the 惟 (X) = {++ + (X1)} {\ expndtw-1 (XX1): X1 (?) X}, X (X) = min {| S |: S/ 惟 (X}). The minimum k degree of the definition D is the minimum k (for = min {1 (X): X (?) V (D), | X | = k, D[X] connected}. A directed graph D is k-optimal, if k (D) = "k" (D). In recent years, the sufficient condition of the 2-connected digraph and the 2-optimal directed graph is one of the research hotspots in the field of limiting arc connectivity. In this paper, the minimum degree condition of the digraph is the 3-and the 3-optimal, and the upper and lower bounds of k-limiting arc connectivity to the Cartesian product are given. This paper is divided into four chapters. The first chapter first introduces some of the concepts and marks used in the paper, and then introduces the research background of k-limit arc communication. In the second chapter, we study the minimum degree of the digraph, which is the k _ connected and the k-optimal, and the examples to illustrate these conditions are the best. The following conclusion is obtained: for a strongly connected directed graph D having a vertex number of at least 2 k, if D is a minimum of 2 k-1 or D's minimum degree of penetration (D) and 2 k-1, then D is k-connected and satisfies the Fk (D)-2k (D). For a strongly connected directed graph D having a number of vertices of at least 6, (1) if the minimum degree of D of the D is equal to (D) = 3, then D is in the range of 3-communicating. (2) if the minimum degree of D of D is equal to (D) -4. Then D is in-3-communicated and satisfies FIG.3 (D) and FIG.3 (D). (3) If the minimum degree of D of D is (D) + | V (D) + 3 |/2, then D is equal to 3-optimal. The third chapter is to determine the value of the 2-limit arc connectivity of the Cartesian product digraph and the upper and lower bounds of k-limit arc connectivity, and the examples show that these conclusions are optimal. Let D1 and D2 be two strongly connected digraphs with V1 and V2 as the set of vertices, respectively. The following results are obtained: (1) If the values of (D1), (D2) and (D2) = 2, D = D1 and D2 are 2-connected and 2 (D) = min {EMA2 (D), | V1 | IX (D2), | V2 | IX (D1)} (2) if | V1 | Hk and | V2 | Fisk, then D = D1 and D2 are k-connected and satisfy the[k (D)/ min {utk (D), | V1 | IX (D2), | V2 | IX (D1)} (3) if | V1 | -3 and | V2 | IX (3), then D = D1 and D2 are the {3-communicated and satisfy the} {3 (D)} min {| V1 | 1 (D2), | V2 | IX (D1), 3-(D2) + 1 (D1),3-(D1) + 1 (D2)}. The strong limit arc communication degree is a concept which is closely related to the limit arc communication degree. The fourth chapter mainly studies the strong limit arc communication degree to the Cartesian product graph, and the examples show that these conclusions are optimal. Let D1 and D2 be two strongly connected digraphs with V1 and V2 as the set of vertices, respectively. The following results are obtained: (1) If the number of their vertices is | V1 | 2, | V2 | 2, and the degree of arc communication is respectively 1 (D1) and (D2), then D = D1-D2 is the's-connected and's (D)/ min {| V1 | 1 (D2), | V2 | IX (D1)}. (2) If the number of their vertices is | V1 | 2, | V2 | 2, the girth is g1, g2, and the degree of arc communication is respectively 1 (D1) and (D2), then the Cartesian product digraph D = D1-D2 is the's-connected and's (D)/ min {| V1 |} (D2), | V2 | IX (D1), xt (D1) + g1 (D2), (D2) + g2 + (D1)}.
【学位授予单位】：山西大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
【参考文献】
相关期刊论文 前2条
1 林上为;丁丹;;λ'最优定向图的最小度条件[J];云南民族大学学报(自然科学版);2016年03期
2 伊辉;王世英;;限制弧连通有向图的充分条件[J];太原师范学院学报(自然科学版);2011年03期
相关硕士学位论文 前1条
1 李洋;强乘积图的限制边连通度和限制弧连通度[D];山西大学;2011年
，本文编号：2478471
本文链接：https://www.wllwen.com/kejilunwen/yysx/2478471.html
