《离散数学》课件 第13章 集.ppt

托特定理推论证明证:对任意V1,设G-V1的奇阶连通分支是Gi,i=1,2,…,r,|V(Gi)|=ni(奇数),|[V(Gi),V1]|=mi.?v?V(Gi)dG(v)=3ni=2|E(Gi)|+mi?mi是奇数.无桥?mi?3.p奇(G-V1)=r?(?ri=1mi)/3?(?v?V1dG(v))/3=|V1|,再用托特定理.#*无桥条件不能去掉反例:p奇(G-{v})=3|{v}|=1,无完美匹配*v小结边覆盖，极小（最小）边覆盖(易解)匹配，极大（最大）匹配，完美匹配(易解)饱和点，非饱和点，交错路径?0,?0,?0,?0,?1,?1之间关系匹配存在的充要条件Berge定理:有最大匹配?无可增广路径Tutte定理:有完美匹配??V’,p奇(G-V’)?|V’|*单元13.3二部图中的匹配第二编图论第十一章平面图13.3二部图中的匹配*内容提要完备匹配充要条件:Hall-条件(相异性条件)充分条件:t-条件k正则二部图无孤立点二部图*完备匹配二部图G=V1,V2,E,|V1|?|V2|,M是匹配?|M|=|V1|*霍尔条件又称“相异性条件”:?S?V1,|S|?|N(S)|N(S)={u|?v?S,(v,u)?E}=?v?S?(v)*SN(S)霍尔定理(婚姻定理)定理13.11(Hall,1935):二部图G有完备匹配?G满足霍尔条件(?S,|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|.*霍尔定理证明|?(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-条件二部图G=V1,V2,E,t?1V1中每个顶点至少关联t条边? V2中每个顶点至多关联t条边*t=3定理13.12设G=V1,V2,E是二部图,则G满足t-条件?G中存在完备匹配*定理13.12证明证:V1中任意k个顶点至少关联kt条边,这kt条边至少关联V2中k个顶点,即相异性条件成立.#*例(1)满足t-条件(t=3)(也满足Hall-条件)(2)满足Hall-条件(但不满足t-条件)(3)不满足Hall-条件(无完备匹配)*(1)(2)(3)定理13.13(k-正则二部图)k-正则二部图G=V1,V2,E中,存在k个边不重的完美匹配*定理13.13证明证: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*定理13.14证明证:设M是最大匹配,X是V1非饱和点集,S={u?V1|?v?X,从v到u有交错路径},T={u?V2|?v?X,从v到u有交错路径}.则N=(V1-S)?T是点覆盖,|N|=|M|,由定理13.6知N是最小覆盖.#*小结完备