图论及其应用知到智慧树章节测试课后答案2024年秋山东大学

图论及其应用知到智慧树章节测试课后答案2024年秋山东大学第一章单元测试

一个图的边数m和所有点的度和r的关系是（）。

A:r=m/3B:r=2mC:r=m+1D:r=m

答案:r=2m下列说法正确的是（）。

A:一条迹上的边可以重复B:一条路上的点可以重复C:边不重复的途径称为迹D:点不重复的途径称为路

答案:边不重复的途径称为迹；点不重复的途径称为路图的周长是其中最长圈的长度。（）

A:对B:错

答案:对图的一个连通分支是它的一个极大连通子图。（）

A:错B:对

答案:对一个图的点连通度小于等于它的边连通度。（）

A:对B:错

答案:对一个图的点连通度和边连通度不一定小于等于最小度。（）

A:对B:错

答案:错有向图是强连通的是指，对其中的任意有序点对x，y，都有从x到y的路。（）

A:对B:错

答案:对下列说法正确的是（）。

A:树是无圈的连通图B:一棵树的两个点之间仅有一条路C:如果一棵树的最大度是k，那么至少有k个叶子顶点D:一棵树可能含圈

答案:树是无圈的连通图；一棵树的两个点之间仅有一条路；如果一棵树的最大度是k，那么至少有k个叶子顶点一个二部图可能含奇圈。（）

A:错B:对

答案:错一个连通图如果没有奇度顶点，则它是欧拉图。（）

A:对B:错

答案:对

第二章单元测试

如果一个图的每个顶点的度都等于k，那么它是k-正则的。（）

A:错B:对

答案:对如果存在关于匹配M的增广路，那么M可能是最大匹配。（）

A:对B:错

答案:错下列说法错误的是（）

A:2-因子的每个分支都是圈B:1-因子是图的完美匹配C:设二部图G=(X,Y)有1-因子，但是可能存在X的一个子集S，使得|N(S)|<|S|D:二部图中最大匹配的边数等于其边的顶点覆盖的最小基数

答案:设二部图G=(X,Y)有1-因子，但是可能存在X的一个子集S，使得|N(S)|<|S|图的一个1-因子也称为完美匹配，包含了图的所有顶点。（）

A:对B:错

答案:对一个无桥的立方图，它的边连通度可能等于1。（）

A:对B:错

答案:错下列说法错误的是（）

A:一个立方图，它的边连通度可能等于1B:一个立方图一定有1-因子C:一个立方图，它的边连通度不可能等于1D:一个立方图一定含圈

答案:一个立方图一定有1-因子；一个立方图，它的边连通度不可能等于1设k是自然数，那么每个k-正则二部图包含1-因子。（）

A:对B:错

答案:对设一个图G有1-因子，那么对任意点子集S，G-S的奇分支数都小于等于S的点数。（）

A:错B:对

答案:对设对图G的任意点子集S，G-S的奇分支数都小于等于S的点数，那么图G也不一定有1-因子。（）

A:对B:错

答案:错每个立方图都有1-因子。（）

A:错B:对

答案:错

第三章单元测试

如果图G是k-连通的，那么任意删掉k-1点，它仍然是连通的。（）

A:对B:错

答案:对下列说法正确的是（）

A:一个2-连通图的最小度可以很大B:一个2-连通图可能含有割点C:如果G是2-连通图，那么从图中去掉任意一个点，这个图仍然是连通的。D:一个2-连通图的最小度等于2

答案:一个2-连通图的最小度可以很大；如果G是2-连通图，那么从图中去掉任意一个点，这个图仍然是连通的。下列哪个说法是错误的（）

A:块是一个没有割点的极大连通分支。B:图中的孤立点不是块。C:每个连通图的块图是一棵树D:图中的孤立点和孤立边都是块

答案:图中的孤立点不是块。四个点的完全图不是3-连通图。（）

A:对B:错

答案:错如果G是一个3-连通图，但它不是四个点的完全图，那么G中有一条边e，使得G/e仍然是3-连通图。（）

A:错B:对

答案:对对于有向图G的两个点s，t，G中存在k条弧不交的s-t路的充要条件是任意删掉k-1条边，s仍然可以到达t。（）

A:错B:对

答案:对一个阶大于k的图G是k-连通的，当且仅当对于G的两个点s，t，G中存在k条独立的s-t路。（）

A:错B:对

答案:对如果图G是k-边连通的，那么对于G的两个不交点集A和B，在A和B之间存在k条边不交的路。（）

A:错B:对

答案:对如果图G是k-连通的，那么它也是k-连接的。（）

A:对B:错

答案:错对于任意自然数k，存在一个函数f(k)，使得每个f(k)-连通的图是k-连接的。（）

A:错B:对

答案:对

第四章单元测试

下列说法正确的是（）

A:五个点的完全图不是可平面图B:四个点的完全图是可平面图C:如果一个图的细分图是可平面图，那么这个图是可平面图D:如果一个图是可平面图，那么这个图的细分图是可平面图

答案:五个点的完全图不是可平面图；四个点的完全图是可平面图；如果一个图的细分图是可平面图，那么这个图是可平面图；如果一个图是可平面图，那么这个图的细分图是可平面图在一个2-连通平面图中，每个面被一个圈所界定。（）

A:对B:错

答案:对下列说法正确的是（）

A:对偶图的边对应原图的边B:对偶图的顶点对应原图的面C:一个平面图的对偶图的对偶图就是它本身D:一个平面图的对偶图是可平面的

答案:对偶图的边对应原图的边；对偶图的顶点对应原图的面；一个平面图的对偶图的对偶图就是它本身；一个平面图的对偶图是可平面的平面图的对偶图是连通的。（）

A:错B:对

答案:对设一个平面图的点数、边数和面数分别是n、m和l，下列说法正确的是（）

A:n-m+l=-1B:n-m+l=1C:n-m+l=2D:n、m和l没有关系

答案:n-m+l=2一个简单平面图的边数和点数的关系是：m不大于3n-6。（）

A:对B:错

答案:对Petersen图是可平面图。（）

A:对B:错

答案:错每个平面图的最小度至多为5。（）

A:对B:错

答案:对在一个无环的3-连通图中，任意一个点的所有邻点在同一个圈上。（）

A:错B:对

答案:对由Kuratowski定理可以判定Petersen图是非平面图。（）

A:错B:对

答案:对

第五章单元测试

每个平面图是5-可着色的。（）

A:错B:对

答案:对下列说法正确的是（）

A:一个图的色数可能等于它的最大度加1。B:一个图的色数可能与点数有关。C:一个图的色数小于等于它的最大度加1。D:一个奇圈的色数等于3。

答案:一个图的色数可能等于它的最大度加1。；一个图的色数可能与点数有关。；一个图的色数小于等于它的最大度加1。；一个奇圈的色数等于3。非平凡二部图的色数等于2。（）

A:对B:错

答案:对二部图的边色数等于它的最大度。（）

A:错B:对

答案:对在正常边着色图中，由两种不同颜色构成的途径不一定是一条路，其中的点可以重复。（）

A:对B:错

答案:错Vizing定理告诉我们，一个图的边色数介于最大度与最大度加1之间（）

A:对B:错

答案:对每个k-色图都包含一个最小度至少为k-1的k-色子图。（）

A:错B:对

答案:对二部图是Vizing定理的第一类图。（）

A:对B:错

答案:对Vizing定理把有限图分为两类：色数等于最大度的图为第一类，色数等于最大度加1的图为第二类。（）

A:对B:错

答案:对如果一个图G的任意导出子图H，都满足H的色数等于H的团数，那么称G是完美图。（）

A:错B:对

答案:对

第六章单元测试

P问题是指是可以有一个确定型图灵机在多项式时间内解决的问题。（）

A:错B:对

答案:对NP问题是指可以在多项式时间内被图灵机验证的问题。（）

A:错B:对

答案:对一个问题如果是NP-Hard问题，那么它一定是NP问题。（）

A:对B:错

答案:错NPC问题是指既是NP问题又具有特定性质，即任何NP问题都可以在多项式时间内归约到该问题。（）

A:对B:错

答案:对如果一个问题是NP-Hard，它的意思是：（）

A:该问题可以在多项式时间内解决B:该问题比NP问题更容易C:该问题一定是NP问题D:任何NP问题都可以在多项式时间内归约到该问题

答案:任何NP问题都可以在多项式时间内归约到该问题如果一个问题可以在多项式时间内解决，它被归类为：（）

A:NPC问题B:NP-Hard问题C:P问题D:NP问题

答案:P问题下列哪些问题是NP问题？（）

A:哥德尔不完备定理B:背包问题C:最大团问题D:旅行推销员问题(TSP)

答案:背包问题；最大团问题；旅行推销员问题(TSP)NPC问题的证明通常涉及哪种类型的归约？（）

A:线性归约B:对数归约C:多项式归约D:指数归约

答案:多项式归约在证明一个问题是NPC时，需要满足什么条件？（）

A:问题必须属于P类B:问题必须有多项式时间算法C:问题必须可以在线性时间内解决D:问题必须是NP问题

答案:问题必须是NP问题如果一个问题被证明是NPC问题，它的意义是什么？（）

A:该问题的解法可以在非常短的时间内找到B:该问题的解法可以在多项式时间内找到C:该问题在实际中没有任何应用D:该问题与其他NP问题具有相似的计算复杂性

答案:该问题与其他NP问题具有相似的计算复杂性

第七章单元测试

下列说法错误的是（）

A:最大度至少为4的子式是拓扑子式B:拓扑子式一定是子式C:最大度至多为3的子式是拓扑子式D:子式一定是拓扑子式

答案:最大度至少为4的子式是拓扑子式；子式一定是拓扑子式所有不包含4个点的完全图作为子式的边极大图的边数不一定相同。（）

A:对B:错

答案:错n个顶点的Turan图关于点数和r个点的完全图是极值的，并且是唯一的。（）

A:对B:错

答案:对每个平均度至少为2的r-2次幂的图都包含一个r个点的完全图作为它的子式。（）

A:错B:对

答案:对每个最小度至少为3，围长至少为f(r)的图，都包含一个r个点的完全图作为子式。（）

A:对B:错

答案:对

第八章单元测试

在Prim算法中，从一个起始节点开始，逐步添加节点以构建最小生成树。（）

A:对B:错

答案:对Kruskal算法和Prim算法在找到最小生成树时得到的结果总是相同的。（）

A:错B:对

答案:错Kruskal算法总是选择连接两个独立的连通分量的边。（）

A:错B:对

答案:对集合覆盖问题的目标是什么？（）

A:最小化集合元素的数量B:最小化集合的数量C:最大化集合的数量D:最大化集合元素的数量

答案:最小化集合的数量什么是绝对近似算法？（）

A:一种总是能找到最优解的算法B:一种总是能找到精确解的算法C:一种在多项式时间内找到近似解的算法D:一种在指数时间内找到最优解的算法

答案:一种在多项式时间内找到近似解的算法Prim算法和Kruskal算法都可以用于解决最小生成树问题。它们之间的主要区别是：（）

A:Prim算法基于节点的操作，而Kruskal算法基于边的操作。B:Prim算法总是生成相同的最小生成树。C:Prim算法总是比Kruskal算法更高效。D:Kruskal算法总是生成相同的最小生成树。

答案:Prim算法基于节点的操作，而Kruskal算法基于边的操作。在Prim算法中，如果图是不连通的，算法将会：（）

A:陷入无限循环B:无法执行C:可以执行但得到不完全的最小生成树D:正常执行

答案:可以执行但得到不完全的最小生成树当最小生成树不唯一时，哪些因素可能导致不同的最小生成树？（）

A:不同算法B:边权重相同C:不同起始节点D:图不是连通图

答案:不同算法；边权重相同；不同起始节点关于k因子近似算法，哪些描述是正确的？（）

A:k因子近似算法总是提供精确的解。B:k因子近似算法的性能通常与近似因子k有关。C:k因子近似算法通常运行时间很长。D:k因子近似算法通常用于解决组合优化问题。

答案:k因子近似算法的性能通常与近似因子k有关。；k因子近似算法通常用于解决组合优化问题。

第九章单元测试

对任意的自然数r，下列说法错误的是（）

A:B:C:D:

答案:；若T是一个树，那么存在无限个关于T是Ramsey极小的图。（）

A:错B:对

答案:错Ramsey定理简单来说就是：给定一个正整数r，每个充分大的图G都包含r个点的完全图作为导出子图。（）

A:对B:错

答案:错对每个自然数r，都存在自然数n，使得每个连通图（阶数至少为n）一定包含哪些作为导出子图？（）

A:B:C:D:

答案:对于稀疏图的Ramsey数有以下性质：具有有界最大度的图H的Ramsey数以|H|的指数方式增长。（）

A:错B:对

答案:错

第十章单元测试

如果一个图G的最小度大于点数的一半，则G是连通的。（）

A:对B:错

答案:对哈密顿圈问题是NP-C问题。（）

A:错B:对

答案:对下列说法错误的是（）

A:图中最小独立集的点数，称为它的独立数B:如果S是图的独立集，那么S中任意两个顶点不相邻C:图的连通度是图中最小分离集的点数D:图中最大独立集的点数，称为它的独立数

答案:图中最小独立集的点数，称为它的独立数如果一个图的独立数小于等于它的连通度，那么这个图是哈密顿的。（）

A: