首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
admin
2019-01-16
27
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全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应该满足下面三个条件:
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
描述滑动窗口机制及其作用。比较停止一等待协议,多帧滑动窗口和后退N帧协议,多帧滑动窗口与选择重传协议的区别。
下图是某存储芯片的引脚图,请回答:(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根,存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)
随机试题
经过CDP-甘油二酯途径可合成
A.碱基顺序B.双螺旋C.超螺旋D.核小体E.核糖体真核生物DNA的三级结构是
确定正中关系位方法中不正确的是
甲亢危象时应使用的药物是
王某承包了20亩鱼塘。某日,王某发现鱼塘里的鱼大量死亡,王某认为鱼的死亡是因为附近的腾达化工厂排污引起,遂起诉腾达化工厂请求赔偿。腾达化工厂辩称,根本没有向王某的鱼塘进行排污。关于化工厂是否向鱼塘排污的事实举证责任,下列哪一选项是正确的?(2008年试卷三
房屋买卖市场的特点主要有()。
心理学研究的发展性原则
若三次方程ax3+bx2+cx+d=0的三个不同实根x1,x2,x3满足x1+x2+x3=0,x1x2x3=0,则下列关系式中恒成立的是().
“睹物思人”、“触景生情”,这种反映形式属于
A、Itmakesourlifemoreinteresting.B、Itenablesustoacquirefirst-handknowledge.C、Ithelpsdevelopourpersonalities.D、I
最新回复
(
0
)