计算机问题求解-论题3-11 图中的匹配与因子分解 2016-11-23
计算机问题求解---论题3-11 图中的匹配与因子分解 2016-11-23
要在左图所示的棋盘上放 × 置4个士兵，任何一行或者 一列恰好放一个，但不能 X 放在有标记的格子中。 × × 问题1： × 你能建一个图 模型来解这样 的问题吗？
X X 问题2： 你认为在这个 模型中。问题的 解应该是什么？ 边集的一个子集，其中没有任何两条边有公共顶点
i1 i2 i3 i4 j1 j2 j3 j4 边集的一个子集, 其中没有任何两条边有公共顶点
什么是matching? d 8 A B D E (a) (b) Figure 8.2:A matching in a bipartite graph 独立边集是匹配的核心概念。问题3：你能用集 合论里面的基本概念解释matching吗？极大匹配？ 完美匹配？
什么是matching？ 独立边集是匹配的核心概念。问题3：你能用集 合论里面的基本概念解释matching吗？极大匹配？ 完美匹配？
匹配、极大匹配、最大匹配、完美匹配 e e e3 e e2 e e es e es )6 6 6
匹配、极大匹配、最大匹配、完美匹配 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5 v1 v2 v3 v4 v5 v6 e1 e4 e2 e3 e5