# Directed hyperpath

Перейти к:навигация, поиск

Directed hyperpath --- ориентированный гиперпуть.

A directed hyperpath $P_{Rt}$ from the root set $R \; (\subseteq V)$ to the sink $t \; (\in V)$ in $H$ is a minimal acyclic sub-hypergraph of $H$ containing both the nodes of $R$ and node $t$, such that each node, with exception of the nodes in $R$, has exactly one entering hyperarc.

The definition of a hyperpath can be extended as follows. A (directed) hypertree $T_{R}$ rooted at $R$ in $H$ is an acyclic sub-hypergraph of $H$ containing the nodes in $R$, such that each node, with the exception of the nodes in $R$ has exactly one entering hyperarc.

The set $R$ is called the root set, while the remaining nodes are called the non-roots. Any non-root $v$ not contained in the tail of any hyperarc of $T_{R}$ is said to be a leaf of the hypertree. By definition, for any non-root $v$ there is a unique directed hyperpath in $T_{R}$ from $R$ to $v$.

An undirected hyperpath (hypertree) is a permutation of a hyperpath $P_{Rt}$ (hypertree $T_{R}$), i.e. it is obtained by a permutation of some of the hyperarcs on $P_{Rt}$ ($T_{R}$), where the permutation of a hyperarc $e$ is a hyperarc $e'$ such that $T_{e}' \cup h_{e}' = T_{e} \sup h_{e}$.