二部图匹配的一个判别条件  

A Sufficient Condition for Immersed-matching of Bipartite Graph

作　　者：黄威[1] 尚有林[1] 王琪凤[1] 

机构地区：[1]河南科技大学数学与统计学院,河南洛阳471023

出　　处：《河南科技大学学报（自然科学版）》2013年第4期85-87,1,共3页Journal of Henan University of Science And Technology:Natural Science

基　　金：国家自然科学基金项目(10971053)

摘　　要：根据Hall定理,二部图G=(V1,V2;E)有一个浸润V1匹配的充要条件是:SV1,N(S)∩V2≥S,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数。当V1中的顶点数较多时,用该条件判定较为困难。本文给出了一个基于顶点度判别二部图有浸润匹配的条件,并应用该条件解决了一个关于图的二划分的问题。According to the Hall theorem,a bipartite graph G=(V1 ,V2;E) has a V1 -immersed matching if and only if the number of the verteces in V2 that are adjacent to any subset S of V1 is not less than the number of vertices in S.It is difficult to be verified when the number of verteces in V1 is large.With degree of vertex,a sufficient condition to determine whether a bipartite graph has an immersed matching is presented.Using the condition,a problem on bipartition partition of graph is solved.

关 键 词：图论 二部图 匹配 顶点度 二划分 

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