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

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

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

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