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

admin2018-08-12 54

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。

关于垄断组织的积极作用，不正确的说法是()。

绿林军领袖为了大影响，拥立汉宗室()为皇帝，恢复汉的国号，以公元23年为更始元年。

北约和华约两个组织对峙近半个世纪，其影响是()。

头下军州中，除了()和一半田租之外要全部上交辽中央，其他都归头下主所有。

简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1．．n，1．．n]，且压缩存储在B[1．．k]，则k的值至少为()。

由一组结构基因加上其上游的启动子和操纵基因组成的结构称为

非关键工作时差的调整应在其时差的范围内进行，以便更充分地利用资源、降低成本或满是施工的需要，可采用的调整方法之一是：

母公司在编制合并财务报表前，对子公司所采用会计政策与其不一致的情形进行的下列会计处理中，正确的有()。

道德作为一种特殊的社会意识形式，归根到底是由社会经济基础决定的。()

甲涉嫌犯聚众斗殴罪，在2010年8月9日被抓捕时逃跑。2014年6月5日，甲抢夺他人财物，数额特别巨大。下列选项中，正确的是()(2015年非法学基础课单选第4题)

设u＝f(x＋y，x2＋y2)，其中f二阶连续可偏导，求.

Thecountry’sinadequatementalhealthsystemgetsthemostattentionafterinstancesofmassviolencethatthenationhasseen

对长度为n的线性表作快速排序，在最坏情况下，比较次数为

Iamwritingthisathomebecauselastweekmyergonomic(符合人体工程学的)chairattheofficefellapart,unableanylongertobearmyw