3
$\begingroup$

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real world?

In computer science we have red-black trees, B-trees, quadtrees, and so on. In the biological sense of the word tree, we have palm trees, pine trees, redwood trees, etc.

My question: is there a word $w$ such that a $w$ tree could refer to a physical tree in the real world, or a mathematical object?

$\endgroup$
  • $\begingroup$ I would give aspen tree as an answer, except that the structure that the authors describe isn't actually a tree. conferences.sigcomm.org/co-next/2013/program/p85.pdf $\endgroup$ – Joe Jun 3 '14 at 17:06
  • 2
    $\begingroup$ It's not quite what you want, but there is a graph-theoretic cactus. $\endgroup$ – Rick Decker Jun 3 '14 at 17:16
  • 1
    $\begingroup$ I guess "rooted tree" does not count? $\endgroup$ – Raphael Jun 3 '14 at 21:32
  • $\begingroup$ This doesn't answer your question either, but this paper borrows liberally from the terminology of forestry management in the service of managing trees, in a typical Phil Wadler way. homepages.inf.ed.ac.uk/wadler/topics/deforestation.html $\endgroup$ – Pseudonym Jun 4 '14 at 2:01
  • 2
    $\begingroup$ I was sorry to find out that people using attributed grammars do not even call Xmas trees their trees decorated with attributes. $\endgroup$ – babou Jun 4 '14 at 13:25
4
$\begingroup$

Robert Tarjan defines the palm tree in "Depth-first search and linear graph algorithms" (1972):

Let $P$ be a directed graph of two disjoint edge sets, denoted $v \rightarrow w$ and $v \overset{-}{\rightarrow} w$ respectively. If $P$ satisfies the following properties:

  1. The subgraph $T$ containing the edges $v \rightarrow w$ is a spanning tree of $P$;

  2. Each edge not in $T$ connects a vertex with one of its ancestors in $T$. The edges $v \overset{-}{\rightarrow} w$ are called the fronds of $P$.

e.g.,

Palm Tree

He goes on to prove that the directed graph generated by a depth-first search of a connected graph is a palm tree.

In Collective Tree Spanners and Routing in AT-free Related Graphs, Dragan, Yan, and Corneil construct a specific spanning tree that they call a willow-tree.

$\endgroup$
3
$\begingroup$

How about a banana tree? The organic kind are colloquially, but not botanically, trees.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.