Hypertree on:
[Wikipedia]
[Google]
[Amazon]
In the
In the mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a hypergraph
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, an undirected hypergraph H is a pair H = (X,E) w ...
is called a hypertree if it admits a host graph such that is a tree
In botany, a tree is a perennial plant with an elongated Plant stem, stem, or trunk (botany), trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondar ...
. 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 nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be co ...
of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for hypergraph
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, an undirected hypergraph H is a pair H = (X,E) w ...
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 (2-Helly property): if asubset
In mathematics, set ''A'' is a subset of a set ''B'' if all 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 are unequal, then ''A'' is a proper subset o ...
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 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, while in other ...
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" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicond ...
it has the Helly property and its line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
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.
It is possible to recognize hypertrees (as duals of alpha-acyclic hypergraphs) in linear time
In 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 performed by ...
.
The exact cover
In the mathematical field of combinatorics, given a collection of subsets of a set , an exact cover is a subcollection of such that each element in is contained in ''exactly one'' subset in . In other words, is a partition of consisting o ...
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, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
for alpha-acyclic hypergraphs.
See also
*Dually chordal graph
In the mathematical area of graph theory, an undirected graph is dually chordal if the hypergraph of its maximal cliques is a hypertree. The name comes from the fact that a graph is chordal if and only if the hypergraph of its maximal cliques i ...
, a graph whose maximal cliques form a hypertree
Notes
References
*. *. *. *. *. *. *. *. {{refend Hypergraphs Trees (graph theory)