首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
admin
2019-01-16
45
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/AYRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
“两个凡是”
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
描述滑动窗口机制及其作用。比较停止一等待协议,多帧滑动窗口和后退N帧协议,多帧滑动窗口与选择重传协议的区别。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
某一个计算机系统采用虚拟页式存储管理方式,当前在处理机上执行的某一个进程的页表如下所示,所有的数字均为十进制,每一项的起始编号是0,并且所有的地址均按字节计址,每页的大小为1024字节。(1)计算下列逻辑地址转换为物理地址,并说明为什么
若无向图G=(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是____。
下图是某存储芯片的引脚图,请回答:(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根,存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)
CISC与RISC的区别表现在()。
随机试题
面的烹调方法为煮、烙、蒸、炸等,_______的营养素损失较少。
基督教在中国设立的最大出版机构广学会发行的报刊是()
上肢不能外展是由于拇指不能对掌是由于
在措施项目清单编制中,通常与两个以上工序相关的措施项目是()。
1.背景:某市新建小区雨水管线工程,直径1500mm,长1320m,管顶覆土约4.8m,采用钢筋混凝土管,水泥砂浆抹带接口,90°混凝土基础;施工范围土质为硬塑的轻粉质黏土,无须降低地下水。由于场地狭小,无法采用机械开挖,项目部决定采用人工开挖:
江苏环球国际贸易有限公司(320196××××)受南京××大学(3201990000)委托向海关申报进口设备一批,装载货物的运输工具于2009年3月29日申报进境。2009年4月2日江苏环球国际贸易有限公司持入境货物通关单(编号:3201001091542
长江股份有限公司(本题下称长江公司)为增值税一般纳税人,适用的增值税税率为17%,适用的所得税税率为25%,所得税采用债务法核算。长江公司2010年度所得税汇算清缴于2011年4月30日完成,在此之前发生的2010年度纳税调整事项,均可进行纳税调整
将下列句子按语序先后排列,最连贯的一项是()。①直到1757年,牛顿的万有引力学说已经确立很久②1882年,教皇才被迫承认地动学说③科学终于以伟大的不可压抑的力量战胜了神权④1616年,教皇宣布《天体运行》列入禁书⑤地动学说成了天经地义,
Accordingtothepassage,destructioncausedbyhighwavesoccurs______.Accordingtothepassage,whichofthefollowingisT
Itisgenerallyacknowledgedthatyoungpeoplefrompoorersocioeconomicbackgroundstendtodolesswellinoureducationsyste
最新回复
(
0
)