Directed hyperpath

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

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}.