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

admin2019-03-15 58

问题以下关于图的说法正确的是( )。
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

学硕统考专业

度田事件

下面哪项条约没有涉及德国的赔款问题?()

论述印度非暴力运动的过程和失败原因。

第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式，最早提出这种方式的是（）。

欧洲历史上第一部系统完备的法典是（）。

论述屋大维的元首政制的统治特点。

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

ICMP在TCP／IP协议集中属于()。

在分光光度法中，应用光的吸收定律进行定量分析，应采用的入射光为

与上颌窦关系最密切的是哪一组牙离下颌管最近的是哪一组牙

下列属于休克中医病机的是()

加权平均投资组合收益率是对投资组合中所有债券的收益率按各自所占比重作为权重进行加权平均后得到的收益率。()

债券的预期货币收入的来源为(　　)。

零贝塔系数的投资组合的预期收益率是()。

陶行知先生提出的“接知如接枝”体现了教学的()。

借鉴汉字行书字体创造日本行书假名——平假名的是()。

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

计算机408

学硕统考专业

度田事件

下面哪项条约没有涉及德国的赔款问题?()

论述印度非暴力运动的过程和失败原因。

第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式，最早提出这种方式的是（）。

欧洲历史上第一部系统完备的法典是（）。

论述屋大维的元首政制的统治特点。

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

ICMP在TCP／IP协议集中属于()。

在分光光度法中，应用光的吸收定律进行定量分析，应采用的入射光为

与上颌窦关系最密切的是哪一组牙离下颌管最近的是哪一组牙

下列属于休克中医病机的是()

加权平均投资组合收益率是对投资组合中所有债券的收益率按各自所占比重作为权重进行加权平均后得到的收益率。()

债券的预期货币收入的来源为( )。

零贝塔系数的投资组合的预期收益率是()。

陶行知先生提出的“接知如接枝”体现了教学的()。

借鉴汉字行书字体创造日本行书假名——平假名的是()。

债券的预期货币收入的来源为(　　)。