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

节点

大于

必然

14 replies • 2015-05-07 22:36:47 +08:00

1

Septembers

May 7, 2015 via Android

无背景信息，我只想说shit

2

yangff

May 7, 2015 via Android

是

3

spencerqiu

May 7, 2015 via iPad

前排膜拜杨芳斐大神。

4

spencerqiu

May 7, 2015 via iPad

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

5

FrankFang128

May 7, 2015 via Android

假设没环

6

lsylsy2

May 7, 2015

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

7

lixia625

OP

May 7, 2015

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

8

yangff

May 7, 2015 via Android

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

9

lixia625

OP

May 7, 2015

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

10

yangff

May 7, 2015 via Android

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

11

lixia625

OP

May 7, 2015

@yangff
那如何证明它不是dag

12

lsylsy2

May 7, 2015

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

13

lixia625

OP

May 7, 2015

@lsylsy2 有点感觉了 thx

14

yangff

May 7, 2015 via Android

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

一张图不是dag必有环