证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。

admin2023-02-06 44

问题证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。

选项

答案此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(A[i][j]=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)

解析

转载请注明原文地址:https://kaotiyun.com/show/RbwD777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。

计算机408

学硕统考专业

板书要求整齐、规范、美观，因此板书的文字、图表等格式要统一，不得有变化。()

杨毅在学习过程中，将自己的笔记本划分成两半，一半记录老师上课时所讲的内容，另一半记录自己不懂的地方或重要的地方。杨毅在这一过程中使用的学习策略属于()。

优秀的足球运动员会利用技巧使踢出的足球在空中旋转，旋转的足球在行进过程中会突然改变原来的运动方向并转弯，这被称为“香蕉球”。下列选项的物理原理与“香蕉球”原理不同的是：

下列关于地图的叙述正确的是：

若信道上有9个再生中继器，再生中继传输系统全程误码率不超过10-6，每个中继段的误码率应小于多少?

举例说明词的非理性意义主要体现在哪些方面。

听觉敏感度下降10分贝，离开噪声环境可恢复正常属于听力下降，听觉器官出现病理性改变，离开噪声环境不能恢复正常属于

逾期提取标的物或者逾期付款的，遇价格上涨时，按新价格执行；价格下降时，按原价格执行。()

下列各项中，应按税法规定计算征收增值税的有()。

“阿伦森效应”指的是随着奖励减少而导致态度逐渐消极。随着奖励增加而导致态度逐渐积极的心理现象。根据上述定义，下列不属于“阿伦森效应”的是：()

项目的可行性研究内容一般应包括如下内容()。①投资必要性；②技术的可行性；③财务可行性；④组织可行性；⑤经济可行性；⑥社会可行性；⑦风险因素及对策。

AustralianminingentrepreneurClivePalmeronTuesdayunveiledblueprintsforTitanicII,amodernreplicaofthedoomedocean