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

admin2018-08-12 35

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

《马可波罗行纪》中载：“此汗八里大城之周围，约有城市二百，位置远近不等，每城皆有商人来此买卖货物，盖此城为商业繁荣之城也。”“此城”指的是()。

下面有关兵制的内容，与唐玄宗有关的是()

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

下列对1918年德国十一月革命说法不正确的是()。

下列不是唐玄宗组织编撰的是()。

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

人的价值在于自由，它是通过个人的“自由选择”实现的，萨特这种观点的错误()

居处恭，执事敬，与人忠。

阳和汤的功用是

患者，男，44岁。右胸车祸伤2小时，右胸痛，呼吸困难，发绀。查体：右前胸未见反常呼吸运动，胸部挤压试验阳性，右肺呼吸音降低。胸片显示右侧第8～10肋骨后端骨折。不恰当的处理是

【2012年第101题】《建筑抗震设计规范》中，横墙较少的多层砌体房屋是指：

可行性研究阶段的分析对策研究是整个项目风险管理的重要组成部分，对策研究的基本要求的说法错误的是()。

下列常用的概念不属于建构主义理论的是()。

根据以下资料，回答116—120题2008年全年各类自然灾害造成直接经济损失11752亿元，比上年增加4.0倍。全年农作物受灾面积3999万公顷，下降18.4%。其中，绝收403万公顷，下降29.8%。全年共发生森林火灾1.3万起，上升45.2%。全年因

Payandproductivity,itisgenerallyassumed,shouldberelated.Buttherelationshipseemstoweaken【C1】______peoplegetolder