首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
admin
2019-08-15
53
问题
证明:对有向图的顶点适当地编号,可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
选项
答案
此题考查的知识点是无环图的定义。根据题意,该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角线元素均为O。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)
解析
转载请注明原文地址:https://kaotiyun.com/show/ddCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
有效容量为128KB的Cache,每块16字节,8路组相联。字节地址为1234567H的单元调入该Cache,其Tag应是()。
假定一台计算机的显示存储器用DRAM芯片实现,若要求显示分辨率为1600×1200,颜色深度为24位,帧频为85Hz,显存总带宽的50%用来刷新屏幕,则需要的显存总带宽至少约为____。
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:写出图G的邻接矩阵A。
若对n阶对称矩阵A[1..n,1..n]以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B[1..n(n+1)/2]中,则在B中确定aij(i
随机试题
【背景资料】某单位工程,按照下图所示的进度计划网络图组织施工。事件一:在第75天进行的进度检查时发现:工作A已全部完成,工作B刚刚开工。建设单位要求施工单位必须采取赶工措施,保证总工期。项目部向建设单位上报了进度计划调整方案,其中调整步骤是分析进度计
综合自动化系统实现对全变电站的主要设备和输配电线路的自动监视、测量、自动控制和微机保护以及与调度通信等综合性的自动化功能,利用的技术包括电子技术、通信设备及信号处理技术和()。
下列单据中,属于原始凭证的是()。
下列属于外汇交易方式的是()
下列关于基金年度报告的说法正确的是()。
在大气成分中,主要吸收太阳紫外线的气体成分为()。
《中共中央国务院关于稳步推进农村集体产权制度改革的意见》指出,要将农村集体经营性资产以股份或者份额形式量化到本集体成员,作为其参加()的基本依据。
计算机网络最突出的优点是()。
下列关于路由器技术指标的描述中,正确的是()。
In1969twoAmericanastronauts______onthemoonandwalkedonitsrocky,dustysurface.
最新回复
(
0
)