2024知到答案 图论及其应用（山东大学） 最新智慧树满分章节测试答案
第一章 单元测试
1、单选题：
一个图的边数m和所有点的度和r的关系是（ ）。
选项：
A:r=m
B:r=2m
C:r=m/3
D:r=m+1
答案: 【r=2m】
2、多选题：
下列说法正确的是（ ）。
选项：
A:点不重复的途径称为路
B:边不重复的途径称为迹
C:一条路上的点可以重复
D:一条迹上的边可以重复
答案: 【点不重复的途径称为路;
边不重复的途径称为迹】
3、判断题：
图的周长是其中最长圈的长度。（ ）
选项：
A:错
B:对
答案: 【对】
4、判断题：
图的一个连通分支是它的一个极大连通子图。（ ）
选项：
A:错
B:对
答案: 【对】
5、判断题：
一个图的点连通度小于等于它的边连通度。（ ）
选项：
A:错
B:对
答案: 【对】
6、判断题：
一个图的点连通度和边连通度不一定小于等于最小度。（ ）
选项：
A:对
B:错
答案: 【错】
7、判断题：
有向图是强连通的是指，对其中的任意有序点对x，y，都有从x到y的路。（ ）
选项：
A:对
B:错
答案: 【对】
8、多选题：
下列说法正确的是（ ）。
选项：
A:如果一棵树的最大度是k，那么至少有k个叶子顶点
B:一棵树的两个点之间仅有一条路
C:一棵树可能含圈
D:树是无圈的连通图
答案: 【如果一棵树的最大度是k，那么至少有k个叶子顶点;
一棵树的两个点之间仅有一条路;
树是无圈的连通图】
9、判断题：
一个二部图可能含奇圈。（ ）
选项：
A:错
B:对
答案: 【错】
10、判断题：
一个连通图如果没有奇度顶点，则它是欧拉图。（ ）
选项：
A:对
B:错
答案: 【对】
第二章 单元测试
1、判断题：
如果一个图的每个顶点的度都等于k，那么它是k-正则的。（ ）
选项：
A:错
B:对
答案: 【对】
2、判断题：
如果存在关于匹配M的增广路，那么M可能是最大匹配。（ ）
选项：
A:对
B:错
答案: 【错】
3、单选题：
下列说法错误的是（ ）
选项：
A:2-因子的每个分支都是圈
B:1-因子是图的完美匹配
C:二部图中最大匹配的边数等于其边的顶点覆盖的最小基数
D:设二部图G=(X,Y)有1-因子，但是可能存在X的一个子集S，使得|N(S)|<|S|
答案: 【设二部图G=(X,Y)有1-因子，但是可能存在X的一个子集S，使得|N(S)|<|S|】
4、判断题：
图的一个1-因子也称为完美匹配，包含了图的所有顶点。（ ）
选项：
A:错
B:对
答案: 【对】
5、判断题：
一个无桥的立方图，它的边连通度可能等于1。（ ）
选项：
A:对
B:错
答案: 【错】
6、多选题：
下列说法错误的是（ ）
选项：
A:一个立方图，它的边连通度不可能等于1
B:一个立方图一定有1-因子
C:一个立方图一定含圈
D:一个立方图，它的边连通度可能等于1
答案: 【一个立方图，它的边连通度不可能等于1;
一个立方图一定有1-因子】
7、判断题：
设k是自然数，那么每个k-正则二部图包含1-因子。（ ）
选项：
A:对
B:错
答案: 【对】
8、判断题：
设一个图G有1-因子，那么对任意点子集S，G-S的奇分支数都小于等于S的点数。（ ）
选项：
A:对
B:错
答案: 【对】
9、判断题：
设对图G的任意点子集S，G-S的奇分支数都小于等于S的点数，那么图G也不一定有1-因子。（ ）
选项：
A:对
B:错
答案: 【错】
10、判断题：
每个立方图都有1-因子。（ ）
选项：
A:对
B:错
答案: 【错】