Все выпуски

Любое бинарное отношение $\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).)$

В предыдущих работах авторов на множестве всех бинарных отношений множества $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\}$. Получена формула для числа транзитивных орграфов, имеющих фиксированное опорное множество. Аналогичная формула для числа ациклических орграфов, имеющих фиксированное опорное множество, получена авторами ранее.

Рассматриваются многозначные отображения, действующие из частично упорядоченного пространства $(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$ — решение исходного включения.