首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
admin
2017-01-04
27
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/RQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
我国对外开放格局的形成过程。
简述雅典民主政治的形成过程。
试析凡尔赛一华盛顿体系的实质及其对一战后国际关系的影响。
简述弭兵之会的背景、过程和结果。
1907年召开的第二国际斯图加特代表大会上,争论最激烈的问题是()。
拜占庭帝国的第二个黄金时代是在()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
随机试题
分析下列形声字的结构:闻,伽,修,旗,蛊,辫,抬,衷。
市政绩效评估方法可以分为__________、__________、__________。
《销售量下降不容忽视》属于哪种形式的标题?()
阅读下列材料并回答问题。材料1我国每亩耕地占有农机总动力只有0.16千瓦,远远低于发达国家水平……机播和机收面积均不超过20%。……在现有耕地中,2/3是中低产田,目前改造的步伐仍然比较慢。
根据《城乡规划法》的规定,建设用地规划管理的行政主体是城市、县人民政府城乡规划主管部门;该主管部门在建设用地规划管理中的主要职责不包括()。
下列明细账应该采用数量金额式的有()。
内地企业在中国香港发行股票,新申请人预期证券上市时由公众人士持有的股份的市值须至少为()万港元。无论任何时候,公众人士持有的股份须占发行人已发行股本至少()。
阅读下列材料自然界某些动物在陆地上出生,但是出生后就去海里生活,海龟就是这样。小海龟在陆地上从蛋里孵化出来,但是不久后就走向海洋。大多数的海龟生命的前半部分在遥远的海洋中度过,但是在最后会移向靠近陆地的海岸。海龟的大部分时间都在海洋里漫游,它们的
某公司年度审计期间,审计人员发现一张发票,上面有赵义、钱仁礼、孙智、李信4个签名,签名者的身份各不相同,是经办人、复核、出纳或审批领导之中的一个,且每个签名都是本人所签。询问4位相关人员,得到以下回答:赵义:“审批领导的签名不是钱仁礼。”
Youwillhearfiveshortpiecesofspeech.Foreachpiecedecidewhoistalking.Writeoneletter(A—G)nexttothenumberofth
最新回复
(
0
)