离散数学期末复习试题及答案(五)(2)

离散数学期末复习试题及答案

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个

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库离散数学期末复习试题及答案(五)(2)在线全文阅读。