2024年3月25日发(作者：教育践行者高三数学试卷)

★ 形成性考核作业 ★

离散数学作业2

姓 名：

学 号：

得 分：

教师签名：

离散数学图论部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部

分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面

作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快

掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合

练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有

解答过程，完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保

存”和“交卷”按钮，以便教师评分。

一、单项选择题

00100

00011



1．设图G的邻接矩阵为

10000

，则G的边数为( )．



01001



01010

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

答 D

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

A．deg(V)=2E B．deg(V)=E

C．

deg(v)2E

D．

deg(v)E

vVvV

答 C（握手定理）

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

是( )．

A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的

答 A（有一条经过每个结点的回路）

1

★ 形成性考核作业 ★

4．给定无向图G如右图所示，下面给出的结

点集子集中，不是点割集的为（ ）．

A．{b, d} B．{d}

C．{a, c} D．{b, e}

答 B

5．图G如右图所示，以下说法正确的是( )．

A．{(a, c)}是割边

B．{(a, c)}是边割集

C．{(b, c)}是边割集

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

答 D

6．无向图G存在欧拉通路，当且仅当( )．

A．G中所有结点的度数全为偶数

B．G中至多有两个奇数度结点

C．G连通且所有结点的度数全为偶数

D．G连通且至多有两个奇数度结点

答 D

7．若G是一个欧拉图，则G一定是( )．

b

a

b

c

4题图

a

d

e

c

5题图

d

e

A．平面图 B．汉密尔顿图 C．连通图 D．对偶图

答 C

8．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2

答 A（欧拉公式：ver  2）

9．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能

确定G的一棵生成树．

A．

mn1

B．

mn

C．

mn1

D．

nm1

答 A（n个结点的连通图的生成树有

n1

条边，必须删去

m(n1)

条边）

10．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T

的树叶数为（ ）．

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

解 这棵无向树T有7条边，所有结点的度数之和为14，而4度、3度、2

度的分支点各一个共3个结点占用了9度，所以剩下的5个结点占用5度，故有

5片树叶．

答 B

2


更多推荐

结点,作业,书面,条边