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

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

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

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

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

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