문제 설명
각 노드에 최대 하나의 아웃바운드 에지가 있는 완전 연결 방향 그래프를 무엇이라고 합니까? (What do you call a fully connected directed graph where each node has at most one outbound edge?)
각 노드가 최대 하나의 인바운드 에지를 갖는 완전 연결 방향 그래프는 트리입니다. 각 노드에 최대 단일 아웃바운드 간선이 있는 완전 연결 방향 그래프에 이름이 있습니까? 안티 트리?!
참조 솔루션
방법 1:
I believe that this does indeed have a name ‑ it is a directed pseudotree.
From the 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.
Hence, we can call the graph you describe above a directed pseudoforest. You also note that the graph is connected. From the same page:
A pseudotree is a connected pseudoforest.
Hence, the term directed pseudotree.
Here is the proper definition of an undirected pseudoforest, for your information, from 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."
(by Christopher King、Luna)