《离散数学》课件 第7章 图.ppt

**********************************************************************************定理7.11证明给G1加新边使它成为Kn1,给G2加新边使它成为Kn2,令G*=Kn1?E1?Kn2.*G1G2E1Kn1Kn2定理7.11证明?(G)?(G)??(G*)?n1-1+??(G)/n1???(G)n1-1+?(G)/n1?(n1-1)(n1-?(G))0??(G)n1??(G)?n1-1.?(G)=n1-1??(G)=n1-1+??(G)/n1???(G)?(G)??(G*)??(G)(矛盾!)?(G)n1-1??(G)?n1-2??(G)+2?n1.#*推论(1)?(G)??(G*)?n1-1??n/2?-1(2)G*中有不相邻顶点u,v,使得dG*(u)+dG*(v)?n-2(3)d(G)?d(G*)?3证明:(2)u?G1,v?G2,在G中不相邻,则在G*中仍然不相邻.(3)d(G)=maxd(u,v)?(G)?n1-2#*定理7.12G是6阶以上连通简单无向图.(1)?(G)??n/2???(G)=?(G)(2)任意一对不相邻顶点u,v都有d(u)+d(v)?n-1,??(G)=?(G).(3)d(G)?2??(G)=?(G).#*定理7.13定理7.13G是n阶简单连通无向非完全图,则2?(G)-n+2??(G).证:设V1是G的点割集,|V1|=?(G),设G-V1的连通分支是G1,G2,…,Gs(s?2),设|V(G1)|=n1,|V(G2)|+…+|V(Gs)|=n2,则n1+n2+?(G)=n.?(G)?n1-1+?(G)=n1+?(G)-1,并且?(G)?n2+?(G)-1?2?(G)?n1+?(G)+n2+?(G)-2=n+?(G)-2??(G)?2?(G)-n+2.#*G1G2Gs小结点割集,边割集,点(边)连通度?(?);?,?,?之间关系,Whitney定理等k-(边)连通图,Menger定理等2-(边)连通,割点,桥,块的充要条件***************************引理2证明证:(反证)否则?(G)=|E’|=|V(G1)|?|V(G2)|?|V(G1)|+|V(G2)|-1=n-1,与G非完全图相矛盾!#a?1?b?1?(a-1)(b-1)?0?ab-a-b+1?0?ab?a+b-1.*k-(边)连通图k-连通图:?(G)?kK-边连通图：?(G)?k例：彼得森图:?=3,?=3它是1-连通图,2-连通图,3-连通图,但不是4-连通图它是1-边连通图,2-边连通图,3-边连通图,但不是4-边连通图*定理定理:对3-正则图G,?(G)=?(G).证明:(作业).#彼得森图:?=3,?=3*Whitney定理定理7.10(Whitney不等式):任意G,?(G)??(G)??(G).推论:k-连通图一定是k-边连通图.#*Whitney定理证明目标:?????.证明:不妨设G是3阶以上连通非完全简单图.(否则可直接验证结论成立).*Whitney定理证明第一部分:???证明:设dG(v)=?.IG(v)={(u,v)|(u,v)?E(G)}则必有扇形边割集S?IG(v),所以,??|S|?|IG(v)|=?.*Whitney定理证明第二部分:???证明: