Multitree

A directed acyclic graph in which every ordered pair of vertices has at most one directed path, equivalently a DAG whose reachability order is diamond-free.

Version

v2 · 2026-09-06 · History

Domain-specific #

2337

Origin domain

mathematics

Subdomain

directed graphs

Aliases

Strongly unambiguous graph, Mangrove graph, Diamond-free reachability DAG

Core Idea

A multitree is a directed acyclic graph in which there is at most one directed path from any vertex (u) to any vertex (v). The condition permits a node to have multiple parents and permits overlapping hierarchies, but forbids two distinct ancestry routes connecting the same ordered pair. Equivalently, the reachability relation is a diamond-free partial order; the transitive reduction of such a poset is a multitree.

Another equivalent test is that the subgraph reachable from any one vertex induces an undirected tree.

Scope of Application

Multitrees model overlapping classifications, unambiguous nondeterministic computation, inheritance structures, and directed reachability where duplicate routes would create ambiguity. Furnas and Zacks use multitrees to represent multiple overlapping hierarchies while retaining navigable local tree structure. Wigderson analyzes unambiguous reachability restrictions in complexity theory.

Clarity

State whether the graph includes transitive edges or is transitively reduced, and test uniqueness over directed paths in the represented relation. Name whether “multitree” means this DAG/poset concept, a series–parallel order, or an unrelated data structure. Distinguish path uniqueness from merely unique shortest path.

Manages Complexity

The abstraction permits a concept to participate in multiple broader categories without allowing two different inheritance chains from one ancestor to the same descendant. Consequently, propagation from a source has a unique explanation path.

Abstract Reasoning

1. Verify directed acyclicity.
2. Compute or reason about reachability.
3. Search for an ordered pair joined by two distinct directed paths.
4. Equivalently search the reachability poset for a diamond.
5. Reduce transitive edges when a cover graph is required.
6. Check each root's reachable subgraph for an undirected cycle.
7. Use unique paths for attribution or propagation.
8. If a second path is needed, decide whether ambiguity is acceptable or the identity should be a general DAG.

Knowledge Transfer

The portable pattern is allow multiple local hierarchies but forbid reconvergence that gives one ancestor two distinct routes to one descendant. It transfers to provenance and access inheritance. The proposed immediate parent is Directed Acyclic Graph.

Relationships to Other Abstractions

Current abstraction Multitree Domain-specific

Parents (1) — more general patterns this builds on

• Multitree is a kind of Directed Acyclic Graph Prime

  Directed Acyclic Graph is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

• Multitree → Directed Acyclic Graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space

Multitree sits in a sparse region of the domain-specific corpus (84^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Discrete Structures & Graph Algorithms (17 abstractions)

Nearest neighbors

• Good Spanning Tree — 0.83
• Homogeneous Graph — 0.82
• Quotient Graph — 0.82
• Cage (Graph Theory) — 0.80
• Tree (Data Structure) — 0.80

Computed from structural-signature embeddings · 2026-09-08