南京大学：《图论与算法》课程教案讲稿（Graph Theory and Algorithms, GTA）第08周 匹配

可有京大赞 NANJING UNIVERSITY 第5章匹配 程龚 2023/4/3

第5章 匹配 程龚 2023/4/3 1

顶点的配对 2023/4/3

2023/4/3 2 顶点的配对

顶点的配对 er VI e2 V2 e3 v3 eA es VA e6 e7 V7 v6 2023/4/3 3

2023/4/3 3 顶点的配对 v 1 v 5 v 7 v 3 v 2 v 6 v 4 e 1 e 2 e 3 e 4 e 5 e 6 e 7

顶点的配对 e V1 VA es e 2023/4/3

2023/4/3 4 顶点的配对

顶点的配对 BHE e3 e12 V11 e2 es e e13 V10 e8 V12 eji e7 内6 e10 v& eg %E4%B9%92KE49%899%93%E7%90%83%E8%BF%90%E5%8A%A8E5%91%98) 2023/4/3

2023/4/3 5 顶点的配对 v1 v2 e1 v3 v7 v6 v5 v4 v11 v12 v9 v8 v10 e2 e3 e5 e4 e6 e7 e8 e9 e10 e11 e12 e13 https://zh.wikipedia.org/wiki/%E9%A9%AC%E9%BE%99_(%E4%B9%92%E4%B9%93%E7%90%83%E8%BF%90%E5%8A%A8%E5%91%98) https://zh.wikipedia.org/wiki/%E8%AE%B8%E6%98%95

顶点的配对 BHE e12. e V2 es e e13 V10 V12 e11 6 e6 e10 httpss/zh.wikipedia.org/wik/%E9%A9%AC%E9%aE%99_(%E4%B9%92%E4%89%93%E7%90%83%E8%BF%90%E5%8A%A8%E5%91%98) https://zh.wikipedia.org/wiki/%E8%AE%88%E6%98%95 2023/4/3

2023/4/3 6 顶点的配对 https://zh.wikipedia.org/wiki/%E9%A9%AC%E9%BE%99_(%E4%B9%92%E4%B9%93%E7%90%83%E8%BF%90%E5%8A%A8%E5%91%98) https://zh.wikipedia.org/wiki/%E8%AE%B8%E6%98%95

本次课的主要内容 5.1匹配和最大匹配 5.2完美匹配 2023/4/3

5.1 匹配和最大匹配 5.2 完美匹配 2023/4/3 7 本次课的主要内容

本次课的主要内容 5.1匹配和最大匹配 5.2完美匹配 2023/4/3

5.1 匹配和最大匹配 5.2 完美匹配 2023/4/3 8 本次课的主要内容

匹配和最大匹配 ■匹配：两两不相邻的边的子集 e3 e12 V11 e2 e V2 e13 V10 V12 e11 e V7 o e6 e10 'e9 2023/4/3

n 匹配：两两不相邻的边的子集 2023/4/3 9 匹配和最大匹配 v1 v2 e1 v3 v7 v6 v5 v4 v11 v12 v9 v8 v10 e2 e3 e5 e4 e6 e7 e8 e9 e10 e11 e12 e13

匹配和最大匹配 ■匹配：两两不相邻的边的子集 ■饱和（已匹配）：匹配中边的端点被匹配饱和 e3 e12 V11 e e2 e13 V10 V12 e e11 6 e10 2023/4/3

n 匹配：两两不相邻的边的子集 n 饱和（已匹配）：匹配中边的端点被匹配饱和 2023/4/3 10 匹配和最大匹配 v1 v2 e1 v3 v7 v6 v5 v4 v11 v12 v9 v8 v10 e2 e3 e5 e4 e6 e7 e8 e9 e10 e11 e12 e13