首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
admin
2019-08-15
69
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为O。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/ddCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
洋务运动时期,首批赴欧海军留学生派出的时间是()。
在一个双链表中,在*p结点之前插入*q结点的操作是()。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
四位运算器框图如下图所示,ALU为算术逻辑单元,A和B为三选一多路开关,预先已通过多路开关A的SW门向寄存器R1,R2送入数据如下:R1=0101,R2=1010。寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下:(1)R1
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
下列关于图的叙述中,正确的是____。I.回路是简单路径Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间Ⅲ.若有向图中存在拓扑序列,则该图不存在回路
已知AOE网中顶点v1,v2,v3,……v7分别表示7个时间,有向线段a1,a2,a3,……a10。分别表示10个活动,线段旁的数值表示每个活动花费的天数,如下图所示。请填写下面两个表格,并用顶点序列表示出关键路径,给出关键活动。
下列叙述正确的个数是()。1)向二排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B一树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
随机试题
艾滋病患者最先出现的继发性感染的常是
《证治准绳》对痹证膝关节肿大者称为《格致余论》称痹证为
A黄色泡沫状脓性B血性C黄色水样D奶油状E豆腐渣样滴虫样阴道炎患者,阴道分泌物可呈
梅毒气血两虚宜选用何法治疗梅毒肝经湿热宜选用何法治疗
格式条款合同中,提供格式条款的一方当事人应()。
下列不属于商业银行获得收益的主要业务活动的是()。
芥子气(一种毒气,是战争期间作为一种战争化学武器被引入的)
Thereareupsettingparallelstoday,asscientistsinonewaveafteranothertrytoawakenustothegrowingthreatofglobalwa
MemoTo:AlltheStaffFrom:Mr.Mendels,thePersonnelManagerDate:Dec15,2008Ref:JM/15/12/08Subject:Thegrantingofann
89.______(由于气温急剧下降),wecouldn’tgoonwiththeexperiment.
最新回复
(
0
)