匹配和最大匹配 ■对于图G=<V,E>和匹配M二E ●M佼错路：交替经过M和E\M仲的边 ●M增广路：M佼错路，非平凡路.且起点和终点未被M饱和 e12 V11 e2 v3 e13 V10 e8 V12 e11 V7 e10 Vg 2023/4/3 21
n 对于图G = <V, E>和匹配M ⊆ E l M交错路：交替经过M和E \ M中的边 l M增广路：M交错路，非平凡路，且起点和终点未被M饱和 2023/4/3 21 匹配和最大匹配 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
匹配和最大匹配 ■对于图G=<V,E和匹配M二E ●M交错路：交替经过M和E\M仲的边 ●M增广路：M佼错路，非平凡路，且起点和终点未被M饱和 ■每个匹配都有交错路和增广路吗？若有，则唯一吗？ e12 e3 V11 e2 V2 e13 V10 V12 e11 V7 6 e6 e10 Vg V8 2023/4/3 22
n 对于图G = <V, E>和匹配M ⊆ E l M交错路：交替经过M和E \ M中的边 l M增广路：M交错路，非平凡路，且起点和终点未被M饱和 n 每个匹配都有交错路和增广路吗？若有，则唯一吗？ 2023/4/3 22 匹配和最大匹配 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
匹配和最大匹配 ■Claude Jacques Berge,1926年出生于法国 https://mathshistory.st-andrews.ac.uk/Biographies/Berge/Berge.ipeg 2023/4/3 23
n Claude Jacques Berge，1926年出生于法国 2023/4/3 23 匹配和最大匹配 https://mathshistory.st-andrews.ac.uk/Biographies/Berge/Berge.jpeg
匹配和最大匹配 ■贝尔热定理：对于图G=<V,E>和匹配M二E,M是最大匹配当 且仅当G不含M增广路。 2023/4/3 24
n 贝尔热定理：对于图G = <V, E>和匹配M ⊆ E，M是最大匹配当 且仅当G不含M增广路。 2023/4/3 24 匹配和最大匹配
匹配和最大匹配 ■贝尔热定理：对于图G=<V,E>和匹配M二E,M是最大匹配当 且仅当G不含M增广路。 ■必要性：你能自己证明吗？ e12 V11 e2 e e13 V10 e8 5 V12 e1 V7 V6 'e6 g e10 'e9 2023/4/3
n 贝尔热定理：对于图G = <V, E>和匹配M ⊆ E，M是最大匹配当 且仅当G不含M增广路。 n 必要性：你能自己证明吗？ 2023/4/3 25 匹配和最大匹配 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