科学技术与工程
科學技術與工程
과학기술여공정
SCIENCE TECHNOLOGY AND ENGINEERING
2008年
13期
3579-3581
,共3页
图%k阶限制边连通度%λk-最优
圖%k階限製邊連通度%λk-最優
도%k계한제변련통도%λk-최우
设S是图G的一个边子集,若G-S不连通且每个分支的阶至少为k,则称S为G的一个k-限制边割.若G有k-限制连割,G的最小k-限制边割的边数称为G的k阶限制边连通度,记为λk(G).记ξk(G)=min{|[X,]|∶|X|=k,G|X|连通},若λk(G)=ξk(G),则称G是λK-最优的.证明了若对G中任意一对不相邻的顶点x,y都有d(x)+d(y)≥n+2(k-2),且G不是G*k图,则G是λk-最优的.
設S是圖G的一箇邊子集,若G-S不連通且每箇分支的階至少為k,則稱S為G的一箇k-限製邊割.若G有k-限製連割,G的最小k-限製邊割的邊數稱為G的k階限製邊連通度,記為λk(G).記ξk(G)=min{|[X,]|∶|X|=k,G|X|連通},若λk(G)=ξk(G),則稱G是λK-最優的.證明瞭若對G中任意一對不相鄰的頂點x,y都有d(x)+d(y)≥n+2(k-2),且G不是G*k圖,則G是λk-最優的.
설S시도G적일개변자집,약G-S불련통차매개분지적계지소위k,칙칭S위G적일개k-한제변할.약G유k-한제련할,G적최소k-한제변할적변수칭위G적k계한제변련통도,기위λk(G).기ξk(G)=min{|[X,]|∶|X|=k,G|X|련통},약λk(G)=ξk(G),칙칭G시λK-최우적.증명료약대G중임의일대불상린적정점x,y도유d(x)+d(y)≥n+2(k-2),차G불시G*k도,칙G시λk-최우적.
