确定图是否单独连接

Question

我的疑问很小。如果一个图形有后边缘，它是单独连接还是不连接？背后边缘指的是从同一个根下的子节点到其祖先之一的连接。如果一个节点连接到一个高于它的节点，而不是它的祖先，那么它就是一个交叉节点。 http://en.wikipedia.org/wiki/Polytree

更新：该链接澄清单独连接的图形的概念。

Answer 1

好问题。如果图形具有后边缘，则不会阻止其单连接。但由于其他原因，它可能不是单连接的。例如，如果图形是无向的。

Answer 2

看来你正在试图与链表（与通常的含义，其中单连接和双连接的是常见的术语）的比喻。

然而，这并不是什么大不了的图形和术语连接更通常可达相关（即：有没有从节点到另一个节点的路径？）

Answer 3

如果我没有理解你问题正确，你想知道Polytree是否可以包含后沿（从节点到其祖先之一的边）。

从您链接到维基百科的文章，一个Polytree是DAG剩下的即使边缘是由无向树。如果有向图包含后沿，则意味着图中会出现一个循环（可以从其祖先到达该节点，然后使用后沿返回祖先）。因此它不再是一个DAG，更不用说树了。如果不是DAG，它不能是Polytree。所以，没有一个Polytree不能有一个后端。