Talk:Multitree

Difference to Directed Forest?

How is a multitree different from a directed forest? According to Graph (mathematics), "a directed tree is a directed graph which would be a(n undirected) tree if the directions on the edges were ignored." By analogy, a directed forest should be a directed graph which would be an undirected forest if the directions on the edges were ignored, in order to be consistent. Right now, I don't see a difference between that and a multitree, although I haven't tried to prove it.

— 78.50.211.66 (talk) 17:17, 6 September 2011 (UTC)

Example: the directed graph with four vertices a, b, c, d and four edges a→c, a→d, b→c, b→d is a multitree but is not a directed forest. Probably this article could use an illustration making this more clear.

—David Eppstein (talk) 18:12, 6 September 2011 (UTC)

To make it more clear: In a forest, each connected component is a tree. Especially, a single tree is also a forest. (A very small forest.) A multi-tree is neither necessarily a forest nor a tree. Graphically, one could depict a multi-tree as an "overlay" of trees, i.e. several trees which share the same vertices but own a different set of edges for each overlay. Stacking all overlays together (i.e. the union of edges), destroys the tree-property of the graph.

—80.246.32.33 (talk) 10:11, 16 June 2020 (UTC)

Inconsistent Definition

Also, there is a minor inconsistency in the definition itself:

"a multitree may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a [diamond-free poset]"

If I understand correctly, in the first case, what this is meant to say is that the subgraph induced by the set of nodes reachable from any node is a tree, and in the second case that the set of nodes reachable from any node together with its reachability relation forms a poset, which are two very different structures, although with the same underlying set.

— 78.50.211.66 (talk) 17:17, 6 September 2011 (UTC)

I don't understand what you want to say, especially I cannot make any sense out of your words "although with the same underlying set." Maybe this is due to your misconception that a multi-tree was equvilent to forest, which is wrong (see section above). However, I agree that the definition is inconsistent.

The condition A) "a directed acyclic graph in which the set of nodes reachable from any node form a tree" is not equivant to the condition B) "a [diamond-free poset]".

Consider the following graph A --> B --> C with an addittional edge A --> C, i.e. C can be reached from A either directly in one step or in two steps over B. This graph is obviously diamond-free, because a diamond requires four vertices, but the whole graph is onlys only made of three vertices. However, the graph is not a multi-tree. Taking A as the root, all vertices are reachable and the resulting graph is not a tree. The condition "diamond-free" is not a sufficient condition for "multi-tree". Also, the cited reference does not state so.

—80.246.32.33 (talk) 10:11, 16 June 2020 (UTC)