数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究匹配图
匹配图是图的一个子图，其中没有边彼此相邻。简单来说，任意两条边之间不应该有任何公共顶点。
匹配
设 'G' = (V, E) 为一个图。如果 G 的每个顶点最多与 M 中的一条边相关联，则子图称为匹配 M(G)，即：
deg(V) ≤ 1 ∀ V ∈ G
这意味着在匹配图 M(G) 中，顶点的度数应为 1 或 0，其中边应来自图 G。
符号 − M(G)
示例
.jpg)
在匹配中，
如果 deg(V) = 1，则 (V) 被称为匹配的
如果 deg(V) = 0，则 (V) 未匹配。
在匹配中，没有两条边是相邻的。这是因为，如果任意两条边相邻，则连接这两条边的顶点的度数将为 2，这违反了匹配规则。
最大匹配
如果不能将图 'G' 的其他任何边添加到 M，则称图 'G' 的匹配 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 不一定是完美的。
示例
它是匹配，但不是完美匹配，即使它具有偶数个顶点。
340 次浏览
