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

admin2019-03-15 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/xBCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

论述欧洲一体化进程及其影响。

试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。

电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。

我国第一部系统的史学理论著作是（）。

下列关于提督学政的说法不正确的是()。

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：下列关于隋唐钱币的表述，不正确的是()

编写判定给定的二叉树是否是二叉排序树的函数。

若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。

设结点x和y是二叉树中任意的两个结点，在该二叉树的先序遍历序列中x在y之前，而在其后序遍历序列中x在y之后，则x和y的关系是()。

CO2气体保护焊有哪些缺点?

关于血型天然抗体哪项是正确的

患儿，5岁。发热恶寒，咳嗽声重，口不渴，咳痰白而清稀，舌质淡红，舌苔白，脉浮紧。其治法是()

根据我国的税收分类，下列税种中，不属于货物和劳务税类的有()。

编制安全技术措施计划的原则有()。

维护社会治安秩序是公安机关的()任务。

牢固树立群众意识，要求坚持以人为本，做到“权为民所用，情为民所系，利为民所谋”。()