二分图的最大匹配

      首先，介绍一些概念：

          二分图：二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集（A,B），并且图中的每条边（i,j）所关联的两个顶点i和j分别属于这两个不同的顶点集（i in A,j in B），则称图G为一个二分图。                                                                 

      匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，这称M是一个匹配。选择这样的边数最大的子集的问题称为图的最大匹配问题。如果一个匹配中，图的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

    例如，图 3、图 4 中红色的边就是图 2 的匹配。