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

admin2019-01-16 37

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

简述路德“唯信称义”与加尔文“预定论”的关系与区别。

下列哪两个国家是第二次工业革命的发源地和“中心”?

解放军渡江战役中横渡长江的东西两个攻击点是()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

某DRAM芯片内部存储元排列成1024．×1024的矩阵，且已知其存取周期为0．1μs，最大刷新间隔为2ms。当采用异步刷新方式时，死时间()。

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

固定式锯架可以安装几种不同规格长度的锯条。()

我国企业现有股票种类包括()

A．支气管炎B．干性胸膜炎C．纵隔气肿D．肺栓塞E．纵隔肿瘤胸骨后闷痛、灼痛常伴有咳嗽多见于

有关肺下界的说法错误的是

A．下唇歪斜B．鼻唇沟变浅C．额纹消失D．伸舌时舌尖偏向患侧E．眼睑闭合不全舌下神经损伤表现为

房地产按其是否产生收益来划分,主要分为下列几类,其中正确的是()。

勃拉姆斯是德国作曲家，作品兼有_________手法和浪漫主义精神。

某单位今年一月份购买5包A4纸、6包B5纸，购买A4纸的钱比B5纸少5元；第一季度该单位共购买A4纸15包、B5纸12包，共花费510元；那么每包B5纸的价格比A4纸便宜：

语言中最小的音义结合的单位是_____。

A、Becausetheydonotwanttopayforthehouses.B、Becausetheyhavefinancialtroubles.C、Becausetheyliketravelingacrosst