标签: 二分图

1 篇文章

二分图 & 最大匹配 & 匈牙利算法
定义 二分图 对于一个无向图 $G=(V, E)$,可以将 $V$ 分为两个不相交的子集,使得任意一条边的顶点分属两个不同的点集,那么这个无向图是二分图。 匹配 对于无向图 $G=(V, E)$,取边集的子集 $E^*$,使得 $E^*$ 中任意两条边没有公共顶点,那么 $E^*$ 是图 $G$ 的一个匹配,又称边独立集。 最大匹配 边数最多的匹配…