图论（最大二分匹配） _最大二分匹配

【图论（最大二分匹配）】二分图是其顶点可以分为两个独立的集合L和R的图, 这样每个边（u, v）要么连接从L到R的顶点, 要么连接从R到L的顶点。换句话说, 对于每个边（u, v）u∈L和v∈L。我们也可以说不存在连接相同集合的顶点的边。

文章图片
匹配是一个二部图, 它是一组边的选择, 没有两个边共享端点。给定无向图G =（V, E）, “匹配”是边M?E的子集, 使得对于所有顶点v∈V, M的最多一个边入射在v上。
最大匹配是最大基数的匹配, 即匹配M, 对于任何匹配M’ , 我们都有| M |> | M’ |。
寻找最大的二分匹配我们可以使用Ford-Fulkerson方法在| V |的时间多项式中在无向二分图G =（V, E）中找到最大匹配。和| E |。技巧是为二部图G构造流网络G =（V’ , E’ ）, 如下所示。我们让源s和接收器t为不在V中的新顶点, 并且让V’ = V∪{s, t}。如果G的顶点分区为V =L∪R, 则G’ 的有向边为E的边缘, 从L到R, 以及| V |新的有向边：