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

admin2018-08-12 56

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列不是苏俄实行战时共产主义政策原因的是()。

1925年爆发的当时世界上罢工时间最长的一次斗争是()。

第二次工业革命引起的生产关系方面最突出的变化是()。

隋在统一全国的过程中，平定江南是一个重要的部分，帮助完成岭南一带平定的是()

下面有关兵制的内容，与唐玄宗有关的是()

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

1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。

判断英国工业革命基本完成的主要依据是()

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

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

门诊发现传染病患者时，应立即采取的措施是

奶制品中，不宜作为婴儿主食的是

患者，男性，64岁。反复咳嗽、咳痰，痰中带血2周。查体：体温38．3℃，WBC12×109／L。胸片示右肺门肿块影，伴远端大片状阴影。抗感染治疗阴影不吸收。有助于尽快明确诊断的检查首选

关于合同成立地点的说法，正确的是()。

根据《中华人民共和国票据法》的规定，下列各项中，属于票据行为的有()。

下列货物销售征收消费税的有()。

一个半断路器接线属于无母线接线。()

(1)记者与当事人电话联系(2)记者听说一件资助失学少年的事情(3)一篇感人的报道引起了反响(4)当事人不愿将自己的事情“曝光”(5)记者到学校进行调查和采访

发展由国家和集体控股的股份制企业，有利于()。

Concerningmoneyoranythingelse,conflictsbetweenhusbandandwifeusuallyreflectapowerstruggle.Conflictsbetweenparent