离散数学期末复习试题及答案
i)
ii)
iii) n个顶点的图是自补图的必要条件是
nn(n -1)/2 = 2m n(n-1)=4m
当n为偶数 ，( n-1) 必为奇数
当n为奇数 ，( n-1) 必为偶数 4 (n-1) n-1=4k n=4k+1
4．若无向图G不连通，则它的补图是连通图。?
若G不连通,分为m个分图 G1,G2…Gm ,
若 V__
i Gi,Vj Gj (i j), ( Vi,Vj) G, 若Vi,Vj属于同一分图 Gi , Vk Gk Gi,
(V__
__
__
i,Vk) G, (Vk,Vj) G ,(Vi,Vk ,Vj)是G中的路。
5．（ｎ，ｍ）一图，若ｍ＞1
2（ｎ－1）（ｎ－2），试证明此图连通。?
证一：无孤立点，否则 V0 , d(V0)=0, 则 G-{V0}
有( n-1)个点,m>(n-1)(n-2)/2条边，而(n-1)个顶点完全图边
数等于(n-1)(n-2)/ 2 矛盾。
归纳法: n = 2 m = 1×0×1/2 = 0 m≥1连通。 假设(n-1) 个顶点时，若m >(n-2)(n-3)/2，图连通，则 n个点时， 若m>(n-1)(n-2)/2 ,若所有V , d(V) = n - 1, 则是完全图， 当然连通。否则 V0, 1≤d(V0)≤n-2 ,G-{V0}有(n-1)个点， 边数 (1/2)(n-1)(n-2)-(n-2)=(1/2)(n-2)(n-3)，由假设，G-{V0} 连通，添上V0及关联边,得 G 连通。
证二：若不连通，至少分为二个分图G1,G2 ,顶点分别有n1,n2个