|
A hypergraph ''H'' is called a hypertree in (arboreal hypergraph in, tree hypergraph in ) 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 hypergraphs. 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 subset of its hyperedges have a common vertex, then all hyperedges of the subset have a common vertex.〔; 〕 By results of Duchet, Flament and Slater (see e.g.〔 ;〕), a hypergraph is a hypertree if and only if it has the Helly property and its line graph is chordal if and only if its dual hypergraph is conformal and chordal. Thus, a hypergraph is a hypertree if and only if its dual hypergraph is alpha-acyclic (in the sense of Fagin et al.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hypertree」の詳細全文を読む スポンサード リンク
|