極大弧連通圖的充分條件.pdf

1、多處理機系統(tǒng)的互聯(lián)網(wǎng)絡(luò)拓撲通常以無向（有向）圖為數(shù)學(xué)模型，此時，圖的頂點集表示多處理機系統(tǒng)中的所有處理機，邊（?。┘硎鞠到y(tǒng)中處理機之間的通信線路.可靠性（容錯性）是網(wǎng)絡(luò)設(shè)計中必須考慮的一個因素，它可用圖的邊（弧）連通度來度量.此時，圖的邊（?。┻B通度越大，對應(yīng)網(wǎng)絡(luò)的可靠性就越好.我們將邊（?。┻B通度達到極大的圖稱為極大邊（?。┻B通圖.本文主要研究了有向圖的弧連通度和無向圖的限制邊連通度，共分為四章.
　　在第一章，我們給出本文將

2、用到的圖論方面的主要術(shù)語、記號.
　　在第二章，我們通過引進孤立弧的概念，給出強連通有向圖和強連通二部有向圖是極大弧連通的充分條件.主要結(jié)果如下:
　　(1)設(shè)D是一個弧連通度為λ，最小度為δ的強連通有向圖.如果對所有的3-距離極大的點集對X，Y(C)V，在D[X∪Y]中存在一條孤立弧，那么λ=δ.
　　(2)設(shè)D是一個弧連通度為λ，最小度為δ的強連通二部有向圖.如果對所有的(4，4)-距離極大的點集對X，Y(C)V，

3、在D[X∪Y]中存在一條孤立弧，那么λ=δ.
　　(3)設(shè)D是一個強連通有向圖，S=[X，(X)]是D的一個最小弧割，其中(X)=V\X.如果存在一點u∈X，使得對任意的x∈X\{u}都有|N+(x)∩(X)|≥1，或者存在一點ū∈(X)，使得對任意的y∈(X)\{ū}都有|N-(y)∩ X|≥1，那么λ=δ.
　　在第三章，我們研究了一類強乘積有向圖的弧連通度.主要結(jié)果如下:
　　(1)對i=1，2，設(shè)Di是一個非平

4、凡強連通有向圖，ni，mi，δi，λi分別表示Di的頂點數(shù)，弧數(shù)，最小度和弧連通度.如果δ+i=δ-i=δi，那么λ(D1(因)D2)≤min{λ1(n2+m2)，λ2(n1+m1)，δ1+δ2+δ1δ2}.
　　(2)設(shè)D2是一個非平凡強連通有向圖，n2，m2，δ2，λ2分別表示D2的頂點數(shù)，弧數(shù)，最小度和弧連通度.如果δ+2=δ-2=δ2，那么λ(C2(因)D2)=min{4λ2，1+2δ2}.進一步，若δ2≤2λ2-1，則C

5、2(因)D2是極大弧連通的.
　　在第四章，我們給出p-p-限制邊連通度λp，p(G)是p-q-限制頂點連通度κp，q(G)的上界的一些充分條件.主要結(jié)果如下:
　　(1)設(shè)G是一個κp，q-連通和λp，p-連通圖，(q≤p).若存在最小的p-p-邊割S=[X,(X)使得在G[X]中含有一個q階連通子圖G1滿足N(G1)∩(X)=(φ)，則κp，q(G)≤λp，p(G).
　　(2)設(shè)G是一個κp，q-連通和λp，p-