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

admin2019-03-15 61

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

学硕统考专业

1925年10月签订《洛迦诺公约》后，法国外长白里安认为：“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。

洋务派创办军事工业的方式是()。

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

下列选项中，不属于“文革”中对“左”倾错误进行纠正的是()

1900年10月修订《英、德扬子协定》规定:将中国之江河及沿海各口岸各国贸易及其他正当经济活动，自由开放，毫无差别并知会各国。该协定:

8岁男孩，右小腿轻微外伤后发热5天，右小腿上端肿胀，剧痛，局部皮温高，肤色正常，白细胞计数25×109／L，X线片未见明显变化，局部穿刺，针达骨膜下时抽出黄色脓液，首先应考虑为

下列属于促进吸收增加疗效的是()。

具有法律地位的药品标准指的是()。

基础租金是业主获取的、与租户经营业绩不相关的一个最低收入。()

现有一蒸汽热网工程准备施工，其条件是：(1)在寒冷北方某城市露天敷设，回水为凝结水。(2)蒸汽压力P=1．8MPa，t=250℃，干管DN=600mm，3处支管DN=500mm。(3)管网要穿过一条道路，而且要穿越几堵围墙。(4)已进了几批钢

下列风险中，不属于市场风险的是()。

_________是指20世纪初期中国各地新式学校中音乐课程中大量传颂的一些原创歌曲。

在教育改革中，只有真正把学生看成学校生存之本，把促进学生发展看学校发展之本，才能真正让教育改革惠及每一名学生。由此可以推出

Imagineaschoolthatexpecteditsstudentstobecomeliteratewithoutanyformalinstruction.Mostparentswouldbealarmedby

_____haswonthenameof"thefatherofAmericanliterature".