2
$\begingroup$

A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes.

Binary tree - root with 2 branches, which branch once/twice themselves

How do you call a rooted tree if the number of branches per node is arbitrary (outdegree of n) but the indegree 1 for all nodes other than the root node?

Tree with four branches and 0-3 sub-branches

$\endgroup$
  • $\begingroup$ How is this different from an arbitrary rooted tree? $\endgroup$ – Yuval Filmus Feb 14 at 12:56
  • $\begingroup$ The illustration shows what I would consider a mono-hierarchical rooted tree. An arbitrary rooted tree could also be a poly-hierarchy as far as I understand, with some nodes having an indegree > 1 i.e. multiple parents. Would mono-hierarchical rooted tree be understood in the field of computer science / discrete mathematics or are there any other established terms? $\endgroup$ – CoDEmanX Feb 14 at 13:08
  • $\begingroup$ In a rooted tree, every vertex other than the root has a single parent. That's the definition. $\endgroup$ – Yuval Filmus Feb 14 at 13:09
  • $\begingroup$ What term would you suggest for the poly-hierarchy case if it's not a tree by definition? Poly-hierarchical rooted graph? If one assumes a directed graph with all edges pointing either up or down, then directed acyclic graph (DAG) seems also fitting, as long as there is no edge pointing to any of the (grand)parents. $\endgroup$ – CoDEmanX Feb 14 at 13:16
  • $\begingroup$ I have never heard of poly-hierarchical rooted graphs, but they correspond to Hasse diagrams of posets. So perhaps Hasse diagram is a reasonable name, though you'll have to define it. $\endgroup$ – Yuval Filmus Feb 14 at 13:22
3
$\begingroup$

Rooted Tree

How do you call a rooted tree if the number of branches per node is arbitrary (outdegree of n) but the indegree 1 for all nodes other than the root node?

That is none other than an rooted tree itself or, more accurately, an arborescence or branching tree or out-tree according to the following quote from Wikipedia entry on rooted tree.

A rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an arborescence, branching, or out-tree; when it has an orientation towards the root, it is called an anti-arborescence or in-tree.

Multitree

Your are also interested in what you might call "Poly-hierarchical rooted graph".

An arbitrary rooted tree could also be a poly-hierarchy as far as I understand, with some nodes having an indegree > 1 i.e. multiple parents.

However, since every vertex other than the root has a single parent in a rooted tree by definition, it is not a viable idea to call them "Poly-hierarchical rooted tree". The conventional name for them is multitree as illustrated below, thanks to Wikipedia.

wikimedia multitree 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 partially ordered set that does not have four items $a$, $b$, $c$, and $d$ forming a diamond suborder with $a\le b \le d$ and $a\le c \le d$ but with $b$ and $c$ incomparable to each other (also called a diamond-free poset).

Polytree

You might be interested in polytree, as illustrated below, thanks to Wikipedia again. It is "also known as oriented tree or singly connected network". It is "a directed acyclic graph whose underlying undirected graph is a tree."

wikimedia ploytree

Hasse Diagram

Another related concept is Hasse diagram, which is "used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction", as illustrated below.

https://math.stackexchange.com/questions/819254/how-many-rows-will-we-draw-in-hasse-diagram


Exercise 1. Draw a polytree that is not a rooted tree. Draw a multitree that is not a polytree. Draw a Hasse diagram that is not a multitree.

Exercise 2. Every rooted tree is a polytree. Show that every polytree is a multitree. Show that every multitree is the Hasse diagram of some finite partially ordered set.

$\endgroup$
  • $\begingroup$ For exercise 1, also draw a directed acyclic graph that is not a Hasse diagram. For exercise 2, add "every Hasse diagram is a directed acyclic graph". $\endgroup$ – Apass.Jack Feb 15 at 17:10

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.