首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
admin
2018-08-12
71
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/KwRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
近代中国各派军阀的共同点有()①始终打着维护共和制度的旗号②利用中央政权排斥异己③都试图夺取中央政权④以帝国主义列强为靠山
第二次工业革命引起的生产关系方面最突出的变化是()。
下列对1918年德国十一月革命说法不正确的是()。
判断英国工业革命基本完成的主要依据是()
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
随机试题
简述收入确认应符合的条件。
高钾血症的心电图表现不应为
哪一项不属于水肿与鼓胀的鉴别要点
从生物药剂学角度,食物对药物的口服吸收有非常重要的影响,如饭后口服对消化道有刺激性的药物,可相应减轻对胃肠道的不良反应,延缓胃排空,使药物在胃中较为充分地吸收。若空腹服用药物,则对胃肠道刺激较强,胃排空速率快,药物快速进人十二指肠和小肠。根据生物节律,
根据《药品经营质量管理规范实施细则》,关于药品经营企业人员要求的说法,正确的是()。
一个孤立的点电荷周围的电场在空间呈辐射状分布,当点电荷为正电荷时,电场()。
徽州地区有“徽派三雕”,又有“徽派四雕”的说法,“徽派四雕”是指()。
商场的自动扶梯以匀速由下往上行驶,两个孩子嫌扶梯走得太慢,于是在行驶的扶梯上,男孩每秒钟向上走2个梯级,女孩每2秒向上走3个梯级。结果男孩用40秒钟到达,女孩用50秒钟到达。则当该扶梯静止时,可看到的扶梯级有:
一棵二叉树共有25个节点,其中5各是叶子节点,则度为1的节点数为( )。
TheUnitedStatesisacountrymadeupofmanydifferentraces.Usuallytheyaremixedtogetherandcan’tbetoldfromoneanoth
最新回复
(
0
)