Binary relation

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

Binary relationбинарное отношение.

\,R is a binary relation on \,V if R \subseteq V \times V. \,R is reflexive on \,V if for all v \in V (v,v) \in R and irreflexive otherwise. \,R is transitive on \,V, if for all u, v, w \in V (u,v) \in R and (v,w) \in R implies (u,w) \in R. \,R is symmetric, if (v,w) \in R implies (w,v) \in R, and antisymmetric on V, if for all u, v \in V (u,v) \in R and (v,u) \in R implies \,u = v.

The inverse of a relation \,R, denoted by \,R^{-1}, is obtained by reversing each of the pairs belonging to \,R, so that \,aR^{-1}b iff \,bRa. Let \,R^{U} denote the union and \,R^{I} the intersection of a collection of relations \{R_{k}: \; k \in {\mathcal C}\} in \,S, where {\mathcal C} is some nonempty index set. Then \,aR^{U}b iff \,aR_{k}b for some \,k in {\mathcal C}, and \,aR^{I}b iff \,aR_{k}b for each \,k in {\mathcal C}.

See also


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