algorithm - 如何确定图是否为单连通图？

Question

如果一个图有后边，它是单连通的还是不连通的？后边缘是指从子节点到其祖先之一的连接，在同一个根下。如果一个节点连接到比它更高的节点，但不是它的祖先，那么它就是一个交叉节点。

http://en.wikipedia.org/wiki/Polytree

此链接阐明了单连通图的概念。

Answer 1

如果一个图有后边，那并不妨碍它被单连接。但由于其他原因，它可能不是单独连接的。例如，如果图是无向的。

Answer 2

您似乎正在尝试与链表进行类比（其中单连接和双连接是具有通常含义的常用术语）。

然而，这对于图来说并不是什么大问题，并且术语连接性通常与可达性相关联（即：是否有从一个节点到另一个节点的路径？）

Answer 3

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

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