首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
admin
2018-08-12
68
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/KwRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列不是苏俄实行战时共产主义政策原因的是()。
在晚清地方势力崛起的过程中,属于淮系的有()
绿林军领袖为了大影响,拥立汉宗室()为皇帝,恢复汉的国号,以公元23年为更始元年。
戈尔巴乔夫上台后,在和平共处五项原则基础上,推动苏中关系正常化,这一做法主要表明了()。
“文化大革命”结束后,在纠正“文化大革命”错误的过程中,整个过程受到()的严重阻碍。
年鉴学派开创了总体史研究方法,其代表人物马克·布洛赫研究中世纪的代表作是()
美国历史上第一个具有宪法性质的文件是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
患者女性,48岁,主诉刷牙出血1月余,伴有口臭,口腔检查:上颌前牙唇侧,下颌前牙舌侧牙石多,牙龈充血,水肿,轻探极易出血,下前牙排列拥挤。检查结果:①龈沟底附着在釉牙骨质界根方;②牙周袋深度3.5mm;③X线示牙槽骨吸收;
实验室建筑与设施应符合
[2007年第4题]若有=0,则当x→a时,f(x)不一定是()。
某高层建筑,设计建筑高度为68.0m,总建筑面积为91200m2。标准层的建筑面积为2176m2,每层划分为1个防火分区:一至二层为上、下连通的大堂,三层设置会议室和多功能厅,四层以上用于办公;建筑的耐火等级设计为二级,其楼板、梁和柱的耐火极限分别为1
普通合伙企业的合伙人之间约定的关于合伙企业亏损分担比例,对债权人没有约束力。()
【2014.山西太原】罗杰斯的“以学生为本”“让学生自发学习”“排除对学习者自身的威胁”的教学原则属于()。
专家们认为,传统的教学方式必须______,才能适应当前形势发展的需要。填入划横线部分最恰当的一项是:
在不同历史阶段,随着社会主要矛盾的变化,集中反对的主要敌人有所不同。在国共合作的大革命时期,革命的主要对象是()
设”个随机变量X1,X2,…,Xn独立同分布,DX1=σ2,,则
下面关于数据访问页叙述错误的是
最新回复
(
0
)