首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
admin
2019-08-15
46
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为O。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/ddCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中共八届九中全会提出的恢复和调整国民经济的方针是()。
《中国国民党改组宣言》发表的时间是()。
洋务运动时期,首批赴欧海军留学生派出的时间是()。
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题西周建立之后,派遣同姓贵族和异姓贵族及归顺的异族首领到各地区,建立国家以藩屏护卫周室,分别分在卫、鲁、唐、燕的贵族是()
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
已知小写英文字母“a”的ASCⅡ码值为61H,现字母“g”被存放在某个存储单元中,若采用偶校验(假设最高位作为校验位),则该存储单元中存放的十六进制数是()。
随机试题
膈肌的正常变异不包括
关于宪法实施的保障,下列哪一选项是不正确的?
甲公司拟在沿海地区选址建厂,主要生产客运汽车。乙咨询单位接受甲公司的委托,开展项目厂址比选。经过收集有关资料,乙咨询单位认为项目选址应从建设条件和建设费用等方面综合考虑,并确定了两个厂址选择方案,现给出了4个评价厂址方案的指标:交通运输、基础设施、投资费用
不可抗力是指当事人在订立合同时不能预见,对其发生和后果不能避免并不能克服的()。
认为领导者具有某些固定特质且这些特质是与生俱来的观点出自()。
甲签发一张票面金额为2万元的转账支票给乙,乙将该支票背书转让给丙,丙将票面金额变造为5万元后背书转让给丁,丁又背书转让给戊。下列关于票据责任承担的表述中,正确的是()。
人民警察的(),是指人民警察在依法履行职务活动中所遵循的道德原则和道德规范。
简述管理者的角色。
Lastweek,Ireadastoryabouta34-year-oldBritishwomanwhoisextremelyafraidofmetalforks.She’sbeenusingplasticone
《凡尔赛和约》
最新回复
(
0
)