Hypertree

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

Hypertree --- гипердерево.

This is a hypergraph (called arboreal hypergraph) such that there is a tree [math]\displaystyle{ T }[/math] with a vertex set [math]\displaystyle{ V }[/math] such that every edge [math]\displaystyle{ e \in {\mathcal H} }[/math] induces a subtree in [math]\displaystyle{ T }[/math] ([math]\displaystyle{ T }[/math] is then called an underlying vertex tree of [math]\displaystyle{ {\mathcal H} }[/math]). A hypergraph [math]\displaystyle{ {\mathcal H} }[/math] is a dual hypertree if there is a tree [math]\displaystyle{ T }[/math] with a vertex set [math]\displaystyle{ {\mathcal H} }[/math] such that for all vertices [math]\displaystyle{ v \in V }[/math] [math]\displaystyle{ T_{v} = \{e \in {\mathcal H}: \; v \in e\} }[/math] induces a subtree of [math]\displaystyle{ T }[/math] ([math]\displaystyle{ T }[/math] is then called the underlying hyperedge tree of [math]\displaystyle{ {\mathcal H} }[/math]).

Observe that [math]\displaystyle{ {\mathcal H} }[/math] is a hypertree if and only if [math]\displaystyle{ {\mathcal H}^{\ast} }[/math] is a dual hypertree.