首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全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
)
