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

admin2017-01-04 33

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/f6fjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

中共十一届三中全会后对外开放开始起步，1980年中央决定设立()。

夏王朝建立后，将其领土划分为九州，派九牧进行治理，在九州范围内根据土地的肥沃程度缴纳贡赋，称为()。

1824～1828年分别用不同的无机物通过不同的途径合成了同一种有机物——尿素，证明了化学定律对有机物和无机物是同样适用的科学家是()。

詹天佑自主设计修建了中国第一条铁路是在()。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

1217年，英格兰的《森林宪章》允许平民百姓在王室森林中放牧牲畜、挖掘水渠并从事其他农业活动。颁布该宪章的主要目的在于()

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

某主机的MAC地址为00．15．C5．C1．5E．28，IP地址为10．2．128．100(私有地址)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。

心绞痛疼痛发作时的典型心电图表现是

患者，女性，结婚4年未孕，形体肥胖，月经40～60天一行，面色白，头晕心悸，胸闷。苔白腻，脉滑。治宜

牙齿松动与下述哪项因素关系不大

从适用性、耐久性和经济性等方面综合考虑。下列哪一种屋面做法最适宜我国北方地区居住建筑平屋顶?

上海证券账户当日开立，（）日生效。

某企业生产某品种产品，设计年产量为6000件，每件产品的销售价格为50元，企业每年固定性开支为66000元，每件产品变动成本为28元，则该项目的生产负荷率为()。

已知求可逆矩阵P，化A为标准形A，并写出对角矩阵A．

创建一个顶层表单，表单的控件名和文件名均为myform。将myform表单设置为模式表单，并将其标题设置为“表单操作”。表单启动后自动居中。