计算机问题求解-论题3-12 图中的匹配与因子分解 2020-12-2
计算机问题求解---论题3-12 图中的匹配与因子分解 2020-12-2
问题1：如何用图模型表达以下问题及其解？ There is a related mathematical question here.Let U and W be two sets.Does there exist a one-to-one function f:U>W? lU<=|W What if the image of each element of U cannot be just any element of W? G: B M
问题1:如何用图模型表达以下问题及其解？ • There is a related mathematical question here. Let U and W be two sets. Does there exist a one-to-one function f : U → W ? • What if the image of each element of U cannot be just any element of W? |U|<=|W|
什么是matching？Match的核心概念是什么？ a d h t Q 0 R A B D (a) (b) Figure 8.2:A matching in a bipartite graph 独立边集是匹配的核心概念
什么是matching？Match的核心概念是什么？ 独立边集是匹配的核心概念
匹配、极大匹配、最大匹配、完美匹配 问题2：你能用集合论里面的基本概念解 释匹配？极大匹配？完美匹配吗？ NA e V1 es 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 问题2：你能用集合论里面的基本概念解 释匹配？极大匹配？完美匹配吗？
二部图中最大匹配的存在性 Theorem 8.3 Let G be a bipartite graph with partite sets U and W such that r=Us W.Then G contains a matching of cardinality r if and only if G satisfies Hall's condition. 必要性： G B F K L M
二部图中最大匹配的存在性 必要性：