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

2015 年 5 月 7 日
 lixia625
3231 次点击
所在节点    问与答
14 条回复
Septembers
2015 年 5 月 7 日
无背景信息,我只想说shit
yangff
2015 年 5 月 7 日
是
spencerqiu
2015 年 5 月 7 日
前排膜拜杨芳斐大神。
spencerqiu
2015 年 5 月 7 日
@Septembers
这个图论问题本身题目描述已经足够了吧……
FrankFang128
2015 年 5 月 7 日
假设没环
lsylsy2
2015 年 5 月 7 日
所有点都有入度——无法拓扑排序——不是有向无环图
lixia625
2015 年 5 月 7 日
@lsylsy2
”无法拓扑排序“,是因为算法本身的原因,不是太有说服力呢
yangff
2015 年 5 月 7 日
@lixia625
不是,是必要条件,由dag的定义可直接得到(有向树+边)
lixia625
2015 年 5 月 7 日
@yangff 就是说不一定有环喽?
yangff
2015 年 5 月 7 日
@lixia625 我是说,无法拓扑排序,不是算法本身的原因,是从dag的定义可以直接得到的
lixia625
2015 年 5 月 7 日
@yangff
那如何证明它不是dag
lsylsy2
2015 年 5 月 7 日
@lixia625 首先,有入度出度的区别,说明这是一张有向图吧。
然后,“有向无环图”的性质是“可以给出拓扑排序”
拓扑排序的要求是必须有一个起始点,这个起始点入度为0;
可得你的图无法给出一个拓扑排序,所以不是有向无环图。
lixia625
2015 年 5 月 7 日
@lsylsy2 有点感觉了 thx
yangff
2015 年 5 月 7 日
@lixia625 有零入度点,是一张图是dag的必要条件
因为dag是有向树加向外的边。
这意味着:
有0入度点的图不一定是dag
没有0入度的图一定不是dag

一张图不是dag必有环

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/189291

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX