首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
admin
2019-08-15
76
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为O。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/ddCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
下面关于进程的叙述中,正确的是()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
下图是三个计算机局域网A,B和C,分别包含10台,8台和5台计算机,通过路由器互联,并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LANA和LANB公用一个C类IP地址
以下说法中,错误的是()。
在下面的应用中,通常使用栈的是()。 Ⅰ递归调用Ⅱ括号匹配Ⅲ表达式求值
随机试题
4个月婴儿,足月顺产,出生体重2000g/L,单纯母乳喂养,未添加辅食。体查:皮肤、巩膜无黄染,前囟平软,唇较苍白,心、肺无异常,肝右肋下3cm,脾左肋下2cm,Hb80g/L,WBC8.5×109/L,N0.38,L0.65,M0.0
下列属于鲁迅杂文集的是()
因履行集体合同发生的争议处理程序。
口服敌百虫中毒时不能用来洗胃的溶液是
停车场的设置应符合防火要求,停车场的汽车宜分组停放,每组停车不宜超过多少辆?[2000-15]
关于招标控制价应用中应注意的主要问题,下列表述不正确的是()。
肌肉长度发生变化,而张力不变的肌肉收缩为__________收缩。
材料1世界经济生活中,全球化趋势加速,各国相互依赖空前密切;于是在整个国际关系领域内,国际政治关系带上更浓的经济色彩,怀有更多的经济目标和经济动力,而国际经济关系又不时渗入政治因素或转换成政治关系。从一个国家的角度看,经济因素往往成了国家对外政治关系的主
一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈,然后再依次出栈,则元素出栈的顺序是()。
在窗体中有命令按钮Command1和文本框Text1,按钮的事件代码如下:PublicXAsIntegerPrivateSubCommand1_Click()x=10Calls1ralls2
最新回复
(
0
)