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

节点

大于

必然

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

Septembers

May 7, 2015 via Android

1

无背景信息，我只想说shit

yangff

May 7, 2015 via Android

2

是

spencerqiu

May 7, 2015 via iPad

3

前排膜拜杨芳斐大神。

spencerqiu

May 7, 2015 via iPad

4

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

FrankFang128

May 7, 2015 via Android

5

假设没环

lsylsy2

May 7, 2015

6

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

lixia625

OP

May 7, 2015

7

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

yangff

May 7, 2015 via Android

8

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

lixia625

OP

May 7, 2015

9

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

yangff

May 7, 2015 via Android

10

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

lixia625

OP

May 7, 2015

11

@yangff
那如何证明它不是dag

lsylsy2

May 7, 2015

12

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

lixia625

OP

May 7, 2015

13

@lsylsy2 有点感觉了 thx

yangff

May 7, 2015 via Android

14

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

一张图不是dag必有环