离散数学第七章图论课后答案

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

离散数学大连理工大学软件学院陈志奎教授办公室：综合楼411,Tel: 87571525实验室：教学楼A318/A323,Tel:87571620/24 Mobile: 13478461921 Email: zkchen@http://www.77cn.com.cn zkchen00@http://www.77cn.com.cn

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

第七章图论

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极大,举类迩而见义远.....让人受益匪浅。

7.4图的矩阵表示一、邻接矩阵 V, E,定义：设 G=ψ 是一个简单有向图，其中的=结点集合V{v1, v2, vn},并且假定各结点已经有了从结点v1到vn的次序。试定义一个n×n的矩阵A,使得其中的元素

ai j={01

当 vi, v j ∈E当 vi, v j E

(1)

则称这样的矩阵A是图G的邻接矩阵。

3/41

大连理工大学离散数学教程。图论,其文约,其辞微,其称文小而其指极

离散数学

第七章 计数

离散数学

7.1 基本计数原理1.加法原理 2.乘法原理

离散数学

加法原理加法原理又称为和计数原理，也称和规则，存在三种表 述形式，其本质是说，整体等于其部分之和。 ① 若集合X是不相交非空子集S1,S2,…,Sm的并，则 |X|= m

| Si 1

i

|

② 若E1,E2,…,Em是彼此互斥事件，并且E1发生有e1 种方式，E2发生有e2种方式，…,Em发生有em种方式， 则E1或E2或…或Em发生有e1+e2+…+em种方式。 应该指出的是，事件E1和E2互斥是说，E1和E2发生但两 者不能同时发生。

离散数学

③ 如果选择事物O1有n1种方法，选择事物O2 有n2种方法，…,选择事物Om有nm种方法， 并且选择诸事物方法不重叠，则选取O1或O2 或…或Om有n1+n2+…+nm种方法。

离散数学

加法原理

例7.1.1 一个学生想选修一门数学课或一门生 物学课，但不能同时选修两门课。如果该生对 5门数学课和3门生物学课具有选课条件，试问 该生有多少方式来选修课程？

离散数学

乘法原理

乘法原理又称有序计数原理，也称积规则，类 似加法原理，也有三种表述形式。 ① 若S1,S2,…,Sm是非空集合，则笛卡尔 m 积S1 S2 … Sm的元

离散数学

第七章 计数

离散数学

7.1 基本计数原理1.加法原理 2.乘法原理

离散数学

加法原理加法原理又称为和计数原理，也称和规则，存在三种表 述形式，其本质是说，整体等于其部分之和。 ① 若集合X是不相交非空子集S1,S2,…,Sm的并，则 |X|= m

| Si 1

i

|

② 若E1,E2,…,Em是彼此互斥事件，并且E1发生有e1 种方式，E2发生有e2种方式，…,Em发生有em种方式， 则E1或E2或…或Em发生有e1+e2+…+em种方式。 应该指出的是，事件E1和E2互斥是说，E1和E2发生但两 者不能同时发生。

离散数学

③ 如果选择事物O1有n1种方法，选择事物O2 有n2种方法，…,选择事物Om有nm种方法， 并且选择诸事物方法不重叠，则选取O1或O2 或…或Om有n1+n2+…+nm种方法。

离散数学

加法原理

例7.1.1 一个学生想选修一门数学课或一门生 物学课，但不能同时选修两门课。如果该生对 5门数学课和3门生物学课具有选课条件，试问 该生有多少方式来选修课程？

离散数学

乘法原理

乘法原理又称有序计数原理，也称积规则，类 似加法原理，也有三种表述形式。 ① 若S1,S2,…,Sm是非空集合，则笛卡尔 m 积S1 S2 … Sm的元

离散数学第七章检测题

一、 单项选择题（每小题2分，共20分）

1．下图中是哈密尔顿图的是( 2

)

2．下面给出的四个图中，哪个不是汉密尔顿图（ （4） ）．

3．下列是欧拉图的是( 2

)

4. 下列各图不是欧拉图的是（ 4 ）

5．设A(G

)是有向图G ,E的邻接矩阵，其第i列中“1”的数目为（ ）。 (C) (1)．结点vi的度数； (2)．结点vi的出度； (3)．结点vi的入度； (4)．结点vj的度数。 6．无向图G中有16条边，且每个结点的度数均为2，则结点数是( 2 )

(1)．8 (2)．16 (3)．4 (4)．32 7．设Ｇ＝ V,E 为无向图， 7,E 23，则Ｇ一定是（ （4） ）．

(1)．完全图； (2)．零图； (3)．简单图； (4)．多重图． 8．若具有n个结点的完全图是欧拉图，则n为( 2 ). (1)．偶数；(2)．奇数； (3)． 9； (4)． 10．

9．无向图G是欧拉图，当且仅当（ ）． (1)

(1)．G连通且所有结点的度数为偶数； (2)．G的所有结点的度数为偶

第六章 图论基础

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

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 ，顶

1 / 13

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图

多重集合: 元素可以重复出现的集合 无序积: A &B ={(x ,y ) | x ∈A ∧y ∈B } 定义 无向图G =, 其中 (1) 顶点集V ≠?，元素称为顶点

(2) 边集E 为V &V 的多重子集，其元素称为无向边，简称边.

例如, G =如图所示, 其中V ={v 1, v 2, …,v 5}, E ={(v 1,v 1), (v 1,v 2),

(v 2,v 3), (v 2,v 3), (v 2,v 5), (v 1,v 5), (v 4,v 5)} ,

定义 有向图D =, 其中

(1) V 同无向图的顶点集, 元素也称为顶点

(2) 边集E 为V ?V 的多重子集，其元素称为有向边，简称边.

用无向边代替D 的所有有向边所得到的无向图称作D 的基图，右图是有向图，试写出它的V 和E

注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G 表示无向图, D 表示有向图, 也常用G 泛指 无向图和有向图, 用e k 表示无向边或有向边.

V (G ), E (G ), V (D ), E (D ): G 和D 的顶点集, 边集. n 阶图:

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

本课程综合练习共分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的结点