饱和二部图  

Saturated Bipartite Graphs

作　　者：张国志[1] 王世英[2] 

机构地区：[1]晋中学院数学学院,山西晋中030600 [2]山西大学数学科学学院,太原030006

出　　处：《晋中学院学报》2010年第3期19-20,共2页Journal of Jinzhong University

基　　金：山西省自然科学基金资助项目(20041002);国家自然科学基金资助项目(60773131)

摘　　要：没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X■V(G),Γ(X)表示V(G)中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=(U,W)是饱和的当且仅当(a)存在唯一X■U,使得X>Γ(X),X-1>Γ(X)且G的导出子图G[X∪Γ(X)]是完全二部图;(b)G的导出子图G[(U-X)∪(W-Γ(X))]是完全二部图,且满足U-X+1=W-Γ(X);(c)U-X中每个顶点与W中的每个顶点都相邻,且X∪(W-Γ(X))是图G的一个独立集.A bipartite graph G without a perfect matching is said to be saturated if any new line is added,the resulting bipartitegraph having a perfect matching. For Xlohtai in V（G）,Γ（X）denotes all points in V（G）which are adjacent to at least one point of X. It isobtained that a bipartite graph G=（U,W）is saturated if and only if （a）there is only one Xlohtai in U such that X Γ（X） with X -1=Γ（X） and the induced subgraph G[X∪Γ（X）]is a complete bipartite graph;（b）G[（U-X）∪（W-Γ（X））]with U-X ＋1= W-Γ（X）is a complete bipartite graph;（c）every point of U-X is adjacent to every point of W and X∪（W-Γ（X））is an independent set.

关 键 词：饱和二部图 完美匹配 集合 

分 类 号：O157.5[理学—数学]