证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。

admin2019-08-15 61

问题证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。

选项

答案此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为O。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(A[i][j]=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)

解析

转载请注明原文地址:https://www.kaotiyun.com/show/ddCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。

计算机408

学硕统考专业

南宋理学家()认为一切封建秩序和伦理纲常都是人“本心”所固有的。而不是来自朱熹等人所说的“天理”。他的这一学说被称为“心学”。

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。

不属于核苷类的抗病毒药有

Inanoldtownlivedamerchant.Heearnedhugeprofitsbyfairmeansandfoul.Withmoreprofitsflowingin,hebecamemoreand

A、视神经炎B、二重感染C、诱发感染D、金鸡钠反应E、肺纤维化四环素的不良反应是

由块状生石灰熟化而成的石灰膏，一般应在储灰坑中陈伏()左右。

《秋千》、《浴女》等绘画作品的作者，是18世纪法国罗可可画家________。

市场经济通过市场机制把社会资源配置到经济效益好的部门和企业，以实现资源的优化配置。（）

强调自上而下知识和自下而上知识的区别的建构主义理论是()。

Thevideoindustryisdevelopingsorapidlythatalmostanything______iswrittenwillhavebeenoutofdatebythetimeitispr

Theroleofandtreatmentofthehousewife,whichisreallythemajorboneofcontentioninsocialsecurityreform,has,ofcour