定向圖的限制弧連通度.pdf

1、在通信網(wǎng)絡(luò)的研究中，人們通常以圖或有向圖為數(shù)學(xué)模型表示多處理器系統(tǒng)的互連網(wǎng)拓?fù)浣Y(jié)構(gòu)，其中頂點(diǎn)集和邊集或弧集分別表示元件和連線的集合.此時(shí)，圖的性質(zhì)和參數(shù)可用來(lái)度量網(wǎng)絡(luò)拓?fù)涞男阅?在實(shí)際應(yīng)用中，很多網(wǎng)絡(luò)的連線都是有向的，這樣的網(wǎng)絡(luò)通常以有向圖為數(shù)學(xué)模型.通常用弧連通度來(lái)度量有向網(wǎng)絡(luò)的可靠性，但是用弧連通度進(jìn)行度量有一定的缺陷，因而為了更好地度量網(wǎng)絡(luò)的可靠性，限制弧連通度的概念被提出.
　　設(shè) D是一個(gè)強(qiáng)連通的有向圖.一個(gè)弧割S是一個(gè)

2、限制弧割，若 D-S包含一個(gè)非平凡的強(qiáng)分支D使得D- V( D)至少包含一條弧.限制弧連通度λ(D)是指最小限制弧割的弧數(shù).設(shè)(( D)是 D的最小弧度，它在絕大多數(shù)情況下都是λ'(D)的上界.一個(gè)強(qiáng)連通有向圖D被稱(chēng)為乂最優(yōu)的，若λ'(D)=((D).一個(gè)強(qiáng)連通的有向圖是超級(jí)λ'的，若它的限制弧連通度是極大的且最小限制弧割的數(shù)目是極小的.
　　近年來(lái)，有向圖是λ'最優(yōu)和超級(jí)λ'的條件得到了廣泛的關(guān)注.2013年，Griiter等人

3、相繼提出了競(jìng)賽圖和二部競(jìng)賽圖是A'最優(yōu)的最小度條件.競(jìng)賽圖是定向圖的一個(gè)子類(lèi).文中給出了定向圖和k部定向圖（k>2)是λ'最優(yōu)的最小度條件，并且研究了定向圖和二部定向圖是超級(jí)A'的最小度條件以及在一些度序列條件下，定向圖的限制弧連通度的一個(gè)下界.
　　本文共分為四章內(nèi)容.
　　第一章首先綜述了限制弧連通度的應(yīng)用背景和研究現(xiàn)狀，然后介紹了本文中將用到的一些圖論基本概念和記號(hào).
　　第二章研究了定向圖和k部定向圖（k≥2)

4、是λ'最優(yōu)的最小度條件.設(shè)D是一個(gè)階為n的定向圖.得到以下結(jié)論：
　　(1)若最小度S(D)≥ n+1_4,則定向圖D是λ'最優(yōu)的.
　　(2)當(dāng) k=2或 n是奇數(shù)時(shí)，若最小度δ(D)≥(k-1） ra+3)—4k,則 k部(k≥2)定向圖D是λ'最優(yōu)的；
　　當(dāng) k≥3且 n是偶數(shù)時(shí)，若最小度δ(D)≥(k-1）（n+4)—4k,則 k部(k≥2)定向圖D是λ'最優(yōu)的.
　　第三章研究了定向圖和二部定向圖是超