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

admin2023-02-06 42

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

()的领导方式认为，学生对集体的喜爱、期望、归属感、团结性与作业水平及学习成绩有关，班主任应信赖集体，将班级作为教育的对象，而不是一对一地去对待每个学生。

区角游戏结束时，几个小朋友仍在大声讲话，没有收拾玩具。叶老师轻轻地唱起了收拾玩具的儿歌并把一盒雪花片放进了玩具柜。此时这几个小朋友安静地把玩具送了回去。叶老师运用的教育方法是()。

个体将在一种学习中习得的一般原理、方法、策略和态度等迁移到另一种学习中去叫作()。

2022年，中央一号文件《中共中央国务院关于做好2022年全面推进乡村振兴重点工作的意见》明确提出“三农”工作的首要任务是“全力抓好粮食生产和重要农产品的供给”。下列选项错误的是()。

对于________．

中医诊断(病名、分型)为中医治法为

A．神曲、莱菔子B．半夏、陈皮C．茯苓D．连翘E．山楂

纠纷发生后，下列不属于仲裁案件受理条件的是()。

2008年，甲公司发生了以下几笔经济业务：(1)2008年2月，在股票市场上，转让A公司的股票100000股，卖出价格为26元/股，该笔股票的购入价格为22元/股，买卖股票的手续费均为1%；(2)2008年10月，在外汇市场上，转让100

下图示意的某区域G1至G2的石油管道，是世界上纬度最高的石油管道。铺设该石油管道所要面对的自然困难是()。

下列哪种学习方式不是《普通高中数学课程标准(实验)》所提倡的。()

通知所传达的事项，往往要求被通知者快速办理，这体现了通知具有（）的特点。

主户和客户