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

admin2019-01-16 73

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

与秦汉史学相比，唐代史学的特点是()①产生了第一部史论专著②出现了典章制度的专史③确立了官修正史的制度④首创了纪传体通史巨编

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

1936年苏联宪法规定苏联的国体是()。

范仲淹在《答手诏条陈十事》中提出，庆历新政的核心内容是()。

1861年俄国废除农奴制改革的主要作用是()。①造成资本集中②扩大了国内市场③增加了自由劳动力④强化了中央集权

中国第一条自行设计修建的铁路是在()。

红山文化的代表性墓葬形式为()。

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

A．痉挛(偏瘫)型B．痉挛(双瘫)型C．痉挛(四肢瘫)型D．共济失调型E．手足徐动型患儿，5岁。出生时有颅内出血，现四肢运动障碍明显，张力增高，屈膝屈肘时常有屈曲性挛缩，膝腱反射亢进，巴氏征阳性。其类型是哪种

我国遴选非处方药的指导思想是

关于行政机关和机构的设立，下列哪些说法是不正确的？

李伍为惯常居所地在甲国的公民，满成为惯常居所地在乙国的公民。甲国不是《保护文学艺术作品伯尔尼公约》缔约国，乙国和中国是该公约的缔约国。关于作品在中国的国民待遇，下列哪些选项是正确的?(2012年试卷一第82题)

下列属于国家颁布的淘汰的灭火器的有()。

某居民纳税人，2012年财务资料如下：收入合计55万元，成本合计30万元，经税务机关核实，企业未能正确核算收入，税务机关对企业核定征收企业所得税，应税所得率为15％，2012年应纳企业所得税为()万元。

有限责任公司的主要特征有()。

美国高等教育有三大职能：教学、研究和________。