Hypertree

A hypergraph H is called a hypertree if it admits a host graph T such that T is a tree. In other words H is a hypertree if there exists a tree T such that every hyperedge of H is the set of vertices of a connected subtree of T.[1] Hypertrees have also been called arboreal hypergraphs[2] or tree hypergraphs.[3]

Every tree T is itself a hypertree: T itself can be used as the host graph, and every edge of T is a subtree of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs.[4]

Properties

Every hypertree has the Helly property (2-Helly property): if a subset S of its hyperedges has the property that every two hyperedges in S have a nonempty intersection, then S itself has a nonempty intersection (a vertex that belongs to all hyperedges in S).[5]

By results of Duchet, Flament and Slater[6] hypertrees may be equivalently characterized in the following ways.

The exact cover problem is solvable in polynomial time for hypertrees but remains NP-complete for alpha-acyclic hypergraphs.[9]

Notes

References

This article is issued from Wikipedia - version of the Friday, April 15, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.