带花树(blossom)

在求二分图最大匹配的问题中,由于二分图不存在奇环的特殊性质,因此我们可以把整张图的顶点分成两个集合A,B.所有与某个顶点邻接的顶点都不与该顶点在同一个集合,由此便可以设计出非常方便且复杂度较优秀的匹配算法,在此不多加论述.而在存在奇环的一般图中,我们便不能直接使用二分图最大匹配的算法进行匹配,需要对奇环进行特殊的处理,这就引出了用于一般图最大匹配的算法——带花树算法.最大匹配数是图的一个重要性质,因此带花树算法也是图论中非常重要的一个算法.