来自蔡菲的问题
若一个有向图的邻接矩阵中主对角线一下的元素均为零请问该图是否为DAG图?
若一个有向图的邻接矩阵中主对角线一下的元素均为零请问该图是否为DAG图?
当然是.
假设不是一个DAG图,不妨令邻接矩阵的节点ID从小到大有序.
因为不是DAG图,必定存在环.
环经过节点的ID不可能单调有序,一定存在某个边,节点ID由小指向大,则该边出现在主对角线以下,矛盾.
大家都在问
最新问答
海冰含盐量接近淡水，...2020-12-30
三峡游山峰一下子就被...2020-12-30
二元一次方程简单的配...2020-12-30
【偏裨将校是什么意思...2020-12-30
如图秒表的读数为__...2020-12-30
____abigfi...2020-12-30
【知道本金和税后利息...2020-12-30
《一百条裙子》读后感...2020-12-30
利用矩阵解二元一次方...2020-12-30
【英语中的peasa...2020-12-30