關于正則圖的圈邊連通度判定算法.pdf

1、一個網(wǎng)絡可以用一個連通圖來表示，其中圖的頂點表示網(wǎng)絡中的組件，邊表示兩個組件之間的通信信道。圖的連通度可以衡量網(wǎng)絡的穩(wěn)定性。一般來說，一個圖的連通性越好，它所代表的網(wǎng)絡越穩(wěn)定。然而，連通度衡量網(wǎng)絡的可靠性是有缺陷的。于是，學者們先后引入各種連通度，包括圈邊連通度。與連通度相比，圈邊連通度不受圖的最小度限制，從而可以更好地衡量網(wǎng)絡的連通性。 長期以來，關于一般圖的圈邊連通度判定是否為P問題還沒有得到解決。LOU和WANG[1]給出

2、了第一個關于K正則圖的圈邊連通度的判定算法，其時間復雜度是O(k11｜V｜8)，此復雜度在實際應用中稍大。因此，進一步提高算法的執(zhí)行效率具有重要意義，也是本文要研究的問題。本文設計的改進算法將在前人工作的基礎上，通過對正則圖的結構作更深入細致的分析，來達到改進算法的目的，新算法的時間復雜度是O(k9｜V｜6)。在研究的過程中，我們證明了以下一個引理： 引理4.2.1圖G是連通的k—正則圖。如果cλ(G)<(k—2)g，則刪除一個

3、最小圈邊割S，G—S有兩個連通分支，每一個連通分支各包含一個圈C。如果C是奇圈，則｜V(C)｜≤2｜logk-1v(G)｜+5；如果C是偶圈，則｜V(C)｜≤2｜logk-1v(G)｜+6。 本文第一部分介紹圖的連通度的研究現(xiàn)狀和進展，指出本文的選題背景和研究意義。第二部分綜述本文所需要的預備知識，包括一些關于圖的基本概念和專業(yè)術語，有關連通度的一些基本結論和一些引理。第三部分基于文獻[1]關于3-正則圖的圈邊連通度判定算法設計