ch5匹配1

### 第五章 匹配 #### 5.1 匹配 **匹配**是指图G的一个边的子集M，其中M内的每条边都不共享任何顶点。具体来说： - **定义**：若M⊆E，且M中的边两两不相邻，则称M为图G的一个匹配。 - **饱和**：若顶点u与v都在M中被一条边连接，则称u与v在M下相匹配，并称M饱和了u与v。 - **完美匹配**：如果一个匹配M使得图G中的每一个顶点都被M饱和，则称M为图G的一个完美匹配。 - **最大匹配**：如果一个匹配M的边数无法通过添加新的边来增加，则称M为图G的一个最大匹配。 此外，还定义了一些特殊的路径类型： - **M-交错路径**：如果一条路径P的边交替地属于M和不属于M，则称P为M-交错路径。 - **M-可扩路径**：如果一条路径既是M-交错路径，且它的起点和终点均为M-不饱和的，则称该路径为M-可扩路径。 **定理5.1 (Berge,1957)**：M为G中的最大匹配当且仅当G中不存在M-可扩路径。 **证明**： - **必要性**：假设存在M-可扩路径P，则可以构造一个新的匹配M' = MΔE(P)，即M与P的边的异或运算。显然|M'| = |M| + 1，这与M为最大匹配矛盾。 - **充分性**：假设M不是最大匹配，存在比M更大的匹配M*。考虑G[MΔM*]，得到的图H的每个分支要么是一条闭合路径，要么是一条开放路径。因为|M*| > |M|，所以必然存在一个以M*-饱和的顶点为起点和终点的开放路径P，这表明P是一条M-可扩路径，与假设矛盾。 #### 5.2 独立集、团、覆盖、和匹配间的关系 本节讨论独立集、团、覆盖以及它们与匹配之间的关系。 - **独立集**：图G的一个顶点子集S，其中任意两个顶点都不相邻。 - **团**：图G的一个完全子图。 - **覆盖**：图G的一个顶点子集S，其中图G的每条边至少有一个端点位于S中。 - **邻集**：对于图G的顶点子集S，其邻集N(S)定义为所有与S中的顶点相邻的顶点的集合。 **定理5.2 (Hall's theorem)**：在偶图G=(X,Y,E)中，G包含一个使X中每个顶点都饱和的匹配当且仅当对于X的任意子集S，都有|N(S)|≥|S|。 **证明**： - **必要性**：如果存在一个匹配M使得X中的每个顶点都饱和，则对于任意的S⊆X，M至少包含|S|条边，因此|N(S)|≥|S|。 - **充分性**：假设存在偶图G满足条件但没有这样的匹配。考虑G的最大匹配M*及其不饱和的顶点u，通过构建Z集合和利用M*的最大性质，可以证明出矛盾。 #### 5.3 偶图的匹配和覆盖 继续讨论偶图中的匹配问题。 - **偶图**：一种二分图，其顶点集可以分为两个互不相交的子集X和Y，图中的每条边都连接X和Y中的顶点。 **定理5.2** (Hall's theorem) 的证明进一步展示了如何确定一个偶图是否存在使X中每个顶点都饱和的匹配。 #### 5.4 完美匹配 完美匹配是匹配的一个特殊形式，当图中的每个顶点都被匹配时，我们称之为完美匹配。 - **推论 5.2 (marriage theorem)**：如果G是一个k-正则偶图（k>0），那么G具有一个完美匹配。 - **证明**：利用Hall's theorem进行证明，通过展示对于X的任意子集S，都有|N(S)|≥|S|。 #### 5.5 人员分派问题 人员分派问题是一种实际应用问题，可以转化为图论中的匹配问题来解决。 - **问题描述**：假设有一组人员需要分配到一组任务中，每个人员适合执行某些特定的任务，问题是找到一种分配方案，使得每个任务都有人完成，且每个人员只分配到一个任务。 - **解决方法**：可以通过构建一个二分图来表示人员与任务之间的关系，然后寻找一个完美匹配来解决问题。 #### 5.6 最优分配问题 最优分配问题是在人员分派问题的基础上增加了成本的概念，目的是找到最小化总成本的分配方案。 - **问题描述**：除了人员与任务之间的匹配外，还需要考虑将人员分配到某个任务上的成本，目标是最小化总成本。 - **解决方法**：同样可以通过构建图模型来解决，但是可能需要更复杂的算法，例如匈牙利算法或Kuhn-Munkres算法等。 #### 5.7 稳定匹配 稳定匹配问题涉及到两组实体（例如学生和大学）之间的匹配，在这种情况下需要确保没有一对未匹配的实体希望互相匹配。 - **问题描述**：假设有一组实体A和一组实体B，每个实体都有一个偏好的排序列表，问题是找到一个匹配方案，使得没有一对未匹配的实体愿意互相匹配。 - **解决方法**：可以通过Gale-Shapley算法来求解，该算法可以确保找到一个稳定的匹配。 以上是对第五章内容的详细介绍，涉及了匹配的基本概念、不同类型的匹配以及它们的应用场景。这些理论不仅在图论研究中有重要意义，还在许多实际问题中发挥着关键作用。