河南科学
河南科學
하남과학
HENAN SCIENCE
2008年
1期
15-18
,共4页
导出匹配%完美匹配%可扩的%循环图
導齣匹配%完美匹配%可擴的%循環圖
도출필배%완미필배%가확적%순배도
如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±k(mod2n)的i和j,均有xixj∈E(G),则称其为步长为1和k的循环图,记为C2n(1,k).通过详细讨论循环图的导出匹配可扩性,具体给出了循环图中的部分图类的导出匹配可扩性.
如果一箇圖的任何一箇導齣匹配都能包含在一箇完美匹配噹中,就稱之為導齣匹配可擴的.對有2n箇頂點x1,x2,…,x2n的圖,如果對于i-j≡±1(mod2n)或者i-j≡±k(mod2n)的i和j,均有xixj∈E(G),則稱其為步長為1和k的循環圖,記為C2n(1,k).通過詳細討論循環圖的導齣匹配可擴性,具體給齣瞭循環圖中的部分圖類的導齣匹配可擴性.
여과일개도적임하일개도출필배도능포함재일개완미필배당중,취칭지위도출필배가확적.대유2n개정점x1,x2,…,x2n적도,여과대우i-j≡±1(mod2n)혹자i-j≡±k(mod2n)적i화j,균유xixj∈E(G),칙칭기위보장위1화k적순배도,기위C2n(1,k).통과상세토론순배도적도출필배가확성,구체급출료순배도중적부분도류적도출필배가확성.