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

admin2018-08-12 38

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

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

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

戈尔巴乔夫上台后，在和平共处五项原则基础上，推动苏中关系正常化，这一做法主要表明了()。

简述中、苏分歧和中、苏同盟关系破裂的原因及其影响。

以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

给定集合S={0，1，2，3，4)，以及优先关系R={0＜1，1＜4，1＜2，2＜3，2＜4，4＜0)。(1)R是偏序关系吗?(2)证明你的结论。

关于立克次体的共同特征，下列说法错误的是A．以节肢动物为传播媒介B．对多种抗生素敏感C．菌体内同时含有DNA和RNAD．大多仅引起人类致病E．以二分裂方式进行繁殖

无牙颌缓冲区需要缓冲的原因是

某患者，13岁。在生活中养成不良的吸烟习惯，父母非常恼火，心理医生建议其采取的较有效的行为治疗是

对于国际货运代理是作为代理人还是当事人的法律地位，国际上通常有强制性的法律法规规定。()

荷花对于（）相当于（）对于地瓜

Whattimedoesthewomanoftengettoherofficeeverymorning?

A、 B、 C、 C

TheMITSloanSchoolofManagementstronglybelievesthatitspurposeistogivestudentsthetoolstheywillneedtobeeffecti