Hypertree
In the mathematical field of graph theory, a hypergraph is called a hypertree if it admits a host graph such that is a tree. In other words, is a hypertree if there exists a tree such that every hyperedge of is the set of vertices of a connected subtree of. Hypertrees have also been called arboreal hypergraphs or tree hypergraphs.
Every tree is itself a hypertree: itself can be used as the host graph, and every edge of is a subtree of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs. They include the connected Berge-acyclic hypergraphs, which have also been used as a generalization of trees for hypergraphs.
Properties
Every hypertree has the Helly property : if a subset of its hyperedges has the property that every two hyperedges in have a nonempty intersection, then itself has a nonempty intersection.By results of Duchet, Flament and Slater hypertrees may be equivalently characterized in the following ways.
- A hypergraph is a hypertree if and only if it has the Helly property and its line graph is a chordal graph.
- A hypergraph is a hypertree if and only if its dual hypergraph is conformal and the 2-section graph of is chordal.
- A hypergraph is a hypertree if and only if its dual hypergraph is alpha-acyclic in the sense of Fagin.
The exact cover problem is solvable in polynomial time for hypertrees but remains NP-complete for alpha-acyclic hypergraphs.