有向圖連通度的下界.pdf

1、多處理機系統(tǒng)的互聯(lián)網(wǎng)拓?fù)渫ǔＲ杂邢驁D或無向圖為數(shù)學(xué)模型，用（有向圖或無向圖）中的頂點集來表示多處理機系統(tǒng)中的所有處理機，用邊集或弧集來表示系統(tǒng)中處理機之間的通信線路.對互聯(lián)網(wǎng)的性能一個關(guān)鍵要求是希望網(wǎng)絡(luò)的可靠性（容錯性）好，這對應(yīng)于圖論的術(shù)語來說，就是希望圖的連通度和邊連通度盡可能的大.
　　在第一章第一節(jié)，我們給出本文將用到的圖論方面的主要術(shù)語、記號.在第二節(jié)，我們介紹了本文將要用到的基本的概念和結(jié)論.
　　本文第二章的主

2、要研究了一類特殊的有向圖-定向圖連通度的下界，給出了定向圖、定向二部圖的連通度的下界:
　　(1)設(shè)D是一個n階定向圖，連通度為κ，度序列為(d1，d2，…，dn).若κ≤δ-k(1≤k≤δ，且k為整數(shù))，則κ≥1/2k+1（2k+1∑i=1dδ-k+i+2k∑i=0dn-i）+2k+2-n.
　　(2)設(shè)D是一個n階定向二部圖，連通度為κ，度序列為(d1，d2，…，dn).若κ≤δ-k(1≤k≤δ，且k為整數(shù))，則κ≥1/

3、k+1(k+1∑i=1dδ-k+i+3k+2∑i=0dn-i)-n+4.
　　(3)設(shè)D是一個團數(shù)ω(D)≤p的n階定向圖，連通度為κ，它的度序列為(d1，d2，…，dn).若κ≤δ-k(1≤k≤δ，且k為整數(shù))，則κ≥1/2k+1(2k+1∑i=1dδ-k+i+2k∑i=0dn-i)-p-1/p(2k+1)+4k+2-n.
　　第三章主要是給出了有向圖連通度的下界:
　　(1)設(shè)D是一個n階的有向圖，連通度為κ，它的

4、度序列為(d1，d2，…，dn).若κ≤δ-k(1≤k≤δ，且k為整數(shù))，則κ≥1/k+1（k+1∑i=1dδ-k+i+k∑i=0dn-i）+2-n.
　　(2)設(shè)D是一個n階有向二部圖，連通度為κ，它的度序列為(d1，d2，…，dn).若κ≤δ-k（1≤k≤δ，且k為整數(shù)），則κ≥1/k（k∑i=1dδ-k+i+3k-1∑i=0dn-i)-n.
　　第四章主要研究了有向圖邊連通度的下界:
　　(1)設(shè)D是一個團數(shù)為ω