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

admin2019-01-16 54

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

真理标准问题大讨论

在春秋晚期，提出了“兵者国之大事”“知彼知己”的思想家是()。

论述周公东征的作用与意义。

在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

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

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

MaisonPlanisarecentlycreatedcompanywithamissiontoprovideprivatehomeownerswithgoodquality,ongoingsupportservic

女，56岁。右利手，突然语言困难2天。有心房颤动病史7年。查体：神志清楚，四肢运动感觉无异常。门诊医生问诊：“生什么病?”答：“呀!吃饭吗?”医生：“把右手举起来。”答：“是”，却向门口走去。最可能的原因是

A．直肠给药B．舌下给药C．呼吸道给药D．经皮给药E．口服给药气体、易挥发的药物或气雾剂的适宜给药途径是

根据个人所得税法的相关规定，关于个人取得拍卖收入的说法，表述正确的有()。

下列关于负债流动性的说法，正确的有()。

企业发生的下列经济活动中，不能改变其速动比率水平的有()。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。

下面关于PC主板BIOS的叙述中，错误的是______。A)主板BIOS是指固化在主板ROM芯片中的一组程序B)PC加电后首先运行主板BIOS中的程序，然后加载操作系统C)主板BIOS包含了PC所有外设的驱动程序D)在PC加电自检过程中，按

Afterayear’shardworkIthinkIam______toalongholiday.

Forthesereasons,thenewspaperishaving______problemsinthenorthofthecountry.