论文部分内容阅读
根据Hall定理,二部图G=（V1,V2;E）有一个浸润V1匹配的充要条件是：SV1,N（S）∩V2≥S,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数。当V1中的顶点数较多时,用该条件判定较为困难。本文给出了一个基于顶点度判别二部图有浸润匹配的条件,并应用该条件解决了一个关于图的二划分的问题。