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

admin2018-08-12 47

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列不是苏俄实行战时共产主义政策原因的是()。

下列城市：①南京②厦门③天津④杭州，按其在近代历史上开放为商埠的时间先后顺序排列应该是()

科学技术革命包括三个既有联系又有区别的过程，下列不属于三个过程的是()。

罗马帝国疆域扩张到顶点是在()统治时期。

8世纪利用汉字偏旁创造日本片假名的是()。

中华人民共和国恢复在联合国合法席位的时间是()。

750年阿拔斯王朝创建时，被消灭的倭马亚王朝的王子阿卜杜勒.拉赫曼逃至西班牙，在当地贵族和柏柏尔人的支持下，建立了()。

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

快速排序最易发挥其长处的情况是()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2，…，en)；i=1：while(所剩边数＞=顶点数){从图中删去ei；若图不再连通，则恢复ei；i=

解释下列句子中加下划线的字。泣孤舟之嫠妇。

当出现下列哪种情况时，非正式群体会影响工作效率()

注射剂的浓配或采用密闭系统的稀配在无菌原料药的暴露工序

对城市历史环境的保护具有重要指导意义的两部文件是()。

护面墙与挡土墙在受力上的最大区别是()。

假设某订单订购3种商品，每种商品有10%的缺货可能性。若没有任何一种商品缺货，全部订货得以履行的概率是()。

建立、维持和发展人际关系的方法有()。

计算机处理模拟视频信号过程中首先要进行(14)。

Java编译程序将Java源程序翻译为JVM可执行代码，即______。