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

admin2021-08-17 49

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下图所示为一个局域网的连接图，每个计算机的IP地址和物理地址如下表所示：假设该局域网采用了以太网，需要达到100Mbps的数据传送率，那么线路的带宽最小为多少?

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

在文件的逻辑组织中，不属于记录文件的是()。

假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、22。T0时刻的资源分配情况如下表所示，此时存在的一个安全序列是

计算机网络由哪些部分组成?什么是通信子网和资源子网?试述这种层次结构观的特点以及各层的作用。

[x]补=1．x1x2)x3x4，则当满足()时，x>一1／2成立。

引起女阴萎缩性营养不良的原因主要是：

细菌的致病性强弱主要取决于()。

交换的积分次序．

根据个人所得税法律制度的规定，下列各项中，暂减按10％税率征收个人所得税的是()。

图中最陡峭的地方是()。

电影类型是怎样形成的?类型电影有何特征?

Youmaysaythatthebusinessofmarkingbooksisgoingtoslowdownyourreading.(31)probablywill.That’soneofthe(32)fo

______referstoabranchoflinguisticsconcernedwiththeuseoflanguageinsocialcontextsandthewaysinwhichpeopleprodu