首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
admin
2019-01-16
59
问题
证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(A[i][j]=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/AYRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
詹天佑自主设计修建了中国第一条铁路是在()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
(1)根据无类IP地址的规则，每个网段中有两个地址是不分配的：主机号全0表示网络地址，主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2，即254台。该网络要划分为两个子网，每个子网要120台主机，因此主机位数X应该满足下面三个条件：
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。
支持多道程序的操作系统，区别于其他操作系统的主要特征为()。
某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1
以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条
对于下图G，按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示；(2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
下图是某存储芯片的引脚图，请回答：(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根，存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)
随机试题
调查取证应当制作笔录，由行政执法人员、当事人或者其代理人、见证人签字；当事人或者其代理人、见证人不签字的，不具有证据效力。（）
Therewasabigpileofbricksonthetopofatallbuildingandamanhadtobringthemdowntotheground.Hehadalongrope
女性，30岁，在颈丛麻醉下施行甲状腺腺瘤切除术，手术顺利。术后病人出现饮水呛咳症状，最可能的原因是
通讯系统
下列方法中，属于将生产成本在完工产品与在产品之间进行分配的分配方法是()。
复式记账法是对每一笔经济业务都必须用相等的金额在两个或者两个以上账户中同时登记，其登记的账户是()。
2019年5月1日22时许，休假的民警小李在街边散步，突然听到一妇女大喊救命，发现一男子冉某和一妇女陈某因电动自行车碰撞而引起纠纷，冉某将陈某按在地上，正用车锁猛击其头部。小李拨打110报警请求支援后，立即上前制止冉某的行为。小李在制止冉某犯罪过程中，
下列说法正确的是()。
TheterrorismmighthaveplantedabombontheplaneinAthens,setto______whenitarrivedinNewYork.
A、Searchforsimilarfossilselsewhere.B、AsktheuniversitytorewardJude.C、Conductamoredetailedsearch.D、Seekadditional
最新回复
(
0
)
