离散数学（全套课件1530P）.ppt

最大匹配 ? 定理13.7: 设M1,M2是G中2个不同匹配,则 G[M1⊕M2]的每个连通分支是M1,M2中的边 组成的交错圈或交错路径 ? 证明: 设G1是G[M1⊕M2]的1个连通分支, ?v∈V(G1), 0dG1(v)=dG[M1⊕M2](v)≤2, 即 dG1(v)=1或2. 所以G1是交错圈或交错路径. # 最大匹配 ? 定理13.8: 设M是G中匹配, Γ是M的可增广 路径, 则M’=M⊕E(Γ)也是G中匹配, 且 |M’|=|M|+1 ? 证明: 显然M是匹配. |M’|=|M⊕E(Γ)|=|M-E(Γ)|+|E(Γ)-M|=|M|+1. # 最大匹配 ? 定理13.9(Berge,1957): M是G中最大匹配?G中无M可增广路径 ? 证明: (?)(反证)定理13.8. (?)设M1是G的最大匹配, H=G[M1⊕M]. 若 H≠?, H的连通分支是交错圈或交错路径. M 和M1都无可增广路径, 所以|M|=|M1|. # 二部图的匹配 ? 完备匹配 – 充要条件: Hall条件(相异性条件) – 充分条件: t条件 ? k正则二部图: 有k个边不重完美匹配 ? 无孤立点二部图: α0=β1 完备匹配(complete matching) ? G=V1,V2,E是二部图, |V1|≤|V2| ? 完备匹配: |M|=|V1| ? Hall条件: ?S?V1, |S|≤|N(S)|, 其中N(S) = { u | ?v∈S,(v,u)∈E } = Uv∈SΓ(v) ? t(≥1)条件: ?v∈V1, d(v)≥t; ?v∈V2, d(v)≤t ? t条件 ? ?完备匹配 ? Hall条件 Hall定理 ? 定理13.11(Hall,1935): 二部图G有完备匹配 ? G满足Hall条件(|S|≤|N(S)|) ? 证明:(?)显然. (?)(反证)设G=V1,V2,E是 满足条件的极小子图, 则存在a1,a2∈V1, x∈V2, (a1,x),(a2,x)∈E. 删除(ai,x)将破坏条件, 则存在A1,A2?V1, ai∈Ai, 在Ai中只有ai与x相 邻, |Γ(Ai)|=|Ai|. Hall定理 ? 证明:(?)(续) |Γ(A1)∩Γ(A2)| ≥ |Γ(A1-{a1})∩Γ(A2-{a2})|+1 ≥ |Γ(A1∩A2)|+1≥|A1∩A2|+1. |Γ(A1∪A2)|=|Γ(A1)∪Γ(A2)| = |Γ(A1)|+|Γ(A2)|-|Γ(A1)∩Γ(A2)| ≤ |A1|+|A2|-(|A1∩A2|+1)=|A1∪A2|-1, 矛盾! # t条件 ? 定理13.12: 设G=V1,V2,E是二部图,若V1 中每个顶点至少关联t(t≥1)条边,而V2中每个 顶点至多关联t条边,则G中存在完备匹配 ? 证明: V1中任意k个顶点至少关联kt条边, 这 kt条边至少关联V2中k个顶点,即相异性条件 成立. # 例 ? (1) 满足t(=3)条件 ? (2) 满足Hall条件 ? (3) 无完备匹配 (1) (2) (3) k正则二部图 ? 定理13.13: 设G=V1,V2,E是k正则二部图, 则G中存在k个边不重的完美匹配 ? 证明: G满足t=k的t条件, 所以有完备匹配M1, 又|V1|=|V2|, 所以完备匹配就是完美匹配. G- M1是k-1正则二部图,又有完美匹配M2, G- M1-M2是k-2正则二部图, …, 一共可得k个完 美匹配, 显然这些匹配是边不重的. # 无孤立点二部图 ? 定理13.14:设G=V1,V2,E是无孤立点二部 图,则α0=β1 ? 证明:设M是最大匹配. X是V1非饱和点集. S={u∈V1|?v∈X,从v到u有交错路径}. T={u∈V2|?v∈X,有v到u交错路径}?V2-X. 令N=(V1-S)∪T是点覆盖,|N|=|M|, 由定理 13.6知N是最小覆盖. # 完美匹配 ? 完美匹配: 没有非饱和点的匹配 e2 e1 e3 e4 e6 e7 e5 e8 e2 e1 e3 e4 e6 e7 e5 e8 e2 e1 e3 e4 e6 e7 e5 e8 完美匹配 ? 定理13.10(Tutte,1947): G有完美匹配 ? ?V’?V(G), p奇(G-V’)≤|V’|. ? 说明: p奇是奇数阶连通分支数 ? 证明: (?)设M是G的完美匹配, G1是G-V’的 奇阶连通分支, 则?u1∈V(G1), ?v1∈V’, (u1,v1)∈M, 所以p奇(G-V’)≤|V’|. 完美匹配 ? 证明: (?) (对G阶数归纳) 取V’=?,得G是偶阶. 取V’={u},得G-{u}恰有1个奇阶连通分支