第十四章 习题.ppt

第十四章第十四章****题****题 10 10、方法一、反证法、方法一、反证法结论的否则: 结论的否则: G G中至多有中至多有 5 5个个5 5度顶点度顶点且至多有且至多有 4 4 个个6 6度顶点。度顶点。 5 5个个5 5度顶点度顶点与握手定理的推论矛与握手定理的推论矛盾。因此至多有盾。因此至多有 4 4个个5 5度顶点,这样, 度顶点,这样, G G中至多有中至多有 8 8个顶点,与个顶点,与 G G是是9 9阶图矛盾。阶图矛盾。方法二、枚举法方法二、枚举法 1)2 1)2 个个5 5度顶点, 度顶点, 7 7个个6 6度顶点; 度顶点; 2)4 2)4 个个5 5度顶点, 度顶点, 5 5个个6 6度顶点; 度顶点; 3)6 3)6 个个5 5度顶点, 度顶点, 3 3个个6 6度顶点; 度顶点; 4)8 4)8 个个5 5度顶点, 度顶点, 1 1个个6 6度顶点; 度顶点; 定义 设G=<V,E>为n阶无向简单图,以 V为顶点集,以所有使 G成为完全图 K n的添加边组成的集合为边集的图,称为 G的补图,记作 G。若图 G≌G,则称为 G是自补图。(1) (1) 为自补图为自补图(2) (2) 和和(3) (3) 互为补图互为补图 19 19、设、设 G G是是n n阶自补图,证明阶自补图,证明 n=4k, n=4k, 或或n=4k+1, n=4k+1, 其其中中k k为正整数; 为正整数; ?G∪ G= Kn ;?由G G≌≌G G, ,因此它们的边数相等,设都为因此它们的边数相等,设都为 m m, , 所以所以 m+m m+m =2m=n(n-1)/2 =2m=n(n-1)/2 ,即,即 4m=n(n-1) 4m=n(n-1) ??n n与与n-1 n-1 互素,所以一定有互素,所以一定有 n=4k n=4k 或或n-1=4k n-1=4k ; ; 20 20、求补图的边数、求补图的边数 m m’’m m’’=n(n-1)/2-m; =n(n-1)/2-m; 29 29、设、设 G G是是n n阶阶n+1 n+1 条边的无向图,证明条边的无向图,证明 G G中中存在顶点存在顶点 v v, ,d(v) d(v) ≥≥3 3 。。证明:反证法证明:反证法否则,任意否则,任意 v v∈∈V(G V(G ), ),均有均有 d(v) d(v) ≤≤2 2,则由握手,则由握手定理可知: 定理可知: 2m=2n+2 < 2n 2m=2n+2 < 2n ,其中,其中 m m为边数为边数. . 矛盾! 矛盾! 30 30、设、设 e=( e=( u,v u,v ) )为无向图为无向图 G G中的一条边,证明: 中的一条边,证明: e e 为为G G中桥当且仅当中桥当且仅当 e e不在不在 G G的任何圈中。的任何圈中。必要性必要性: :若若e e为桥为桥, ,则则e e不在不在 G G中的任何圈中。中的任何圈中。反证法:否则,存在圈反证法:否则,存在圈 C= C= uev uev v v 1 1v v 2 2…………. .v v s su u, ,在在 G G中含有边中含有边 e(e e(e 为桥为桥) ),则,则 G-e G-e 中,顶点中,顶点 v v到到u u有通有通路路 v v v v 1 1v v 2 2…………. .v v s