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

admin2018-08-12 37

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

蒋介石在国民党的()全国代表大会上的对外关系演说表示国民党对日关系开始发生变化。

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

罗马帝国疆域扩张到顶点是在()统治时期。

《汉谟拉比法典》中规定：如果奴隶胆敢对主人说：“你不是我的主人。”他的耳朵就要被割掉。这部法典诞生于()。

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

封闭环：

土的无侧限抗压强度即其所受的最大轴向应力。()

居住区内住宅与道路的最小距离以道路边线为起算点，当道路设有人行便道时，道路边线是指下列哪项?[2010年第54题]

某一薄层且裂隙发育的石灰岩出露的场地，在距地面17m深处有一溶洞，洞室Ho=2.0m，按溶洞顶板坍塌自行填塞法对此溶洞进行估算，地面下不受溶洞坍塌影响的岩层安全厚度最接近()。(石灰岩松散系数取1.2)

1999年以后，我国金融债券的发行主体主要是()。

英国殖民主义哪一年宣布占领香港?()

消极完美主义者总是非常仔细地检查任何事情的细枝末节，有时竟达到()的地步。他们缺少一种适时放弃的智慧，他们所追求的“完美”，不是美学意义上的“完美”，而是一种非常刻板而教条式的“完美”。

下列关于《中华民国临时政府组织大纲》的表述中，正确的是()

Memberstateshadtheoptionto______fromthisagreementwithoneyear’snotice.