Binary relation
Binary relation — бинарное отношение.
[math]\displaystyle{ \,R }[/math] is a binary relation on [math]\displaystyle{ \,V }[/math] if [math]\displaystyle{ R \subseteq V \times V }[/math]. [math]\displaystyle{ \,R }[/math] is reflexive on [math]\displaystyle{ \,V }[/math] if for all [math]\displaystyle{ v \in V }[/math] [math]\displaystyle{ (v,v) \in R }[/math] and irreflexive otherwise. [math]\displaystyle{ \,R }[/math] is transitive on [math]\displaystyle{ \,V }[/math], if for all [math]\displaystyle{ u, v, w \in V }[/math] [math]\displaystyle{ (u,v) \in R }[/math] and [math]\displaystyle{ (v,w) \in R }[/math] implies [math]\displaystyle{ (u,w) \in R }[/math]. [math]\displaystyle{ \,R }[/math] is symmetric, if [math]\displaystyle{ (v,w) \in R }[/math] implies [math]\displaystyle{ (w,v) \in R }[/math], and antisymmetric on [math]\displaystyle{ V }[/math], if for all [math]\displaystyle{ u, v \in V }[/math] [math]\displaystyle{ (u,v) \in R }[/math] and [math]\displaystyle{ (v,u) \in R }[/math] implies [math]\displaystyle{ \,u = v }[/math].
The inverse of a relation [math]\displaystyle{ \,R }[/math], denoted by [math]\displaystyle{ \,R^{-1} }[/math], is obtained by reversing each of the pairs belonging to [math]\displaystyle{ \,R }[/math], so that [math]\displaystyle{ \,aR^{-1}b }[/math] iff [math]\displaystyle{ \,bRa }[/math]. Let [math]\displaystyle{ \,R^{U} }[/math] denote the union and [math]\displaystyle{ \,R^{I} }[/math] the intersection of a collection of relations [math]\displaystyle{ \{R_{k}: \; k \in {\mathcal C}\} }[/math] in [math]\displaystyle{ \,S }[/math], where [math]\displaystyle{ {\mathcal C} }[/math] is some nonempty index set. Then [math]\displaystyle{ \,aR^{U}b }[/math] iff [math]\displaystyle{ \,aR_{k}b }[/math] for some [math]\displaystyle{ \,k }[/math] in [math]\displaystyle{ {\mathcal C} }[/math], and [math]\displaystyle{ \,aR^{I}b }[/math] iff [math]\displaystyle{ \,aR_{k}b }[/math] for each [math]\displaystyle{ \,k }[/math] in [math]\displaystyle{ {\mathcal C} }[/math].
See also
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.