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

admin2019-01-16 35

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

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

解放军渡江战役中横渡长江的东西两个攻击点是()。

“瓜步之战”发生在下列哪两个政权之间?()

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

下图是某存储芯片的引脚图，请回答：(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根，存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)

某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。集中式总线判优控制与分布式总线判优控制的区别是什么?

CISC与RISC的区别表现在()。

()应急处理程序的基本原则是疏散所有人员，最大程度减少人员伤亡。

“()”是将煮好的茶水趁热倒入白酒中，是纳西族人治疗感冒的秘方。

试述对住院儿童心理反应的护理。

有3个并发进程：R、E、P，R将键盘输入的一个整数读入缓冲区B1，E将B1中的数据取出进行处理，处理后存入缓冲区B2中。最后由P负责将B2中的数据打印输出。用PV操作写出管理3个进程的并发程序。(注：B1和B2均只能存放一个数据)

Ihopethingswouldgetbetter,butasitistheyaregettingworse.

不属于常用的血清学诊断试验的是

A．《药品生产许可证》B．《药品经营许可证》C．《医疗机构制剂许可证》D．《医疗机构执业许可证》根据《中华人民共和国药品管理法》药品批发企业在购销药品中无真实、完整的购销记录且情节严重的，应吊销其()。

()是显性课程的主要特征，是区分正规课程和非正规课程的主要标志。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。