Все выпуски

Любое бинарное отношение $\sigma\subseteq X^2$ (где $X$ - произвольное множество) порождает на множестве $X^2$ характеристическую функцию: если $(x,y)\in\sigma,$ то $\sigma(x,y)=1,$ а иначе $\sigma(x,y)=0.$ В терминах характеристических функций на множестве всех бинарных отношений множества $X$ вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар различных смежных бинарных отношений. Если $X$ - конечное множество, то эта алгебраическая система - граф («граф графов»).
Показано, что если $\sigma$ и $\tau$ - смежные отношения, то $\sigma$ является рефлексивно-транзитивным отношением тогда и только тогда, когда $\tau$ является рефлексивно-транзитивным отношением. Исследованы некоторые особенности строения графа $G(X)$ рефлексивно-транзитивных отношений. В частности, если $X$ состоит из $n$ элементов, а $T_0(n)$ - это число помеченных $T_0$-топологий, определенных на множестве $X,$ то количество компонент связности равно $\sum_{m=1}^n S(n,m) T_0(m-1),$ где $S(n,m)$ - числа Стирлинга 2-го рода. $($Хорошо известно, что количество вершин в графе $G(X)$ равно $\sum_{m=1}^nS(n,m) T_0(m).)$

Any binary relation $\sigma\subseteq X^2$ (where $X$ is an arbitrary set) generates on the set $X^2$ a characteristic function: if $(x,y)\in\sigma,$ then $\sigma(x,y)=1,$ otherwise $\sigma(x,y)=0.$ In terms of characteristic functions we introduce on the set of all binary relations of the set $X$ the concept of a binary reflexive relation of adjacency and determine an algebraic system consisting of all binary relations of the set and of all unordered pairs of various adjacent binary relations. If $X$ is a finite set then this algebraic system is a graph (“the graph of graphs’’).
It is shown that if $\sigma$ and $\tau$ are adjacent relations then $\sigma$ is a reflexive-transitive relation if and only if $\tau$ is a reflexive-transitive relation. Several structure features of the graph $G(X)$ of reflexive-transitive relations are investigated. In particular, if $X$ consists of $n$ elements, and $T_0(n)$ is the number of labeled $T_0$-topologies defined on the set $X,$ then the number of connected components is equal to $\sum_{m=1}^nS(n,m) T_0(m-1),$ where $S(n,m)$ are Stirling numbers of second kind. $($It is well known that the number of vertices in a graph $G(X)$ is equal to $\sum_{m=1}^nS(n,m) T_0(m).)$

В предыдущих работах авторов на множестве всех бинарных отношений множества $X$ введено понятие бинарного рефлексивного отношения смежности и определена алгебраическая система, состоящая из всех бинарных отношений множества $X$ и из всех неупорядоченных пар смежных бинарных отношений. Если $X$ - конечное множество, то эта алгебраическая система - граф (граф бинарных отношений $G$). В настоящей работе для ациклических и транзитивных орграфов вводится понятие опорного множества: это совокупности $S(\sigma)$ и $S'(\sigma)$, состоящие из вершин орграфа $\sigma\in G$, имеющих нулевую полустепень захода и исхода соответственно. Доказано, что если $G_\sigma$ - связная компонента графа $G$, содержащая ациклический или транзитивный орграф $\sigma\in G$, то $\{S(\tau): \tau\in G_\sigma\}=\{S'(\tau): \tau\in G_\sigma\}$. Получена формула для числа транзитивных орграфов, имеющих фиксированное опорное множество. Аналогичная формула для числа ациклических орграфов, имеющих фиксированное опорное множество, получена авторами ранее.

In previous works of the authors, the concept of a binary reflexive adjacency relation was introduced on the set of all binary relations of the set $X$, and an algebraic system consisting of all binary relations of the set $X$ and of all unordered pairs of adjacent binary relations was defined. If $X$ is a finite set, then this algebraic system is a graph (graph of binary relations $G$). The current paper introduces the notion of a support set for acyclic and transitive digraphs. This is the collections $S(\sigma)$ and $S'(\sigma)$ consisting of the vertices of the digraph $\sigma\in G$ that have zero indegree and zero outdegree, respectively. It is proved that if $G_\sigma $ is a connected component of the graph $G$ containing the acyclic or transitive digraph $\sigma\in G$, then $\{S(\tau): \tau\in G_\sigma\}=\{S'(\tau): \tau\in G_\sigma\}$. A formula for the number of transitive digraphs having a fixed support set is obtained. An analogous formula for the number of acyclic digraphs having a fixed support set was obtained by the authors earlier.

Рассматриваются многозначные отображения, действующие из частично упорядоченного пространства $(X,\leq)$ в множество $Y$, на котором задано рефлексивное бинарное отношение $\vartheta$ (это отношение не предполагается ни антисимметричным, ни транзитивным, т.е. $\vartheta$ не является порядком в $Y$). Для таких отображений введены аналоги понятий накрывания и монотонности. С использованием этих понятий исследуется включение $F(x)\ni \tilde{y}$, где $F\colon X \rightrightarrows Y$, $\tilde{y}\in Y$. Предполагается, что для некоторого заданного $x_0\in X$ существует $y_{0} \in F(x_{0})$ такой, что $(\tilde{y},y_{0}) \in \vartheta$. Получены условия существования решения $x\in X$ изучаемого включения, удовлетворяющего неравенству ${x\leq x_0}$, и условия существования минимального и наименьшего решений. Также определяется и исследуется свойство устойчивости решений рассматриваемого включения к изменениям многозначного отображения $F$ и элемента $\widetilde{y}$. А именно, рассматривается последовательность «возмущенных» включений $F_i(x)\ni \tilde{y}_i$, $i\in \mathbb{N}$, получены условия, при которых эти включения имеют решения $x_i \in X$ и для любой возрастающей последовательности $\{i_n\}$ натуральных чисел выполнено $\sup_{n \in \mathbb{N}}\{x_{i_{n}}\}= x$, где $x\in X$ — решение исходного включения.

Set-valued mappings acting from a partially ordered space $X=(X,\leq)$ to a set $Y$ on which a reflexive binary relation $\vartheta$ is given (this relation is not supposed to be antisymmetric or transitive, i.e., $\vartheta$ is not an order in $Y$), are considered. For such mappings, analogues of the concepts of covering and monotonicity are introduced. These concepts are used to study the inclusion $F(x)\ni \tilde{y},$ where $F\colon X \rightrightarrows Y,$ $\tilde{y}\in Y.$ It is assumed that for some given $x_0 \in X,$ there exists $y_{0} \in F(x_{0})$ such that $(\tilde{y},y_{0}) \in \vartheta.$ Conditions for the existence of a solution $x\in X$ satisfying the inequality $x\leq x_0$ are obtained, as well as those for the existence of minimal and least solutions. The property of stability of solutions of the considered inclusion to changes of the set-valued mapping $F$ and of the element $\widetilde{y}$ is also defined and investigated. Namely, the sequence of “perturbed” inclusions $F_i(x)\ni \tilde{y}_i,$ $i\in \mathbb{N},$ is assumed, and the conditions of existence of solutions $x_i \in X$ such that for any increasing sequence of integers $\{i_n\}$ there holds $\sup_{n \in \mathbb{N}}\{x_{i_{n}}\}= x,$ where $x \in X$ is a solution of the initial inclusion, are derived.