圖的四階限制邊連通度的研究.pdf

1、圖的限制性邊連通度問題及許多理論都是源自大型網絡的設計和可靠性分析．另外限制性邊連通度在實際問題中有著廣泛的應用，是圖論研究中一個很活躍的課題，各類限制邊連通度問題被相繼提出并加以發(fā)展、應用． 如果不是特別說明，本文中談及的所有圖都是簡單連通的，階至少是8.當研究網絡可靠性的時候，經常考慮這樣一種圖模型，它的節(jié)點不失效，但是它的連線，也就是邊可以獨立地等可能地失效，失效的概率是p ∈ (0，1)．這就是非常有名的Moore-Sh

2、annon網絡模型[1，2]．令G是—個Moore-Shannon網絡模型，邊數為h的邊割的數目用Ch表示，如果G恰好有e條邊，則它不連通的概率P(G，p)就可以表示為； P(G,p)=∑eh=1Chph(1-p)e-h. 顯然，P(G，p)的值越小，網絡的可靠性越好．如果能確定所有的系數Ch，那么這個網絡的可靠性就是確定的．但是對于任意圖，Provan和Ball在文獻[3]中指出，確定所有的系數Ch是一個NP-hard

3、問題． 用Ω(n，e)表示n個點e條邊的圖的集合，當p充分小時，在Ω(n，e)中，為了最小化P(G，p)，邊連通度λ(G)起了非常重要的作用． Bauer et al.在文獻[6]中指出，當p充分小時，對G1，G2∈Q(n，e)，如果λ(G1)>λ(G2)，則P(G1，p)

4、通度的概念進一步推廣，提出了k階限制邊割和k階限制邊連通度的概念[5]．目前，對于k=1，2，3的情況已經有了廣泛而深入的研究． 在本文第一章中，我們主要介紹了文章所涉及的一些概念、術語和符號．記圖G的頂點集為V(G),邊集為E(G).對于X ∈ V(G),令G[X]表示X的導出子圖,X=V(G)-X，[X,-X]表示G中一端在X中，另一端在-X中的邊的集合．如果G是一個連通圖，S ∈E(G)使得G-S不連通，且G—S的每一個分

5、支至少有4個點，則S稱為是G的一個四階限制邊割．G中所有四階限制邊割的最小階稱為是G的四階限制邊連通度，用λ4(G)表示．如果λ4(G)存在，則稱G是λ4-連通的．如果G中的一個四階限制邊割滿足|S|=λ4，則S稱為λ4-割．在第二章中，我們研究圖的四階限制邊連通度的存在性問題．階至少為8的連通圖F若含有一個割點s使得F-s的每—個分支的階至多是3，則稱F為4-花．三角形每個頂點粘合一個3階完全圖的子圖所構成的圖，稱為三角支撐圖．利用這

6、兩類圖我們刻畫了階至少是9的非λ4-連通的圖． 在文獻[20]中，歐見平證明了階至少是11的λ4-連通圖G滿足λ4(G)≤ξ4(G)，其中ξ4(G)=min{|(X，-X)|：X ∈ V(G)，|X|=4，G[X]是連通的)，本文第三章對這個定理給出了一個簡潔的證明． 滿足λ4(G)=ξ4(G)的λ4-連通圖G稱為是λ4-最優(yōu)的．如果X ∈ V(G)，[X，-X]是一個λ4-割，則X稱為G的一個λ4-碎片．令T4(G)=