Talk:Arborescence (graph theory)
This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
This article was nominated for merging with Tree (graph theory) on 24 July 2014. The result of the discussion was Do not merge. |
Untitled[edit]
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)
- 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)
Untitled2[edit]
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)
Definition is Incorrect[edit]
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)
- 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)
Actually, I think replacing the word `path' with the word `walk' in the definition should be sufficient.