Hypertree
Encyclopedia
A hypergraph
H is called a hypertree, if it admits a host graph T such that T is a tree
, in other words if there exists a tree T such that every hyperedge of H induces a subtree in T.
Since a tree is a hypertree, hypertrees may be seen as a generalization of the notion of a tree for hypergraph
s. Any hypertree is isomorphic to some family of subtrees of a tree.
of its hyperedges have a common vertex, then all hyperedges of the subset have a common vertex.
The line graph of a hypertree is a chordal graph
.
A hypergraph is a hypertree if and only if
its dual hypergraph is conformal and chordal.
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
H is called a hypertree, if it admits a host graph T such that T is a tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
, in other words if there exists a tree T such that every hyperedge of H induces a subtree in T.
Since a tree is a hypertree, hypertrees may be seen as a generalization of the notion of a tree for hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
s. Any hypertree is isomorphic to some family of subtrees of a tree.
Properties
A hypertree has the Helly property (2-Helly property), i.e., if any two hyperedges from a subsetSubset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of its hyperedges have a common vertex, then all hyperedges of the subset have a common vertex.
The line graph of a hypertree is a chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
.
A hypergraph is a hypertree if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
its dual hypergraph is conformal and chordal.