首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
admin
2019-03-15
73
问题
以下关于图的说法正确的是( )。
I 图G的生成树是该图的一个极小连通子图
Ⅱ 生成树中最长路径的起点和终点的度均为1
Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
选项
A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅱ
D、仅有Ⅱ
答案
D
解析
说法工是错误的，图G的生成树是该图的一个极小连通子图，但必须包含全部顶点。
说法Ⅱ是正确的，可用反证法证明。设v
1
，v
2
，…，v
k
是生成树的一条最长路径，其中，v
1
为起点，v
k
为终点，若v
k
的度为2，取v
k
的另一个邻接点v，由于生成树中无回路。所以，v在最长路径上，显然v
1
，v
2
，…，v
k
，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v
1
的度不能大于1，只能为1。
说法Ⅲ是错误的，只有连通图从某个顶点出发进行一次遍历，可访问图的所有顶点。
转载请注明原文地址:https://kaotiyun.com/show/xBCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下面哪项条约没有涉及德国的赔款问题?()
根据下列史料，说明朝鲜社会性质发生了怎样的变化。第四款朝鲜釜山之草粱项设有日本公馆，久为两国人民通商之地。从今日起，改革从前惯例及岁遣船等事，以此次新订条款为标准，办理贸易事务，朝鲜政府开放第五款所载两口岸，准日本人民往来通商，随意在该两地租借地
中国抗战在世界反法西斯战争中的作用。
系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。
下列选项中，不属于“文革”中对“左”倾错误进行纠正的是()
如下图所示为一个网络连接的示意图，主机1到主机2采用了SLIP网络连接，SLIP网络可以传输的最大数据段是296字节，主机2和主机3使用了以太网连接。请问：(1)为了使IP不分片，主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。
某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。
对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。
若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。
随机试题
货恶其弃于地也，而不必藏于己。
患者耳鸣不断，按之不减，烦躁易怒，胸胁胀痛，口苦咽干，舌苔黄，脉弦数。治疗除取听会、翳风、中渚、侠溪外，还应加
A．甲状腺危象B．喉返神经损伤C．喉上神经内支损伤D．喉上神经外支损伤E．手术区内出血术后呼吸困难和窒息
紫杉醇的生物活性与结构中最密切有关的基团是
压实黏性土壤路基时，可选用的压实机械有()。[2014年真题]
下列对会计本质的理解中，正确的有()。
下列对商业银行声誉风险管理的表述，正确的有()。
以下帝王谥号中表示褒扬的有()。
《关于推进公务员职业道德建设工程的意见》明确提出了24个字的中国特色公务员职业道德的主要内容，即：
下列选项中,属于非法人组织的是()。
最新回复
(
0
)
