In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a

hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...

is called a hypertree if it admits a

host graph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, a directed hypergraph is a pair (X,E), where X is ...

such that is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

. In other words, is a hypertree if there exists a tree such that every

hyperedge This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

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 In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected Node (computer science), nodes. Each node in the tree can be connected to many children (depending on the type of ...

of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for

s. They include the connected Berge-acyclic hypergraphs, which have also been used as a (different) generalization of trees for hypergraphs.

Properties

Every hypertree has the

Helly property In combinatorics, a Helly family of order is a family of sets in which every minimal ''subfamily with an empty intersection'' has or fewer sets in it. Equivalently, every finite subfamily such that every -fold intersection is non-empty has non ...

(2-Helly property): if a

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

of its hyperedges has the property that every two hyperedges in have a nonempty

intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...

, then itself has a

nonempty In mathematics, the empty set or void set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, whi ...

intersection (a vertex that belongs to all hyperedges in ). 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 In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

it has the Helly property and its

line graph In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...

is a chordal graph. *A hypergraph is a hypertree if and only if its

dual hypergraph Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual number, a nu ...

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 mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...

in the sense of Fagin. It is possible to recognize hypertrees (as duals of alpha-acyclic hypergraphs) in

linear time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

. The

exact cover In the mathematical field of combinatorics, given a collection \mathcal of subsets of a set X, an exact cover is a subcollection \mathcal^ of \mathcal such that each element in X is contained in ''exactly one'' subset in \mathcal^. One says that e ...

problem (finding a set of non-overlapping hyperedges that covers all the vertices) is solvable in polynomial time for hypertrees but remains

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

for alpha-acyclic hypergraphs.

Notes

References

*. *. *. *. *. *. *. *. {{refend Hypergraphs Trees (graph theory)

Properties

See also

Notes

References