图论 - 匹配

匹配图是图的子图，其中没有彼此相邻的边。简单地说，任何两条边之间不应该有任何公共顶点。

匹配

让 '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 中，则图“G”的匹配 M 被称为最大。

例子

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

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

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

例子

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

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

度(V) = 1 ∀ V

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

例子

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

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

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

例子

注意- 上述陈述的反面不一定成立。如果 G 有偶数个顶点，则 M1 不必是完美的。

例子

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