1-可擴圖與圈邊連通度的有效判定算法.pdf

1、在該文中,我們設計了三個有效算法,并且對于算法的正確性以及時間復雜度給出了嚴格的證明,從而充分保證了算法的準確高效.在第一章中,我們首先給出對于該文中所使用的基本術語和概念的說明,然后針對我們描述的算法所涉及的分支領域,我們用兩節(jié)的內容分別闡述了對集理論和連通度理論中相關研究的歷史與最新進展.在第二章中,我們依據耳朵分解原理,可以得到如下結果,如果G是一個具有二分類(X,Y)的偶圖且M是G的一個完美對集,G是1-可擴圖當且僅當G有如下耳

2、朵分解G=e+P<,1>+P<,2>+…+P<,r>,使得e∈M并且P<,i>是一條起始及終止于非對集邊的M-交錯路.文中給出了一個高效算法判定一個偶圖是否為1-可擴圖,并找出該圖的耳朵分解.算法的時間復雜度為0(|E|<'2>).判定一個圖的圈邊連通度問題是否為P問題是一個長期沒有解決的問題,即使對于正則圖到目前為止也是如此.在第三章中,我們依據寬度優(yōu)先搜索策略,可以得到如下結果,對于每個e∈E(G),至多有O(k<'4>|V|<'2

3、>)個包含e且長度不大于4(1og<,k-1>v+2)的圈.文中給出了第一個判定k-正則圖(k≥3)中圈邊連通度的有效算法.算法的時間復雜度為O(k<'11>|V|<'8>),尤其在立方圖中其時間復雜度為0(|V|<'8>).在第四章中,我們首先刻劃了具有無窮圈邊連通度的圖,可以得到如下結果,如果G是一個連通圖,且δ(G)≥3,g(G)≥5,那么cλ(G)≠∞當且僅當v(G)≥2g(G);如果G是一個連通圖,且δ(G)≥3,g(G)=4