首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
admin
2019-01-16
47
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/AYRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
雍正帝为了证明清朝统治的合理性以及自己即位的合法性,颁布了()。
下列哪两个国家是第二次工业革命的发源地和“中心”?
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。集中式总线判优控制与分布式总线判优控制的区别是什么?
下图是某存储芯片的引脚图,请回答:(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根,存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)
随机试题
计日工是指在工程实施过程中,业主有一些临时l生的或新增加的项目需要按计日(或计量)使用人工和()所需的费用。
组织环境的构成有哪些?
患者女,45岁,左眼视力下降1年。Vod0.8,Tod15mmHg,Vos0.3,Tos30mmHg,右眼眼前后段正常。左眼无充血,KP(+),灰褐色,前房轴深4C.T.,房水闪辉(±),虹膜蛇皮样,晶状体轻度混浊,C/D0.8。正确的诊断是
根据下列哪项检查可确诊肺动脉口狭窄
深层搅拌桩成墙施工顺序为()。
钻孔灌注桩施工时,造成钻孔垂直度不符合规范要求的主要原因有()。
预应力筋张拉或放张时,混凝土强度应符合设计要求,当设计无具体要求时,至少不应低于设计混凝土立方体抗压强度标准值的()%。
职工参与企业民主管理的形式包括()。
论述过渡时期总路线反映了中国由新民主主义向社会主义转变的历史必然性。
Thegreatrecessionmaybeover,butthiseraofhighjoblessnessisprobablybeginning.Beforeitends,itwilllikelychanget
最新回复
(
0
)