algorithm - 每个节点最多有一个出站边缘的完全连接的有向图叫什么？

Question

一个完全连接的有向图，其中每个节点至多有一个入站边是一棵树。每个节点最多只有一个出站边的完全连接的有向图是否有名称？反树？!

Answer 1

我相信这确实有一个名字——它是一棵有向伪树。

来自Wikipedia article on pseudoforests :

A directed pseudoforest is a directed graph in which each vertex has at most one outgoing edge; that is, it has outdegree at most one. A directed 1-forest – most commonly called a functional graph, sometimes maximal directed pseudoforest – is a directed graph in which each vertex has outdegree exactly one.[8] If D is a directed pseudoforest, the undirected graph formed by removing the direction from each edge of D is an undirected pseudoforest.

因此，我们可以将您在上面描述的图称为有向伪森林。您还注意到该图是连通的。来自同一页面:

A pseudotree is a connected pseudoforest.

因此，术语有向伪树。

这是无向伪森林的正确定义，供您引用，来自 Wolfram Alpha :

A pseudoforest is an undirected graph in which every connected component contains at most one graph cycle. A pseudotree is therefore a connected pseudoforest and a forest (i.e., not-necessarily-connected acyclic graph) is a trivial pseudoforest.

Some care is needed when encountering pseudoforests as some authors use the term to mean "a pseudoforest that is not a forest."