R-二部图上的R-可行匹配问题

摘要

设图G=(V, E)有边子集RE若G′=(V,E-R)是具有二分类(X,Y)的二部图,则称图G是R-二部图.对图G的匹配M,若由所有M饱和点导出的子图不包含R中的边,则称M是R-可行匹配.先讨论R-二部图上的R-可行匹配数与R-可行覆盖数的关系和一类特殊R-二部图上的R-可行匹配数,然后证明了R-二部图上的R-可行匹配问题的NP-困难性,基于匈牙利算法给出了该问题的近似算法.