- 二分图:简单理解,一张图,可以分成两个点集,其中每个点集内部不存在边,边只出现在两个集合之间。
- 匹配:二分图的一个边集E,其中任意一条边的两个端点出自不同的集合,且任意两条边都不依附于同一个顶点。
- 最大匹配:匹配的最大数量。
- 点覆盖:G(V, E),一个点集W,使得任意边都至少有一个端点在W中。
- 最小点覆盖:点覆盖最小的点集的大小。
- 独立集:点集V中,任意两点都不存在边相连。
- 最大独立集:独立集最大的集合。
- 最小覆盖问题:分成两种,一种是不相交的,另一种是可以相交的。以不相交为例:最少的不相交路径能够覆盖图中所有的点。