2
$\begingroup$

I have an algorithm that recursively connects together pairs of nodes into new nodes. It looks like the Huffman code algorithm, except that a node can be re-used after it has been part of a merge. The result is a graph where each node has two parents, but can have any amount of children.

Is there a term for such a graph? It isn't technically a tree -- and has none of the special properties of a tree -- but it does look very related to one, which makes me think someone has explored this kind of generalisation. A pseudo-tree? A multi-parent tree?

The reason I ask is because it's easy to find tree drawing software out there (e.g. ETE3, which seems like it only supports binary trees), but searching for "graph visualisation" gives way too general results (e.g. for social network analysis).


Example, drawn manually: Tree?

$\endgroup$
4
  • $\begingroup$ What is the parent relationship and how does it relate to the merging? Why can a node have multiple children? $\endgroup$
    – D.W.
    Dec 20, 2022 at 19:44
  • $\begingroup$ @D.W. The relationship is string concatenation. A node can have multiple children because it can be concatenated to multiple strings. $\endgroup$
    – Mew
    Dec 21, 2022 at 12:01
  • $\begingroup$ I don't understand. I don't understand what you mean by "concatenated to multiple strings" - the question says nothing about strings or about concatenation. Can you please edit the question to define precisely the conditions under which one node is considered to be a parent of another node? Can you give an example of a minimal sequence of merges that leads to a node having two or more children? $\endgroup$
    – D.W.
    Dec 21, 2022 at 21:42
  • $\begingroup$ @D.W. Haha, the question was abstract because I wanted to keep it as graph-theoretical as possible. The example relation I gave was not in the question because it was only relevant as an answer to your question. Anyways, I've added an example graph. The question isn't why this relation exists, but what one calls it. $\endgroup$
    – Mew
    Dec 21, 2022 at 22:35

2 Answers 2

1
$\begingroup$

In graph theory, a tree is is usually defined as a connected undirected graph with no cycles. One would also call a directed graph a tree if the underlying undirected graph is a tree. The concept of nodes having "parents" is more a technique for working with trees as data structures in computer science. For an undirected graph, the concept of a "parent" only makes sense when there is a special node, called the "root" because a tree has the special property that there is a unique path between any two nodes. Thus, each non-root node has a unique neighbor that is closer to the root, which is the "parent". This implicitly gives you a way to direct the edges: direct all edges away from the root. (You could also direct all edges towards the root). This means that rooted trees are directed graphs where every node has in-degree 1, except for the root which has in-degree 0. The term "pseudotree" is already used to mean a directed graph where every node has in-degree 1, or in the undirected case, a graph that is a tree plus one more edge.

The graphs you are describing are quite unlike trees in a graph-theoretic way, so I doubt they would have been studied has a generalization of trees. That being said, my understanding of the process by which you are creating these graphs implies that there will never be a directed cycle. These are called Directed Acyclic Graphs (DAGs for short) and are quite important in computer science. Furthermore, your graphs have the property that the in-degree of a node is at most 2. I don't know if these have been studied but the keywords that you should search for are "Directed Acyclic Graphs" and "bounded in-degree".

$\endgroup$
0
$\begingroup$

I am not familiar with any standard name for graphs with this property. There are many more properties that one could imagine than names.

I would suggest that you use standard graph visualization software. You should be able to find many options, with a bit more searching. See, e.g., https://en.wikipedia.org/wiki/Graph_drawing, Graphviz, and many more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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