早教吧作业答案频道 -->其他-->
若一个有向图的邻接矩阵中主对角线一下的元素均为零请问该图是否为DAG图?
题目详情
若一个有向图的邻接矩阵中 主对角线一下的元素均为零 请问该图是否为DAG图?
▼优质解答
答案和解析
当然是.
假设不是一个DAG图,不妨令邻接矩阵的节点ID从小到大有序.
因为不是DAG图,必定存在环.
环经过节点的ID不可能单调有序,一定存在某个边,节点ID由小指向大,则该边出现在主对角线以下,矛盾.
假设不是一个DAG图,不妨令邻接矩阵的节点ID从小到大有序.
因为不是DAG图,必定存在环.
环经过节点的ID不可能单调有序,一定存在某个边,节点ID由小指向大,则该边出现在主对角线以下,矛盾.
看了 若一个有向图的邻接矩阵中主对...的网友还看了以下：
三角函数平移是否有这样一个规律（不用算,答好一定加分）做了一些题目,如为了得到函数y=sin(2x 2020-06-06 …
建筑工人砌墙时，常利用铅垂线来检查墙砌得是否竖直，其原因是，如图甲一堵南北走向的墙上，所挂铅垂线如 2020-06-19 …
判断一个图是否有环无向图有向图 2020-06-22 …
Solidworks能否在一个装配体内制作几个视图的爆炸图!如题,比如说,一个装配体A我做好了一个 2020-06-27 …
画统计图时,横轴的箭头方向能否朝左(也就是正方向在两坐标轴交点以左),纵轴的箭头方向能否向下(也就 2020-07-30 …
作用在球体上的力我知道不一定指向圆心,但请问怎样判断是否指向圆心呢?例如：有一个球放在一个木块旁, 2020-07-30 …
关于数据结构的题1.有n个顶点的有向连通图最多有条边,最少有条边.2.具有n个顶点的完全无向图有条 2020-08-01 …
求算法：欧拉路Description定义：图G的欧拉回路是包含图G所有边的一个简单回路,而欧拉路径 2020-08-01 …
已知将二次函数Y=-X平方的图像向上平移四个单位,再向左平移3个单位得到一新的二次函数,其图像与X轴 2020-11-01 …
设计算法判断一个无向图G是否为树。若是，输出“Yes！”；否则输出“No！”。输入格式：第1行是空格 2020-11-07 …