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

admin2019-03-15  43

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

选项 A、I、Ⅱ   
B、Ⅱ、Ⅲ   
C、I、Ⅱ   
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/xBCi777K
0

最新回复(0)