正盈量二部图的最大匹配数下界的紧性  

作　　者：刘春扬[1] 

机构地区：[1]福建医科大学数理计算机教学部,福建福州350004

出　　处：《龙岩学院学报》2005年第6期9-10,12,共3页Journal of Longyan University

摘　　要：无向简单图G的亏度(deficiency)是未被最大匹配所覆盖的顶点数;一个二部图G(A,B)具有正盈量(positivesurplus)(对A而言)当且仅当对A的任何非空集合X所包含的顶点数一定小于其邻集所包含的顶点数。对具有正盈量的二部图,刻画了其当亏度def(G)给定时达到最大匹配数下界的二部图,从而验证了此类二部图最大匹配数下界的紧性。

关 键 词：二部图 最大匹配数 正盈量 

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