1 / 5
2020 年秋《离散数学》图论测试
姓名: ____________________ 学号: ____________________ 成绩: ____________________
一. 不定项选择题: 本题共 4 小题, 每小题 4 分, 共 16 分. 每小题有多个选项符合题
意, 全部选对的得 4 分, 选对但不全的得 2 分, 有选错或不答的得 0 分.
1. 下列关于图的基本概念的说法中, 正确的有 ______.
A. 在有向图 中, 每个结点 的正度和负度相等,所有结点的正度之和等于所
有结点的负度之和.
B. 已知图 . 如果 是 的生成子图, 那么 .
C. 从图 中删除某个点 和与其相连接的边, 得到的图 是 图 的导
出子图.
D. 如果图 和 不同构, 那么它们不存在同构的导出子图.
2. 下列关于图的代数表示的说法中, 正确的有 ______.
A. 无向图的邻接矩阵是一个对称矩阵.
B. 有向图如图 1 所示,它的邻接矩阵表示为
.
C. 关联矩阵能够表示自环,但不能表示重边.
D. 已知有向图 , 它的关联矩阵第行非零元的数目恰是结点
的度,
第 行所有元素之和为结点
的正度与负度之差.
3. 下列关于道路与回路的说法中, 正确的有______.
A. 在图 中, 如果道路 是一条简单道路,那么在 中不存在重复出现的结点.
B. 图 的极大联通子图是不唯一的, 而且每个极大联通子图 都是 的导出子
图.
C. 图 2 中(a) (b) (c) 三张图的连通支的个数分别为 1, 2, 3.
D. 如果二分图中出现回路, 那么该回路一定由偶数条边组成.
4. 下列关于树和森林的说法中, 正确的有______.
A. 删除树的任意一条边可以将其分成两个不连通的分支,每个分支都是原来
评论0