圖的超級限制邊連通性和邊連通度的下界.pdf

1、多處理機系統(tǒng)的互連網(wǎng)絡拓撲通常以（有向或無向）圖為數(shù)學模型.設G是無向簡單連通圖，F(xiàn)是G的一個邊割，如果G-F不含孤立點，則稱F是G的一個限制邊割.最小限制邊割所含的邊數(shù)稱為G的限制邊連通度.限制邊連通度作為邊連通度的推廣，是計算機互連網(wǎng)絡可靠性的一個重要度量.超級限制邊連通性是比限制邊連通度更精確的一個網(wǎng)絡可靠性指標.一個圖是超級限制邊連通的，如果它的任一最小限制邊割都孤立一條有最小邊度的邊.本文主要研究了直徑為2的圖的超級限制邊連通

2、性和有向圖的邊連通度的下界.
　　在第一章第一節(jié)我們給出本文將用到的圖論方面的術語、記號.在第二節(jié)我們介紹了關于邊連通性方面的基本概念和基本結(jié)論.
　　本文第二章研究了幾類直徑為2的圖的超級限制邊連通性.在第一節(jié)我們給出后文將要用到的幾個簡單事實，并簡略總結(jié)了直徑為2的圖的連通性方面的已有結(jié)論.在第二節(jié)，直徑為2的圖為超級限制邊連通的幾個充分條件被給出，具體是:
　　(1)設G是階為v(≥4)的一個圖.若對G的任意一對

3、不相鄰頂點x，y，都有|N(x)∩N（y)|≥3;對任意一對相鄰的點u，v，都有|N（u）∩N（v）|≥2，那么圖G是超級限制邊連通的，除非G屬于一類特殊的圖.
　　(2)設G是階為v(≥4)的一個圖.若對圖G的任意一對不相鄰頂點u，v滿足G[N（u）∩N(v)]中至少包含三條邊，那么圖G是超級限制邊連通的，除非G屬于一類特殊的圖.
　　(3)設G是階為v(≥13)的一個圖.若對G中的任意兩個不相鄰的頂點u，v，有|N(u)

4、∩N(v)|≥3且最小邊度ξ(G)≤(「)v/2」+2，則圖G是超級限制邊連通的.
　　(4)設G是階為v(≥10)的一個圖且最小度δ(G)≥3.若對它的任意兩個相鄰頂點x，y，有|N(x)∩N(y)|≤1;對它的任意兩個不相鄰頂點u，v，有|N(u)∩N(v)|≥2，則G是超級限制邊連通的.
　　本文第三章研究了有向圖，定向圖，定向二部圖的邊連通度的下界.結(jié)論如下:
　　(5)設D是階為v(≥4)的一個強連通有向圖，

5、邊連通度為λ(D)，最小度為δ(D)，最小弧度為ξ(D).若λ(D)＜δ(D)，則λ(D)≥ξ(D)-v/2+2.
　　(6)設D是階為v(≥6)的一個強連通定向圖，邊連通度為λ(D)，最小度為δ(D)，度序列為d1≥d2≥…≥dv.若λ(D)≤δ(D)-k(1≤k≤δ(D)且k為整數(shù)），則λ(D)≥1/24k+1∑i=0dv-i-（2k+1）（v-2k-2）/2.
　　(7)設D是階為v(≥6)的一個強連通定向二部圖，邊連