關(guān)于正則圖的圈邊連通度判定算法.pdf

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

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

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