有向圖的k-限制弧連通度
發(fā)布時(shí)間：2019-05-16 18:17
【摘要】：眾所周知,多處理機(jī)網(wǎng)絡(luò)的基礎(chǔ)拓?fù)渫ǔＲ詧D為數(shù)學(xué)模型,其中圖中的頂點(diǎn)表示處理機(jī),圖中的邊表示處理機(jī)間的直接通訊聯(lián)系.很多網(wǎng)絡(luò)間的通訊聯(lián)系都具有方向,因此,以有向圖為網(wǎng)絡(luò)的數(shù)學(xué)模型并且用弧連通度來(lái)度量有向網(wǎng)絡(luò)的可靠性.限制弧連通度作為比弧連通度更加精確的指標(biāo)被提出.本文提出了 k-限制弧連通度的概念,它是弧連通度與限制弧連通度的共同推廣.設(shè)D是強(qiáng)連通有向圖且S是D的一個(gè)弧子集.若D - S包含一個(gè)頂點(diǎn)數(shù)至少為k的強(qiáng)連通分支D'使得D-V(D')包含一個(gè)頂點(diǎn)數(shù)至少為k的連通子圖,則稱S為D的一個(gè)k-限制弧割.若是這樣的一個(gè)k-限制弧割存在,那么稱D是λk_連通的.一個(gè)λk-連通有向圖D的k-限制弧連通度λk(D)是指D中一個(gè)最小k-限制弧割所含弧數(shù).為了研究k-限制弧連通度,本文提出最小k-度的概念.設(shè)D是有向圖,k是一個(gè)正整數(shù).對(duì)任意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]連通}.一個(gè)有向圖D是λk-最優(yōu)的,若λk(D)=ζk(D).近幾年,λ2-連通有向圖和λ2-最優(yōu)有向圖的充分條件是限制弧連通度領(lǐng)域的一大研究熱點(diǎn).本文主要研究有向圖是λ3-連通和λ3-最優(yōu)的最小度條件,并且給出了有向笛卡爾積圖的k-限制弧連通度的上、下界.本文共分為四章.第一章首先介紹了本文用到的一些圖理論概念和記號(hào),然后介紹了k-限制弧連通度的研究背景.第二章研究了有向圖是λk_連通的和λk-最優(yōu)的最小度條件并用例子說(shuō)明這些度條件是最優(yōu)的.得到以下結(jié)論:對(duì)頂點(diǎn)數(shù)至少為2k的強(qiáng)連通有向圖D,若D的最小出度δ+(D) ≥ 2k-1或D的最小入度δ (D) ≥ 2k - 1,那么D是λk-連通的且滿足λk(D)≤ ζk(D).對(duì)頂點(diǎn)數(shù)至少為6的強(qiáng)連通有向圖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-最優(yōu)的.第三章確定笛卡爾積有向圖2-限制弧連通度的值以及k-限制弧連通度的上、下界,并且用例子說(shuō)明這些結(jié)論是最優(yōu)的.設(shè)D1和D2是兩個(gè)分別以V1和V2為頂點(diǎn)集的強(qiáng)連通有向圖.得到下述結(jié)果:(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)}.強(qiáng)限制弧連通度λs是一個(gè)與限制弧連通度密切相關(guān)的概念.第四章主要研究有向笛卡爾積圖的強(qiáng)限制弧連通度,并且用例子說(shuō)明這些結(jié)論是最優(yōu)的.設(shè)D1和D2是兩個(gè)分別以V1和V2為頂點(diǎn)集的強(qiáng)連通有向圖.得到下述結(jié)果:(1)若它們的頂點(diǎn)數(shù)分別為|V1| ≥ 2,|V2| ≥ 2,弧連通度分別為λ(D1),λ(D2),那么D=D1×D2 是λs-連通的且λs(D) ≤min{|V1|λ(D2),|V2|λ(D1)}.(2)若它們的頂點(diǎn)數(shù)分別為|V1|≥2, |V2|≥ 2,圍長(zhǎng)分別為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)}.
【學(xué)位授予單位】：山西大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5
本文編號(hào)：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)}.
【學(xué)位授予單位】：山西大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5
【參考文獻(xiàn)】
相關(guān)期刊論文 前2條
1 林上為;丁丹;;λ'最優(yōu)定向圖的最小度條件[J];云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年03期
2 伊輝;王世英;;限制弧連通有向圖的充分條件[J];太原師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2011年03期
相關(guān)碩士學(xué)位論文 前1條
1 李洋;強(qiáng)乘積圖的限制邊連通度和限制弧連通度[D];山西大學(xué);2011年
，本文編號(hào)：2478471
本文鏈接：http://sikaile.net/kejilunwen/yysx/2478471.html
最近更新
教材專著
