有向圖的條件弧連通度.pdf

1、在設(shè)計大型網(wǎng)絡(luò)時，人們要考慮的一個基本問題是網(wǎng)絡(luò)的可靠性（容錯性），它可由圖的邊連通度來度量.為更精確地度量，人們推廣邊連通度，提出限制邊連通度的概念.限制邊連通度一經(jīng)提出就得到了很多的關(guān)注作為限制邊連通度在有向圖中的推廣，圈弧連通度λc(D)、強限制弧連通度λ2（D)、限制弧連通度λ'(D）分別被提出.本文提出限制邊連通度的又一個推廣-條件弧連通度.
　　設(shè)D是一個強連通有向圖.D的一個弧子集S是D的一個條件弧割，若D-S不是強

2、連通的且它的最小度δ(D-S)≥1.稱D是λ(1)-連通的，若它包含一個條件弧割D的條件弧連通度,記為λ(1)(D)，是D的一個最小條件弧割所含的弧數(shù).
　　Kautz圖是有競爭力的大型網(wǎng)絡(luò)-Kautz網(wǎng)絡(luò)的拓撲結(jié)構(gòu)本文分為四章，將給出條件弧連通度的一些性質(zhì)并確定有向Kautz圖的條件弧連通度.
　　第一章首先介紹將用到的一些圖論基本概念和記號，然后給出本文的研究背景、主要概念和主要結(jié)果.
　　第二章首先說明條件弧連通

3、度是限制邊連通度的一個推廣,討論條件弧連通度和強限制弧連通度λ2(D)，圈弧連通度λc(D)，限制弧連通度λ'(D)之間的關(guān)系，證明對于存在一個強限制弧割的有向圖D，λ2(D)≥λ(1）(D)≥λc(D)≥λ'(D)，并用例子說明限制邊連通度的這四個推廣各不相同.
　　Volkmann給出了有向圖D的限制弧連通度λ'(D）的一個上界ξ(D).第三章證明了當一個有向圖D的最小度大于它的圍長時有λ(1)(D)≤ξ(D),并用例子說明了