所有节点入度全大于 0，是否就必然有环存在？

[lixia625]

[Septembers]

无背景信息，我只想说shit

[yangff]

是

[spencerqiu]

前排膜拜杨芳斐大神。

[spencerqiu]

@Septembers
这个图论问题本身题目描述已经足够了吧……

[FrankFang128]

假设没环

[lsylsy2]

所有点都有入度——无法拓扑排序——不是有向无环图

[lixia625]

@lsylsy2
”无法拓扑排序“，是因为算法本身的原因，不是太有说服力呢

[yangff]

@lixia625
不是，是必要条件，由dag的定义可直接得到（有向树+边）

[lixia625]

@yangff 就是说不一定有环喽？

[yangff]

@lixia625 我是说，无法拓扑排序，不是算法本身的原因，是从dag的定义可以直接得到的

[lixia625]

@yangff
那如何证明它不是dag

[lsylsy2]

@lixia625 首先，有入度出度的区别，说明这是一张有向图吧。
然后，“有向无环图”的性质是“可以给出拓扑排序”
拓扑排序的要求是必须有一个起始点，这个起始点入度为0；
可得你的图无法给出一个拓扑排序，所以不是有向无环图。

[lixia625]

@lsylsy2 有点感觉了 thx

[yangff]

@lixia625 有零入度点，是一张图是dag的必要条件
因为dag是有向树加向外的边。
这意味着：
有0入度点的图不一定是dag
没有0入度的图一定不是dag

一张图不是dag必有环