最大b匹配的花算法

1引言b匹配问题是匹配问题的推广,它在国内研究较少,但在国外已有一定研究．文献[3]给出了b匹配的应用实例,文献[4]～[6]给出了b匹配算法的研究成果,这些算法主要有两类:第一类为通过b匹配问题的线性规划模型求解,第二类为将b匹配问题转化为匹配问题求解．本文首次提出增广迹的概念,证明定理1[M为G的最大b匹配(?)G中不存在M增广迹]的正确性,并仿照最大匹配的花算法设计最大b匹配的花算法,即直接对b匹配问题求解,避免将b匹配问题转化为匹配问题,这样就可以将各顶点b(vi)