Все выпуски

Любое бинарное отношение σ⊆X (где X - произвольное множество) порождает на множестве X² характеристическую функцию: если (x,y)∈σ, то σ(x,y)=1, а иначе σ(x,y)=0. В терминах характеристических функций на множестве всех бинарных отношений множества X вводится понятие бинарного рефлексивного отношения смежности и определяется алгебраическая система, состоящая из всех бинарных отношений множества и из всех неупорядоченных пар различных смежных бинарных отношений. Если X - конечное множество, то эта алгебраическая система - граф («граф графов»).

Показано, что если σ и τ - смежные отношения, то σ является частичным порядком тогда и только тогда, когда τ является частичным порядком. Исследованы некоторые особенности строения графа G(X) частичных порядков. В частности, если X состоит из n элементов, а T₀(n) - это число помеченных T₀-топологий, определенных на множестве X, то количество вершин в графе G(X) равно T₀(n), а количество компонент связности равно T₀(n-1).

Для всякого отношения частичного порядка σ определяется понятие его опорного множества S(σ), являющегося некоторым подмножеством множества X. Если X - конечное множество, а частичные порядки σ и τ принадлежат одной и той же компоненте связности графа G(X), то равенство S(σ)=S(τ) имеет место тогда и только тогда, когда σ=τ. Показано, что в каждой компоненте связности графа G(X) совокупность опорных множеств ее элементов является специфическим частично упорядоченным множеством относительно естественного отношения включения множеств.

Any binary relation σ⊆X (where X is an arbitrary set) generates a characteristic function on the set X²: if (x,y)∈σ, then σ(x,y)=1, otherwise σ(x,y)=0. In terms of characteristic functions on the set of all binary relations of the set X we introduced the concept of a binary reflexive relation of adjacency and determined the algebraic system consisting of all binary relations of a set and of all unordered pairs of various adjacent binary relations. If X is finite set then this algebraic system is a graph (“a graph of graphs”).

It is shown that if σ and τ are adjacent relations then σ is a partial order if and only if τ is a partial order. We investigated some features of the structure of the graph G(X) of partial orders. In particular, if X consists of n elements, and T₀(n) is the number of labeled T₀-topologies defined on the set X, then the number of vertices in a graph G(X) is T₀(n), and the number of connected components is T₀(n-1).

For any partial order σ there is defined the notion of its support set S(σ), which is some subset of X. If X is finite set, and partial orders σ and τ belong to the same connected component of the graph G(X), then the equality S(σ)=S(τ) holds if and only if σ=τ. It is shown that in each connected component of the graph G(X) the union of support sets of its elements is a specific partially ordered set with respect to natural inclusion relation of sets.

Любое бинарное отношение $\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$ — конечное множество, то эта алгебраическая система — граф («граф графов»). Доказано, что диаметр графа бинарных отношений равен 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

В предыдущих работах авторов на множестве всех бинарных отношений множества $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.

Изучается бикомпактное расширение счётного дискретного пространства, построенное как пространство Стоуна одной булевой алгебры. Получены новые классы точек этого расширения.

We consider a compactification of a countable discrete space constructed as a Stone space of a Boolean algebra. Some new points of the compactification are constructed.

Рассматривается компактификация BN счётного дискретного пространства N. В данной работе описаны свойства замыканий подмножеств BN, состоящих из различных классов точек. Показано существование точек, не принадлежащих классам, выделенным ранее.

We consider a compactification BN of a countable discrete space N. The paper describes some properties of the closures of subsets of BN, which consist of points belonging to different classes. We prove the existence of points which do not belong to the classes obtained before.

Pассматриваются пространства Стоуна BD и BS двух булевых алгебр. Доказывается, что множество свободных ультрафильтров пространства BD и пространство BS гомеоморфны канторову совершенному множеству.

We consider the Stone spaces BD and BS of two Boolean algebras. We prove, that the subspace Ĉ ⊆ BD of free ultrafilters of the space BD, and the space BS are homeomorphic to the Cantor set.

В работе рассматривается пространство Стоуна булевой алгебры подмножеств одного счетного частично упорядоченного множества. Главной особенностью этого множества является наличие бесконечного числа непосредственных последователей у каждого его элемента. Отсюда следует, что каждый фиксированный ультрафильтр данного пространства Стоуна является неизолированной точкой, а подмножество свободных ультрафильтров всюду плотно. В работе дана классификация точек пространства, доказано, что есть свободные ультрафильтры, которые не являются пределами последовательностей фиксированных ультрафильтров, а также свободные ультрафильтры, определяемые цепями частично упорядоченного множества. Рассмотрены кардинальные инварианты подпространства свободных ультрафильтров. Доказано, что это подпространство имеет счетное число Суслина, но не сепарабельно.

The paper concerns the Stone space of the Boolean algebra of subsets of one countable partially ordered set. The main feature of this set is the existence of countably many successors of each of its elements. From this property it follows that every fixed ultrafilter of this Stone space is a nonisolated point; the subset of free ultrafilters is dense everywhere. The classification of space points is given; the fact that there are free ultrafilters, which are not limits of sequences of fixed ultrafilters, as well as free ultrafilters determined by chains of partially ordered set, is proved. The cardinal invariants of the subspace of free ultrafilters are considered. It is shown that this subspace has the countable Suslin number, but is not separable.

Изучаются свойства дискретной вариационной задачи динамической аппроксимации в комплексном евклидовом (L + 1)-мерном пространстве E. Она обобщает известные задачи среднеквадратической полиномиальной аппроксимации функций, заданных своими отсчетами в конечном интервале. В рассматриваемой задаче аппроксимация последовательности y = {y_i}_L⁰ отсчетов функции y(t) ∈ L²[0, T], T = Lh на сетке I_h осуществляется решениями однородных линейных дифференциальных или разностных уравнений заданного порядка n с постоянными, но, возможно, неизвестными коэффициентами. Тем самым показано, что в последнем случае задача аппроксимации включает в себя и задачу идентификации. Анализ ее особенностей - основная тема статьи. Ставится задача нахождения вектора коэффициентов  разностного уравнения Σ_n⁰ ŷ_i+k α_i = 0, где k = 0,L − n. Оптимизируются коэффициенты  и начальные условия переходного процесса y этого уравнения. Цель оптимизации - наилучшая аппроксимация исследуемого динамического процесса y ∈ E. Критерий аппроксимации  минимум величины ||y − ŷ||²_E. Показано, что изучаемая вариационная задача сводится к задачам проектирования в E вектора y на ядра разностных операторов с неизвестными коэффициентами α ∈ ω ⊂ S ⊂ Eⁿ⁺¹. Здесь α - направление, S - сфера или гиперплоскость. Показана связь изучаемой задачи с задачами дискретизации и идентифицируемости. Тогда координаты вектора y ∈ E есть точное решение дифференциального уравнения на сетке I_h и y = ŷ. Дано сравнение изучаемой задачи вариационной идентификации с алгебраическими методами идентификации. Показано, что ортогональные дополнения к ядрам разностных операторов всегда имеют теплицев базис. Это приводит к быстрым проекционным алгоритмам вычислений. Показано, что задача нахождения оптимального вектора α сводится к задаче безусловной минимизации функционала идентификации, зависящего от направления  в Eⁿ⁺¹. Предложена итерационная процедура его минимизации на сфере с широкой областью и высокой скоростью сходимости. Изучаемую вариационную задачу можно применять при математическом моделировании в управлении и научных исследованиях. При этом на конечных интервалах может использоваться, в частности, возможность кусочно-линейной динамической аппроксимации сложных динамических процессов разностными и дифференциальными уравнениями указанного типа.

Some properties of the discrete variational problem of the dynamic approximation in the complex Euclidean (L + 1)-dimensional space are studied here. It generalizes familiar problems of the mean square polynomial approximation of the functions given on the finite interval in accordance with their references. In the problem under consideration sequence approximation y = {y_i}_L⁰ of the references of the function y(t) ∈ L²[0, T], T = Lh on the lattice I_h is achieved by solving homogeneous linear differential equations or difference equations of the given order n with constant but possibly unknown coefficients. Thus, it is shown that in the latter case the approximation problem also includes the identification problem. The analysis of its properties is the main subject of the article. The problem is set to find vector of coefficients  of difference equation Σ_n⁰ ŷ_i+k α_i = 0, where k = 0,L − n. Coefficients  and initial conditions of the transient process by of this equation are optimized. The optimization purpose is to achieve the best approximation of the dynamic process y ∈ E being considered here. The approximation criterion is a minimum of the quantity ||y − ŷ||²_E. The variational problem under study is shown to be reduced to the problem of projecting vector y in E on the kernels of the difference operators with unknown coefficients  α ∈ ω ⊂ S ⊂ Eⁿ⁺¹, where  is a direction, S is a sphere or a hyperplane. The problem under study is shown to be related to the problems of the discretization and identifiability. In this case vector coordinates y ∈ E is an exact solution of differential equation on the lattice I_h and y = ŷ. The problem of the variational identification is compared with algebraic methods of identification. The orthogonal complement to the kernels of the difference operators are shown to always have Toeplitz basis. This results in fast projecting algorithms of computation. The problem of finding optimal vector α is shown to be reduced to the problem of the absolute minimization of the identification functional depending on the direction  in Eⁿ⁺¹. The iterative procedure of its minimization on a sphere with wide domain and high speed of convergence is presented here. The variational problem considered here can be applied in mathematical modeling for control problem and research purposes. On the finite intervals, for example, it is possible to use piecewise-linear dynamic approximations of the complex dynamic processes with difference and differential equations of the specified type.

Рассматривается задача построения вершинного описания выпуклого полиэдра, заданного как множество решений некоторой системы линейных неравенств, коэффициенты которой являются алгебраическими числами. Обратная задача эквивалентна (двойственна) исходной. Предлагаются программные реализации нескольких модификаций хорошо известного метода двойного описания (метода Моцкина-Бургера), решающего поставленную задачу. Рассматривается два случая: 1) элементы системы неравенств - произвольные алгебраические числа, при этом каждое такое число задается минимальным многочленом и локализующим интервалом; 2) элементы системы неравенств принадлежат заданному конечному расширению ${\mathbb Q} (\alpha)$ поля ${\mathbb Q}$, при этом для $\alpha$ задаются минимальный многочлен и локализующий интервал, а все элементы исходной системы, конечные и промежуточные результаты представлены как многочлены от $\alpha$. Как и ожидалось, программная реализация для второго варианта значительно превосходит реализацию для первого варианта по производительности. Для большего ускорения во втором случае предлагается использовать булевы матрицы вместо матриц невязок. Результаты вычислительного эксперимента показывают, что программные реализации вполне пригодны для решения задач умеренных размеров.

We consider the problem of constructing the dual representation of a convex polyhedron defined as a set of solutions to a system of linear inequalities with coefficients which are algebraic numbers. The inverse problem is equivalent (dual) to the initial problem. We propose program implementations of several variations of the well-known double description method (Motzkin-Burger method) solving this problem. The following two cases are considered: 1) the elements of the system of inequalities are arbitrary algebraic numbers, and each such number is represented by its minimal polynomial and a localizing interval; 2) the elements of the system belong to a given extension ${\mathbb Q} (\alpha)$ of ${\mathbb Q}$, and the minimal polynomial and the localizing interval are given only for $\alpha$, all elements of the system, intermediate and final results are represented as polynomials of $\alpha$. As expected, the program implementation for the second case significantly outperforms the implementation for the first one in terms of speed. In the second case, for greater acceleration, we suggest using a Boolean matrix instead of the discrepancy matrix. The results of a computational experiment show that the program is quite suitable for solving medium-scale problems.