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

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

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

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