Все выпуски

В терминах характеристических функций на множестве всех бинарных отношений множества $X$ вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар смежных бинарных отношений. Если $X$ — конечное множество, то эта алгебраическая система — граф («граф графов»). Доказано, что диаметр графа бинарных отношений равен 2. Показано, что если $\sigma$ и $\tau$ — смежные отношения, то $\sigma$ — ациклическое отношение (конечный ациклический орграф) тогда и только тогда, когда $\tau$ — ациклическое отношение. Получена явная формула для числа компонент связности графа ациклических отношений.

The paper introduces the concept of a binary reflexive relation of adjacency on the set of all binary relations of a set $X$ (in terms of characteristic functions) and determines an algebraic system consisting of all binary relations of the set and of all unordered pairs of adjacent binary relations. If $X$ is a finite set then this algebraic system is a graph (“the graph of graphs”). It is proved that the diameter of a graph of binary relations is 2. It is shown that if $\sigma$ and $\tau$ are adjacent relations, then $\sigma$ is an acyclic relation (finite acyclic digraph) if and only if $\tau$ is an acyclic relation. An explicit formula for the number of connected components of a graph of acyclic relations is received