郑州铁路职业技术学院学报
鄭州鐵路職業技術學院學報
정주철로직업기술학원학보
JOURNAL OF ZHENGZHOU RAILWAY VOCATIONAL COLLEGE
2005年
1期
34-35
,共2页
导出匹配%最小废%度条件
導齣匹配%最小廢%度條件
도출필배%최소폐%도조건
我们说简单图G是2k点可删的导出匹配可扩图,是指如果对于任意的s( )V(G),|S|=2k,都有G-S是导出匹配可扩图.简单图G是2k点可删的导出匹配可扩图的度条件是: 若图G有2n个顶点且n≥4、k是一个小于或等于n-3的正整数,则当δ(G)≥4n+2k/3时,图G是2k点可删的导出匹配可扩图,并且[(4n+2k)/3]是2k点可删的导出匹配可扩图G的最小度的最小值.
我們說簡單圖G是2k點可刪的導齣匹配可擴圖,是指如果對于任意的s( )V(G),|S|=2k,都有G-S是導齣匹配可擴圖.簡單圖G是2k點可刪的導齣匹配可擴圖的度條件是: 若圖G有2n箇頂點且n≥4、k是一箇小于或等于n-3的正整數,則噹δ(G)≥4n+2k/3時,圖G是2k點可刪的導齣匹配可擴圖,併且[(4n+2k)/3]是2k點可刪的導齣匹配可擴圖G的最小度的最小值.
아문설간단도G시2k점가산적도출필배가확도,시지여과대우임의적s( )V(G),|S|=2k,도유G-S시도출필배가확도.간단도G시2k점가산적도출필배가확도적도조건시: 약도G유2n개정점차n≥4、k시일개소우혹등우n-3적정정수,칙당δ(G)≥4n+2k/3시,도G시2k점가산적도출필배가확도,병차[(4n+2k)/3]시2k점가산적도출필배가확도G적최소도적최소치.
