以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

admin2019-03-15 51

问题以下关于图的说法正确的是( )。
I  图G的生成树是该图的一个极小连通子图
  Ⅱ 生成树中最长路径的起点和终点的度均为1
  Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

选项 A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅱ
D、仅有Ⅱ

答案D

解析说法工是错误的，图G的生成树是该图的一个极小连通子图，但必须包含全部顶点。
说法Ⅱ是正确的，可用反证法证明。设v₁，v₂，…，v_k是生成树的一条最长路径，其中，v₁为起点，v_k为终点，若v_k的度为2，取v_k的另一个邻接点v，由于生成树中无回路。所以，v在最长路径上，显然v₁，v₂，…，v_k，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v₁的度不能大于1，只能为1。
说法Ⅲ是错误的，只有连通图从某个顶点出发进行一次遍历，可访问图的所有顶点。

转载请注明原文地址:https://kaotiyun.com/show/xBCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

计算机408

学硕统考专业

度田事件

简述清末新政的内容及作用。

基辅罗斯国家对居民征税的方式是()。

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为：intIsFull_Bitree(BitreeT)。

世界上的生物正以每月一种的速度消失，按照此速度，大约400年以后世界上将有五分之四的生物消失。以下哪项为真，最能反驳上述观点?

有关剂量体积直方图(DVH)描述正确的是哪项

在行政诉讼中，人民法院可以主动收集证据的情况包括（）。(2009年多项选择第52题)

下列属于总分类科目的有()。

公元前21世纪，禹建立夏王朝起，我国开始了奴隶社会。()

阿尔法女孩：指许多方面的能力和表现都在同龄男性之上的年轻女性，下列不属于阿尔法女孩的是：

设z=f[xg(y)，x—y]，其中f二阶连续可偏导，g二阶可导，求

设A=[68-2]，B=68-2、C=“6*8-2”，属于合法表达式的是()。

Theworld’senvironmentissurprisinglyhealthy.Discuss.Iftherewereanexaminationtopic,moststudentswouldtearitapart

以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点

计算机408

学硕统考专业

度田事件

简述清末新政的内容及作用。

基辅罗斯国家对居民征税的方式是()。

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为：intIsFull_Bitree(BitreeT)。

世界上的生物正以每月一种的速度消失，按照此速度，大约400年以后世界上将有五分之四的生物消失。以下哪项为真，最能反驳上述观点?

有关剂量体积直方图(DVH)描述正确的是哪项

在行政诉讼中，人民法院可以主动收集证据的情况包括（）。(2009年多项选择第52题)

下列属于总分类科目的有()。

公元前21世纪，禹建立夏王朝起，我国开始了奴隶社会。()

阿尔法女孩：指许多方面的能力和表现都在同龄男性之上的年轻女性，下列不属于阿尔法女孩的是：

设z=f[xg(y)，x—y]，其中f二阶连续可偏导，g二阶可导，求

设A=[6*8-2]，B=6*8-2、C=“6*8-2”，属于合法表达式的是()。

Theworld’senvironmentissurprisinglyhealthy.Discuss.Iftherewereanexaminationtopic,moststudentswouldtearitapart

设A=[68-2]，B=68-2、C=“6*8-2”，属于合法表达式的是()。