图论 - 匹配

匹配图是图中没有相邻边的子图。简单来说，任何两条边之间都不应该有任何共同的顶点。

匹配

设"G"= (V, E) 为图。如果 G 的每个顶点最多与 M 中的一条边相关，则子图称为匹配 M(G)，即

deg(V) ≤ 1 ∀ V ∈ G

这意味着在匹配图 M(G) 中，顶点的度应为 1 或 0，其中边应与图 G 关联。

符号 − M(G)

示例

在匹配中，

如果 deg(V) = 1，则 (V) 被称为匹配

如果 deg(V) = 0，则 (V) 不匹配。

在匹配中，没有两条边是相邻的。这是因为，如果任何两条边相邻，那么连接这两条边的顶点的度数将为 2，这违反了匹配规则。

最大匹配

如果图"G"的匹配 M 没有其他边可以添加到 M，则称其为最大匹配。

示例

上图中的 M1、M2、M3 是 G 的最大匹配。

最大匹配

又称为最大最大匹配。最大匹配定义为具有最大边数的最大匹配。

"G"的最大匹配中的边数称为其匹配数。

示例

对于上例中给出的图，M1 和 M2 是"G"的最大匹配，其匹配数为 2。因此，通过使用图 G，我们只能形成最多只有 2 条边的子图。因此，匹配数为 2。

完美匹配

如果图 g (G) 的每个顶点都恰好与匹配 (M) 的一条边相关，则图 (G) 的匹配 (M) 被称为完美匹配，即

deg(V) = 1 ∀ V

子图中每个顶点的度数都应为 1。

示例

在下图中，M1 和 M2 是 G 完美匹配的示例。

注意 − 图的每个完美匹配也是图的最大匹配，因为在完美匹配图中没有机会再添加一条边。

图的最大匹配不必是完美的。如果图"G"具有完美匹配，则顶点数 |V(G)| 为偶数。如果为奇数，则最后一个顶点与另一个顶点配对，最后剩下一个顶点，该顶点不能与度数为零的任何其他顶点配对。它明显违反了完美匹配原则。

示例

注意 − 上述陈述的逆命题不一定成立。如果 G 有偶数个顶点，则 M1 不必完美。

示例

它是匹配的，但不是完美匹配，即使它有偶数个顶点。