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

来源：网络收集时间：2026-02-13

导读：离散数学期末复习试题及答案第五章图论 1．画出下面两图的补图 2．下面两图是否同构？为什么？ e d 4 b c 同构 1 a, 2 b , 3 c , 4 d , 5 e (2 ,1) (d,a) (5,2) (e,b) (4 ,1) (d,a) (3,2) (c,b) (1 ,3) (a,c) (3,4) (c,d) (1 ,5) (a,e) (5,4) (e,d)

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

第五章图论 1．画出下面两图的补图

2．下面两图是否同构？为什么？

4 b c

同构 1 a, 2 b , 3 c , 4 d , 5 e (2 ,1) (d,a) (5,2) (e,b) (4 ,1) (d,a) (3,2) (c,b) (1 ,3) (a,c) (3,4) (c,d) (1 ,5) (a,e) (5,4) (e,d)

3．一个图如果同构于它的补图，则该图称为自补图 ｉ）给出有4个顶点的自补图。 ｉｉ）给出有5个顶点的自补图。

ｉｉｉ）证明一个自补图或者有4k个顶点，或者有4k+1个顶点。

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

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个

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

n1+n2＝n,由ni≥1,ni≤n - 1 (i =1,2)

m ≤n1(n1-1)/2 + n2(n2-1)/2 ≤(n-1)(n1+n2-2)/2 = (n-1)(n-2)/2 与条件矛盾.

证三:若G不连通,__

G连通(由第四题结论), G是(n,m')图

m'≤(n(n-1)/2)-m≤(n(n-2))/2-((n-1)(n-2)/2) =(n-1) 由定理3,__G不连通,矛盾.

证四：若 G不连通，至少有 2 点 a ,b不连通, 其余(n-2)个点不会同时与 a ,b 有边连通,则 m ≤(n(n-1)/2)-1-(n-2)=(n-1)(n-2)/2 矛盾.

6．写出下图的邻接矩阵，可达性矩阵，并求它的强分图。 V1

2 V3

5 V4

01000 1011 0

0010 0 10000 01011 01011 6. A= 1

0000 P= 1011 p pT= 00001 1

00100

01011 01011 0

0 0

7．确定下图中ａ到ｚ的最短路径

b 10 f

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

e i

逆序： 10——7——6——3——4——5——1 顺序： 1——5——4——3——6——7——10

最短路为： a —— e —— d —— c —— f —— g —— z

8．求下图中ｕ到各顶点的最短路径长度

d g

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

u d g, u c f e v

9. a)一笔 b) 四笔

10．画一个图，使它

ｉ）有一条欧拉回路和一条哈密顿回路； ｉｉ）有欧拉回路但无哈密顿回路； ｉｉｉ）有哈密顿回路但无欧拉回路； ｉｖ）既没欧拉回路又无哈密顿回路。

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

11．若ｕ和ｖ是无向图Ｇ中仅有的两个奇数度顶点，证明ｕ和ｖ是连通的。可从u 出发，沿着任意条边进入其他顶点，如果已是顶点V，则已

连通。否则，进入某一点后，由于这种点都是偶数度的，能进去一定能出来，又进入其他顶点，如果在某一步已进入V，则已连通，不然只要进入偶次顶点一定又可以出来，由于图中次是有限的，总能到达V。

12．证明 G 是强连通的当且仅当存在一条完备回路。

G 强连通。不妨设顶点为 V1,V2,……,Vn,由强连通，V1 到 V2有路,V2到 V3有路,……,Vn-1到Vn有路，Vn到V1有路，把这些路连在一起，是一条完备的回路。

13．证明 G 是单连通的当且仅当存在一条完备道路。

充分性显然。G 单连通，任一个顶点 V 总能加入到任意有向路中去, 若 G 中某一有向路 C , C:(V1,V2,...,Vi,...,Vm),不含顶点 V，由单连通性, a C,或 a 到 V 可达,或 V 到 a 可达, 若 V 到 V1可达，则

C1=( V,..., V1,..., Vm), 否则 V1到 V 可达,若 V 到 V2可达,则 C2=( V1,..., V,...,V2,...,Vn), 否则 V2到 V 可达,..., 若 i,Vi到 V 可达,V 到Vi+1可达, 则

Ci+1=(V1,...,Vi,...,V,...,Vi+1,...,Vm),否则均是 V1, V2,……,Vm 到 V 可达, 则

Cm+1＝(V1,...,Vm,...,V), 必可把 V 加入到道路中去。

14．若图 G 中有一顶点V，d(V) = 1，则 G 一定不是哈密顿图。 H 图是存在H 回路的，d(V) = 1, V 不在任何回路上，因此不存在 H 回路。

15．巡回售货员从ａ出发，访问ｂ，ｃ，ｄ，最后回到ａ，求最短路线。

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

( a, b,d,c ,a) or (a,c,d,b,a) long = 47

16．ｎ阶无向完全图 Kn，（ｎ＞1）是否存在欧拉道路和欧拉回路？充要条件是什么？

K2存在欧拉道路，Kn (n为奇数且 n>1) 存在欧拉回路。

17．如果ｎ（ｎ≥ 4）个顶点的线性图的每对顶点的次之和≥ｎ，则G 存在哈密顿回路。

每对顶点次之和≥n＞n-1 , 有充分性定理 , 必有 H 路, 不妨设此路为( V1,V2,…,Vn)。若 V1与 Vn 相邻，则(V1,V2,…,Vn,V1)是 H 回路。否则,

V1与Vi1,Vi2,...,Vij相邻,则Vn必与Vi1 1,Vi2 1,...,Vij 1之一相邻。否

则, Vn 的次 ≤n-j-1, V1 的次加 Vn的次 ≤(n-j-1)+j = n-1，与每对顶点次之和≥n矛盾。不妨Vn与Vit 1相邻，V1与Vit 相邻，可得

H 回路 (Vit 1

,Vit 2,...,V2,V1,Vit,Vit 1,...,Vn,Vit 1)

V1 V2 V3 Vi

t 1

…… ……

…… 此处隐藏：1187字，全部文档内容请下载后查看。喜欢就下载吧 ……

离散数学期末复习试题及答案(五).doc 将本文的Word文档下载到电脑，方便复制、编辑、收藏和打印

下载这篇word文档

本文链接：https://www.jiaowen.net/wenku/107104.html（转载请注明文章来源）

上一篇：考研失利后转型找工作的若干建议
下一篇：北京发那科 PMC 补充讲义zhao