匹配和最大匹配 ■匹配：两两不相邻的边的子集 ■饱和（已匹配）：匹配中边的端点被匹配饱和 ■极大匹配：匹配，且不是任何匹配的真子集 e12 e3, 11 e2 e V3 e13 V10 V12 e e11 1 e10 2023/4/3
n 匹配：两两不相邻的边的子集 n 饱和（已匹配）：匹配中边的端点被匹配饱和 n 极大匹配：匹配，且不是任何匹配的真子集 2023/4/3 11 匹配和最大匹配 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 e e2 V2 e13 V10 e8 V12 e7 e11 V6 e10 2023/4/3 12
n 匹配：两两不相邻的边的子集 n 饱和（已匹配）：匹配中边的端点被匹配饱和 n 极大匹配：匹配，且不是任何匹配的真子集 n 最大匹配：边的数量最多的匹配 2023/4/3 12 匹配和最大匹配 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
匹配和最大匹配 ■每个图都有匹配吗？ 2023/4/3 13
n 每个图都有匹配吗？ 2023/4/3 13 匹配和最大匹配
匹配和最大匹配 ■每个图都有匹配吗？ ■阶为n的图的最大匹配至多有多少条边？ 2023/4/3 14
n 每个图都有匹配吗？ n 阶为n的图的最大匹配至多有多少条边？ 2023/4/3 14 匹配和最大匹配
匹配和最大匹配 ■每个图都有匹配吗？ ■阶为n的图的最大匹配至多有多少条边？ ■完全图K的最大匹配有多少条边？ 2023/4/3 15
n 每个图都有匹配吗？ n 阶为n的图的最大匹配至多有多少条边？ n 完全图Kn的最大匹配有多少条边？ 2023/4/3 15 匹配和最大匹配