Pergunta

A tree is a special kind a graph.

However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if you will.

This is not a tree anymore.

This is a specialized DAG that has more restriction. That is, it has a single root (or source)

Does this type of graph have a name?

CLARIFICATION:

By 'tree', I'm referring to the tree data structure, not a tree in graph theory. It seems crazy to me that such related objects have the same name even though they don't mean the same thing. The tree data structure is always rooted but there are rooted DAG that are not trees.

{1→2, 2→3, 1→3, 4→2} doesn't qualify because 4→2 is an edge toward an ancestor, not a descendant. {1→2, 1→3, 2→4, 3→4} doesn't qualify.

{1→2, 2→3, 1→3} and {1→2, 1→3, 2→4, 3→5, 3→6, 1→4, 1→6} both qualify.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top