首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
以下关于图的说法正确的是( )。 I 图G的生成树是该图的一个极小连通子图 Ⅱ 生成树中最长路径的起点和终点的度均为1 Ⅲ 对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点
admin
2019-03-15
95
问题
以下关于图的说法正确的是( )。
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
学硕统考专业
相关试题推荐
关于“一战”后构筑的凡尔赛体系，说法不正确的是()。
1925年10月签订《洛迦诺公约》后，法国外长白里安认为：“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。
“二战”后世界经济发展变化迅速，这种变化主要表现在()。①国际金融体系和贸易体系的形成②国家垄断资本主义的空前发展③形成以美、苏“冷战”为特征的两极格局④科学技术推动生产力发展更为迅速
鸦片战争前中国同英国相比在政治、经济和军事上存在着哪些差距?到19世纪60年代．外来因素使中国社会出现了哪些变化?变化中进步的主流是什么?
在明朝中叶，农业生产发生了一件非常重要的事件——()，对于当时的食物结构产生了重大的影响
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50
请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为：intIsFull_Bitree(BitreeT)。
设结点x和y是二叉树中任意的两个结点，在该二叉树的先序遍历序列中x在y之前，而在其后序遍历序列中x在y之后，则x和y的关系是()。
随机试题
国际海上货物运输中，不具有物权凭证作用的单据是()
支配臂肌前群的神经是
除了哪一种化合物外，下列化合物都含有高能键?
申请领购增值税专用发票的单位和个人，除了提供经办人身份证明、税务登机证件或者其他有关证明以及财务印章或者发票专用章的印模外，还应当提供加盖有“增值税一般纳税人”确认专用章的()。
商业理财业务的核心活动是()。
某公司2005年1—4月份预计的销售收入分别为100万元、200万元、300万元和400万元，每月材料采购按照下月销售收入的80%采购，采购当月付现60%，下月付现40%。假设没有其他购买业务，则2005年3月31日资产负债表“应付账款”项目金额和2005
简析近代早期殖民强国葡萄牙、西班牙衰落的原因。(2009年统考真题)
下面对对象概念描述正确的是
Онивстретилисьтак,____ониблизкиедрузья.
________peoplediedinthepowerfulstorm.
最新回复
(
0
)
