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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3487 天前的主题，其中的信息可能已经有所发展或是发生改变。

节点

大于

必然

14 条回复 • 2015-05-07 22:36:47 +08:00

Septembers

2015-05-07 20:48:54 +08:00 via Android

无背景信息，我只想说shit

yangff

2015-05-07 20:50:06 +08:00 via Android

是

spencerqiu

2015-05-07 20:58:18 +08:00 via iPad

前排膜拜杨芳斐大神。

spencerqiu

2015-05-07 20:59:44 +08:00 via iPad

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

FrankFang128

2015-05-07 21:07:54 +08:00 via Android

假设没环

lsylsy2

2015-05-07 21:26:15 +08:00

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

lixia625

2015-05-07 21:38:01 +08:00

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

yangff

2015-05-07 21:46:01 +08:00 via Android

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

lixia625

2015-05-07 21:48:37 +08:00

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

yangff

2015-05-07 21:54:06 +08:00 via Android

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

lixia625

2015-05-07 22:03:35 +08:00

@yangff
那如何证明它不是dag

lsylsy2

2015-05-07 22:05:31 +08:00

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

lixia625

2015-05-07 22:08:53 +08:00

@lsylsy2 有点感觉了 thx

yangff

2015-05-07 22:36:47 +08:00 via Android

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

一张图不是dag必有环