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

admin2023-02-06 43

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/frPiFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

教学是在教师与学生的交往和对话过程中，使每个学生都达到最佳水平的活动。()

学习策略的掌握需要学生不断实践。在训练学生运用各种学习策略时，应遵循的原则是()。

李磊和几个平时关系不错的同班同学经常一起玩耍，久而久之便形成了一个小群体。他们组成的小群体经常会与班主任和班委会对抗，还不参加集体活动。他们这个群体属于()。

在实际教学过程中，张老师采用画小红花、插小红旗等方式鼓励学生的德育方法是()。

关于教师和学生关系的两个对立观点是()。

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

等距抽样

可引起大叶性肺炎的病原菌有

男性，65岁。因椎-基底动脉系统血栓形成入院，其临床表现中哪项不应出现

茶碱类治疗支气管哮喘的作用机制是

女性，45岁，劳累后心悸、气急6年。查体：二尖辩面容，第一心音亢进，心尖部可闻及隆隆样舒张期杂音，有开瓣音，心律规则。本次因呼吸困难不能平卧入院。该病人首要的护理问题是

新生儿缺氧、缺血性脑病时发生惊厥，首选的药物是

《宪法》规定，国家为了公共利益的需要，可以依照法律规定对土地实行()并给予补偿。

某学校甲、乙、丙三位老师年龄各不相同，一位喜欢足球，一位喜欢篮球，一位喜欢排球。现在知道：甲比喜欢足球的人年龄大；喜欢排球的老师比喜欢篮球的老师年龄小；乙老师年龄最大。由此可以推出()。

设函数y=y(x)由参数方程(t＞1)所确定，求d2y／dx2|x=9。