国防科大离散数学答案图论

第二章 二元关系

第一章 集合

习题1.1

1.

a) {0, 1, 2, 3, 4} b) {11, 13, 17, 19} c) {12, 24, 36, 48, 64} 2.

a) {x | x ? N 且x ? 100}

b) Ev = {x | x ? N 且2整除x } Od = {x | x ? N 且2不能整除x } c) {y | 存在x ? I 使得 y = 10 ? x } 或 {x | x/10 ? I }

3. 极小化步骤省略 a) ①

② 或 ① ② 或 ① ②

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ? A ； 若?, ? ? A，则??? ? A 。

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ? A ；

若? ? A 且 a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a?? ? A 。 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ? A ；

若? ? A 且 a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则??a ? A 。

b)

① {0, 1, 2, 3, 4, 5, 6,

第六章 图论基础

图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。

6.1 图的基本概念

我们已知集合的笛卡尔积的概念，为了定义无向图，还需要给出集合的无序积的概念。 任意两个元素a,b构成的无序对（Unordered pair）记作(a,b)，这里总有(a,b)?(b,a)。 设A,B为两个集合，无序对的集合{(a,b)a?A?b?B}称为集合A与B的无序积（Unordered Product），记作A&B。无序积与有序积的不同在于A&B?B&A。

例如，设A??a,b?，B??0,1,2?，则A&B?{(a,0),(a,1),(a,2),(b,0),(b,1),(b,2)} ?B&A,A&A?{(a,a),(a,b),(b,b)}。 为了引出图的定义，我们先介绍如下的例子。

B start s=0,i =1 i=1 S i=11? Y N s

第4章 图论

综合练习

一、 单项选择题

1．设L是n阶无向图G上的一条通路，则下面命题为假的是( )． (A) L可以不是简单路径，而是基本路径 (B) L可以既是简单路径,又是基本路径 (C) L可以既不是简单路径，又不是基本路径 (D) L可以是简单路径，而不是基本路径 答案：A

2．下列定义正确的是( )．

(A) 含平行边或环的图称为多重图 (B) 不含平行边或环的图称为简单图 (C) 含平行边和环的图称为多重图 (D) 不含平行边和环的图称为简单图 答案：D

3．以下结论正确是 ( )．

(A) 仅有一个孤立结点构成的图是零图 (B) 无向完全图Kn每个结点的度数是n (C) 有n(n>1)个孤立结点构成的图是平凡图 (D) 图中的基本回路都是简单回路 答案：D

4．下列数组中，不能构成无向图的度数列的数组是( )． (A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3) 答案：B

5．下列数组能构成简单图的是( )． (A) (0,1,2,3)

离散数学课程作业（图论）

一、 填空题 1. 2. 3. 4.

任意两点之间都有边相连的无向简单图称为 ；只有点，没有边的图称为 ；只有一个点的图称为 。 有n个顶点的连通无向图中至少有 条边。

无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点的度数均小于3，问G的阶数n至少为 。（答案：11） 写出如下无向图的关联矩阵：

5. 对任何连通平面图恒有：顶点数－边数＋面数＝ 。 6. 一个连通的无向图G是欧拉图当且仅当G中有 个奇度点。 7. 任意一棵非平凡的无向树都恰有 片叶子。 8. 判断如下哪些说法是正确的？

（1） 无向简单图中，无向完全图是边数最多的简单图。 （2） 哈密顿图一定是连通图。 （3） 欧拉图中只有2个奇度点。 （4） 在简单图中，连通但删去一条边后就不连通的图一定是树。

8. 设Ｇ是一个有n个结点的有向完全简单图，则Ｇ的边数为 。 9. 设T为一棵树，边数为m ，顶

离散数学图论部分综合练习

本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是图论部分的综合练习。

一、单项选择题

1．设图G的邻接矩阵为

??01100?011?

?10??10000??

?01001????01010??则G的边数为( )．

A．6 B．5 C．4

2．已知图G的邻接矩阵为

，

则G有（ ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

3．设图G＝，则下列结论成立的是 ( )．

A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．V?deg(v)?E

v?v?V4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割

★ 形成性考核作业 ★

离散数学作业5

姓 名： 学 号： 得 分： 教师签名： 离散数学图论部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题

1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 15 ．

2．设给定图G(如右由图所示)，则图G的点割集是 {f} ．

3．设G是一个图，结点集合为V，边集合为E，则 G的结点

离散数学图论部分综合练习

本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是图论部分的综合练习。

一、单项选择题

1．设图G的邻接矩阵为

??01100?011?

?10??10000??

?01001????01010??则G的边数为( )．

A．6 B．5 C．4

2．已知图G的邻接矩阵为

，

则G有（ ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

3．设图G＝，则下列结论成立的是 ( )．

A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．V?deg(v)?E

v?v?V4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割

离散数学图论部分综合练习

1．设图G＝，则下列结论成立的是 ( )． A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．?deg(v)?E

v?Vv?Va ? d? ? c

图一

b ? ? f

?e

2．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集 D．{(a, d) ,(a, c)}是边割集

3．如图二所示，以下说法正确的是 ( )． A．e是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集

4．如图三所示，以下说法正确的是 ( ) ．

图二 A．{(a, e)}是割边 B．{(a, e)} 是边割集

C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集

图三

5．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是 ( )．

离散数学图论部分综合练习

一、单项选择题

1．设图G的邻接矩阵为

?01?10??10

??01??01100?011??000?

?001?010??

则G的边数为( )．

A．6 B．5 C．4 D．3

2．已知图G的邻接矩阵为

， 则G有（ ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

3．设图G＝，则下列结论成立的是 ( )．

A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．?deg(v)?E

v?Vv?Va ? d? ? c

图一

b ? ? f

?e

4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集 D．{(a, d) ,(a, c)}是边割集

5．如图二所示，以下说法正确的是 ( )． A．e是割点

离散数学图论部分综合练习

一、单项选择题

1．设图G的邻接矩阵为

?01?10??10

??01??01100?011??000?

?001?010??

则G的边数为( )．

A．6 B．5 C．4 D．3

2．已知图G的邻接矩阵为

， 则G有（ ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

3．设图G＝，则下列结论成立的是 ( )．

A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．?deg(v)?E

v?Vv?Va ? d? ? c

图一

b ? ? f

?e

4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集 D．{(a, d) ,(a, c)}是边割集

5．如图二所示，以下说法正确的是 ( )． A．e是割点