Connected to relation

Материал из WikiGrapp

Connected to relationотношение связности ''к'', (достижимость) в гиперграфе.

The relation connected to, which is denoted by the symbol [math]\displaystyle{ \succ }[/math], is defined for a given subset [math]\displaystyle{ \,R }[/math] of nodes and a node [math]\displaystyle{ \,y }[/math]; we say that [math]\displaystyle{ \,R }[/math] is connected to [math]\displaystyle{ \,y }[/math] and write [math]\displaystyle{ R \succ y }[/math] if and only if a directed hyperpath exsists in a hypergraph from [math]\displaystyle{ \,R }[/math] to the node [math]\displaystyle{ \,y }[/math].

It is easy to check that the relation [math]\displaystyle{ \succ }[/math] satisfies the following set of connectivity axioms:

(1) [math]\displaystyle{ y \in R \subseteq V \Rightarrow R \succ y }[/math] (reflexivity);

(2) [math]\displaystyle{ R \succ y\mbox{ and } Z \subseteq V \Rightarrow (R \cup Z) \succ y }[/math] (augmentation);

(3) [math]\displaystyle{ R \succ y, \; \forall y \in Y,\mbox{ and }Y \succ z \Rightarrow R \succ z }[/math] (transitivity).

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.