图论及其应用智慧树知到期末考试答案章节答案2024年山东大学

图论及其应用智慧树知到期末考试答案+章节答案2024年山东大学下列错误的是（）。

答案:一个平面图的对偶图不一定是可平面的###对偶图的顶点对应原图的边###对偶图的边对应原图的点如果一个图的最小度至少为2，那么它就包含圈。（）

答案:对一个2-连通的平面图的对偶图是2-连通的。（）

答案:对任意一个竞赛图都包含哈密顿圈。（）

答案:错

答案:错

答案:对如果一个问题是NP问题，那么它的解一定可以在多项式时间内找到。（）

答案:错

答案:对在正常边着色图中，由两种不同颜色构成的途径实质上是一条路。（）

答案:对一个图的直径小于等于半径的二倍。（）

答案:对算法的时间复杂度描述的是执行算法所需的物理（实际）时间。（）

答案:错树是连通的森林。（）

答案:对如果一个图是5-可着色的，那么它的点色数可能是（）。

答案:5###4###3什么是最大团问题的目标？（）

答案:找到一个图中的最大团###证明一个图中不存在最大团下列关于2-连通平面图说法正确的是（）。

答案:它的对偶图不存在割边###它的对偶图不存在割点###它的对偶图是连通的###它的对偶图是2-连通的

答案:以下哪个问题属于P问题？（）

答案:线性方程组的解###判断一个图是否为树

答案:

答案:哈密顿圈问题属于什么问题？（）

答案:NP-C

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

答案:下列关于求最小树的Kruskal算法和Prim算法的正确说法是？（）

答案:

答案:3SAT问题是关于什么类型的布尔公式？（）

答案:三元布尔公式

答案:关于Ramsey定理，下列说法正确的是（）。

答案:图的完美匹配指的是（）。

答案:1-因子包含5-圈这一性质的阈函数是（）。

答案:如果k是至少为3的正整数，那么t(n)=1/n是包含3-圈这一性质的阈函数。（）

答案:对对于每个介于0和1之间的常数p和任意图H，几乎每个随机图包含H的一个导出拷贝。（）

答案:对用概率方法可以证明存在一个图具有大围长和大色数。（）

答案:对在随机图中，一条边存在的概率是p，不存在的概率为q，那么p+q<1。（）

答案:错对于随机变量X和正实数a，X≥a的概率小于等于X的期望除以a。（）

答案:对一个图G的线图L(G)的顶点集是G的边集。（）

答案:对任意一个竞赛图都有一个哈密顿路。（）

答案:对假设简单图G的阶为n，并且G中有两个点的度为n-1，那么G中可能存在一个点，其度为1。（）

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

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

答案:对如果图中任意一对不相邻顶点的度和都大于图的阶，那么图是哈密顿的。（）

答案:对一个强连通的竞赛图不一定含有3-圈。（）

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

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

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

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

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

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

答案:Prim算法和Kruskal算法都可以用于解决最小生成树问题。它们之间的主要区别是：（）

答案:Prim算法基于节点的操作，而Kruskal算法基于边的操作。关于k因子近似算法，哪些描述是正确的？（）

答案:k因子近似算法的性能通常与近似因子k有关。###k因子近似算法通常用于解决组合优化问题。在Prim算法中，从一个起始节点开始，逐步添加节点以构建最小生成树。（）

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

答案:最小化集合的数量在Prim算法中，如果图是不连通的，算法将会：（）

答案:可以执行但得到不完全的最小生成树什么是绝对近似算法？（）

答案:一种在多项式时间内找到近似解的算法Kruskal算法总是选择连接两个独立的连通分量的边。（）

答案:对当最小生成树不唯一时，哪些因素可能导致不同的最小生成树？（）

答案:边权重相同###不同起始节点###不同算法Kruskal算法和Prim算法在找到最小生成树时得到的结果总是相同的。（）

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

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

答案:对所有不包含4个点的完全图作为子式的边极大图的边数不一定相同。（）

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

答案:对如果一个问题可以在多项式时间内解决，它被归类为：（）

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

答案:问题必须是NP问题NPC问题的证明通常涉及哪种类型的归约？（）

答案:多项式归约如果一个问题被证明是NPC问题，它的意义是什么？（）

答案:该问题与其他NP问题具有相似的计算复杂性NPC问题是指既是NP问题又具有特定性质，即任何NP问题都可以在多项式时间内归约到该问题。（）

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

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

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

答案:任何NP问题都可以在多项式时间内归约到该问题下列哪些问题是NP问题？（）

答案:旅行推销员问题(TSP)###最大团问题###背包问题一个问题如果是NP-Hard问题，那么它一定是NP问题。（）

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

答案:对每个平面图是5-可着色的。（）

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

答案:对非平凡二部图的色数等于2。（）

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

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

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

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

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

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

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

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

答案:n-m+l=2由Kuratowski定理可以判定Petersen图是非平面图。（）

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

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

答案:对在一个2-连通平面图中，每个面被一个圈所界定。（）

答案:对平面图的对偶图是连通的。（）

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

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

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

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

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

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

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

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

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

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

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

答案:错图的一个1-因子也称为完美匹配，包含了图的所有顶点。（）

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

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

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

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

答案:错设k是自然数，那么每个k-正则二部图包含1-因子。（）

答案:对一个二部图可能含奇圈。（）

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

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

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

答案:对图的周长是其中最长圈的长度。（）

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

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

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

答案:对

答案:对

答案:错每个平面图中都存在一个顶点，它的度小于等于5。（）

答案:对一棵树中的任意两个顶点都被唯一的一条路连接。（）

答案:对

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

答案:对如果一个图是连通的，那么它一定有唯一的最小生成树。（）

答案:错块是一个没有割点的极大连通分支。（）

答案:对

答案:对

答案:对如果一个有向图的出度大于0，那么它包含一个圈。（）

答案:对如果一个图的独立数小于等于它的最小度，那么这个图是哈密顿的。（）

答案:错一个图的边着色数要么等于它的最大度，要么等于它的最大度加一。（）

答案:对一个块可以是2-连通图。（）

答案:对

答案:对每个强连通的竞赛图都包含一个4-圈（）

答案:对连通图中最小生成树的边数一定等于节点数减一。（）

答案:对

答案:对一个二部图一定不含奇圈。（）

答案:对

答案:对

答案:

答案:下列包含完美匹配的图是（）。

答案:无桥的立方图###有1-因子的图

答案:最小生成树问题的输入通常包括：（）

答案:图的邻接矩阵###图的边的权重

答案:关于竞赛图下列说法正确的（）。

答案:下列哪些的是关于树的性质（）。

答案:树是一个二部图###树的边数等于它的点数减一###树是极小连通的###树是极大无圈的一个5-连通的图，它的连通度可能是（）。

答案:6###7###5

答案:下列关于Hadwiger猜想说法正确的是（）。

答案:下列哪些图一定包含哈密顿圈（）。

答案:二部图的充要条件是（）。

答案:不含奇圈

答案:SAT问题是关于什么类型的问题？（）

答案:布尔逻辑问题

答案:下列关于图的染色数与边数的关系说法正确的是（）。

答案:

答案:

答案:下列关于简单平面图的说法正确的