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

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

admin2019-12-10  79
问题 以下关于图的说法正确的是(    )。
    Ⅰ  图G的生成树是该图的一个极小连通子图
　　Ⅱ  生成树中最长路径的起点和终点的度均为1
　　Ⅲ  对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
选项 A、Ⅰ、Ⅱ
B、Ⅱ、Ⅲ
C、Ⅰ、Ⅲ
D、仅有Ⅱ
答案D
解析 说法Ⅰ是错误的，图G的生成树是该图的一个极小连通子图，但必须包含全部顶点。说法Ⅱ是正确的，可用反证法证明。设v1，v2，…vk是生成树的一条最长路径，其中，v1为起点，vk为终点，若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路。所以，v在最长路径上，显然v1，v2，…，vk，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v1的度不能大于1，只能为1。说法Ⅲ是错误的，只有连通图从某个顶点出发进行一次遍历，可访问图的所有顶点。
转载请注明原文地址:https://kaotiyun.com/show/hz3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)