中国科学A辑
中國科學A輯
중국과학A집
SCIENCE IN CHINA (SERIES A)
2006年
6期
659-668
,共10页
系列平行图%边连通度%边覆盖染色%极大-极小定理
繫列平行圖%邊連通度%邊覆蓋染色%極大-極小定理
계렬평행도%변련통도%변복개염색%겁대-겁소정리
任意给定系列平行图G的一个顶点v*,则G的边集可划分为k=min{k'(G)+1,δ(G)}个子集,使得每一个边子集覆盖可能除v*以外的所有顶点,其中δ(G)为G的最小度,K'(G)为G的边连通度.另外,证明了该结果是最好的可能,并且通过此证明过程得到一个可找到该划分的多项式时间算法.
任意給定繫列平行圖G的一箇頂點v*,則G的邊集可劃分為k=min{k'(G)+1,δ(G)}箇子集,使得每一箇邊子集覆蓋可能除v*以外的所有頂點,其中δ(G)為G的最小度,K'(G)為G的邊連通度.另外,證明瞭該結果是最好的可能,併且通過此證明過程得到一箇可找到該劃分的多項式時間算法.
임의급정계렬평행도G적일개정점v*,칙G적변집가화분위k=min{k'(G)+1,δ(G)}개자집,사득매일개변자집복개가능제v*이외적소유정점,기중δ(G)위G적최소도,K'(G)위G적변련통도.령외,증명료해결과시최호적가능,병차통과차증명과정득도일개가조도해화분적다항식시간산법.
