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

admin2019-01-16 79

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

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

杜鲁门总统执政时期，针对美国国内问题提出的计划是()。

导致东欧国家和苏联发生剧变的根本原因是()。

秦统一过程中，最先和最后灭掉的国家是()。

第二次世界大战后，世界形势变化的最大特点是()。

抗日战争期间，日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理，而名义是()

反映近代资产阶级政治思想萌芽的著名代表人物是()。

中华民国军政府是由下列哪个军阀成立的?()

Whathappenedtothewoman’sflight?

人体活动主要的直接供能物质是

患者女性24岁，因左上智齿颊向高位阻生，要求拔除注射局麻药后同侧颊部随即出现肿胀，这是发生了

风心病好发于哪个瓣膜

根据《上海证券交易所股票上市规则》，当上市公司涉及的诉讼金额占最近1期经审计净资产绝对值，涉案金额超过万元的重大诉讼、仲裁事项，应当及时披露。()[2017年9月真题]

在有些企业中，一方面存在5个人干3个人活的现象，另一方面在一些关键岗位上又缺乏合适人选，这种情况称为（）。

阿里山位于台湾省台北市东北，高山铁路、森林、云海、日出及晚霞，号称阿里山五奇。()

病人在医院里做检查常使用的“CT"技术，其术语是指(　　)。

传统的集合运算包括

WhatwillthemandoonSaturday?

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

计算机408

学硕统考专业

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

杜鲁门总统执政时期，针对美国国内问题提出的计划是()。

导致东欧国家和苏联发生剧变的根本原因是()。

秦统一过程中，最先和最后灭掉的国家是()。

第二次世界大战后，世界形势变化的最大特点是()。

抗日战争期间，日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理，而名义是()

反映近代资产阶级政治思想萌芽的著名代表人物是()。

中华民国军政府是由下列哪个军阀成立的?()

Whathappenedtothewoman’sflight?

人体活动主要的直接供能物质是

患者女性24岁，因左上智齿颊向高位阻生，要求拔除注射局麻药后同侧颊部随即出现肿胀，这是发生了

风心病好发于哪个瓣膜

根据《上海证券交易所股票上市规则》，当上市公司涉及的诉讼金额占最近1期经审计净资产绝对值________，涉案金额超过________万元的重大诉讼、仲裁事项，应当及时披露。()[2017年9月真题]

在有些企业中，一方面存在5个人干3个人活的现象，另一方面在一些关键岗位上又缺乏合适人选，这种情况称为（）。

阿里山位于台湾省台北市东北，高山铁路、森林、云海、日出及晚霞，号称阿里山五奇。()

病人在医院里做检查常使用的“CT"技术，其术语是指( )。

传统的集合运算包括

WhatwillthemandoonSaturday?

根据《上海证券交易所股票上市规则》，当上市公司涉及的诉讼金额占最近1期经审计净资产绝对值，涉案金额超过万元的重大诉讼、仲裁事项，应当及时披露。()[2017年9月真题]

病人在医院里做检查常使用的“CT"技术，其术语是指(　　)。