无环图和树有什么区别?

  数学 离散数学    浏览次数:917        分享
0

没有专业学过离散数学,想请教一下无环图和树有什么区别?树也是没有环的,两者是不是就完全等价了。

 

rtrip   2022-04-06 21:21



   2个回答 
4

无环图是就是没有环的图。

如果无环图是联通的,那么就是树(tree);如果无环图是不连通的,那么就是多棵树,等价于森林(forest)

下图的例子是有环图(cyclic graph)和一个联通的无环图(acyclic graph)


DAG和AG不是同一个概念。DAG是指图里的边都是有方向的无环图。有向树(polytree)是DAG的一种。

SofaSofa数据科学社区DS面试题库 DS面经

卡里昂   2022-04-08 15:57

0

举个例子,你应该就明白了:


SofaSofa数据科学社区DS面试题库 DS面经

eleve11   2022-04-08 11:08

例子是有向图和有向树 - 卡里昂   2022-04-08 16:09


  相关讨论

离散数学中偏序是什么意思?

python里如何判断一个集合是另一个集合的子集?

关于边的个数的图论问题

python求笛卡尔积

python中求两个集合的交集?

python中计算二项式系数?

为什么图的拉普拉斯矩阵的最小特征值一定是0?

轮流射击先中枪的概率题

如何通俗地解释中餐馆过程(Chinese restaurant process)?

图里的强连通成分是什么意思?

  随便看看

deep learning中的pooling是什么意思?

如何在numpy array尾部增加一行

Data Application Lab怎么样?

怎么理解推荐系统中的NDCG?

序列的autocorrelation(自相关系数)的计算公式