厦门理工学院学报
廈門理工學院學報
하문리공학원학보
JOURNAL OF XIAMEN UNIVERSITY OF TECHNOLOGY
2010年
1期
18-20,23
,共4页
几乎k-可扩图%几乎完美匹配%去边%加边
幾乎k-可擴圖%幾乎完美匹配%去邊%加邊
궤호k-가확도%궤호완미필배%거변%가변
设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性.
設G是具有奇數箇頂點的圖,k是非負整數且滿足V(G)≥2k+1,若G中任意一箇k-匹配都可以擴充為G的一箇幾乎完美匹配,則稱G是幾乎k-可擴圖.文中證明瞭連通的幾乎1-可擴圖與2-連通的幾乎k-可擴二部圖分彆添加一箇新邊後仍保持原來的可擴性.
설G시구유기수개정점적도,k시비부정수차만족V(G)≥2k+1,약G중임의일개k-필배도가이확충위G적일개궤호완미필배,칙칭G시궤호k-가확도.문중증명료련통적궤호1-가확도여2-련통적궤호k-가확이부도분별첨가일개신변후잉보지원래적가확성.