Talk:Arborescence (graph theory)

This article was nominated for merging with Tree (graph theory) on 24 July 2014. The result of the discussion was Do not merge.

Untitled

Is this really the right name? Arborescence is to Redness as Arbor is to Red. This word may be a noun, but it isn't the type of noun used to name (non-Platonic) objects. It is the kind of word to name a concept. In this case it means something like "The quality of being tree-like", which is as non-apt for naming trees as "redness" is for naming a color. 74.192.28.189 (talk) 02:24, 12 February 2013 (UTC)[reply]

Yes, it really is the right name.

https://www.cnrtl.fr/definition/arborescence

ARBORESCENCE, subst. fém.

A.− BOT. Qualité, état d'un végétal arborescent.

− P. anal.

1. Dessin naturel ou non en forme d'arbre Quantum Knot (talk) 14:57, 5 June 2024 (UTC)[reply]

Untitled2

sorry i can't get how is it defferent from a plain tree. could someone elaborate? — Preceding unsigned comment added by 192.127.94.7 (talk)

It's a directed graph; trees are undirected. Moreover, it's not just any graph whose undirected graph is a tree. --Robin (talk) 13:39, 14 June 2010 (UTC)[reply]

It's important to realise this is the terminology of graph theory not computer science. In comp sci and software engineering, when we say tree, we nearly always mean a DAG with a root. Perhaps the article could contain a hint about that in the introduction. I went around 5 wikipedia pages to satisfy this question myself. 194.39.218.19 (talk) 14:50, 26 August 2024 (UTC)[reply]

Definition is Incorrect

The definition allows for example a directed graph which is a directed cycle, together with a single edge from a root vertex r to the cycle. There is then a unique path from r to every vertex in the graph, yet this isn't an arborescence. I don't know of the cleanest way to `fix' this, perhaps ask that every vertex apart from the root has a unique in-neighbour. — Preceding unsigned comment added by 134.100.221.55 (talk) 13:21, 6 March 2019 (UTC)[reply]

No, there isn't a unique path from the root to any vertex in your example. Choose any path from r to some vertex v on the cycle. Then append the cycle. That's a new, different path from the root to v. Quantum Knot (talk) 14:59, 5 June 2024 (UTC)[reply]

The example given is not a counterexample, but they are still right, the definition is false, there are counterexamples.ZMBerber (talk) 22:38, 28 June 2024 (UTC)[reply]

A working counterexample is to just take a directed cycle, and choose any node as the root. There is a unique path from every node to the root, but this is not an arborescence. If we replace "path" by "trail" in the definition, and consider empty paths at a node as paths as well (which is true in most definitions), then this is not an arborescence. Also, if the node with this property has to be unique, then this is also not a counterexample. But there are worse counterexamples, as I will give below.

Another counterexample: We take a directed cycle, and we add another node outside the cycle, and add an outgoing edge from one of the nodes of the cycle to the new node, and make that node the root. Then this root node is the unique node with the property of having a unique path/trail from every node to it, but this is still not an arborescence.ZMBerber (talk) 22:38, 28 June 2024 (UTC)[reply]

I was not completely right, the detail about having "trail" is wrong. It might actually be true that both "walk" and "trail" both work for the definition of an arborescence. ZMBerber (talk) 17:53, 18 July 2024 (UTC)[reply]

Actually, I think replacing the word `path' with the word `walk' in the definition should be sufficient.

I agree. I read the definition and came to the same conclusion, and came up with the same fix ("walk" instead of "path"), actually.ZMBerber (talk) 22:38, 28 June 2024 (UTC)[reply]

Definition detail about the root being distinguished

The definition says that an arborescence has a "distinguished" node with certain properties, which is the root node. In my opinion, the wording "distinguished" is not well chosen, it is either wrong or ambiguous. For me, saying "distinguished" means that the root node is part of the datum of an arborescence. But this information is redundant, since there would be a unique such node. The existence of such a node is an intrinsic property of a directed graph, and this existence defines an arborescence. Perhaps this is written like this because rooted trees (which in some sense have a one-to-one correspondence to arborescences) have a distinguished node, the root, as part of their datum.ZMBerber (talk) 22:38, 28 June 2024 (UTC)[reply]