Все выпуски

Получены необходимые и достаточные условия выживаемости дифференциальной системы с последействием и дифференциального включения с последействием. Получены достаточные условия положительной инвариантности множества для системы (включения) с последействием.

Necessary and sufficient conditions of viability of differential systems with aftereffect and differential inclusions with aftereffect are received. Sufficient conditions of positive invariance of set for systems (inclusions) with aftereffect are received.

Для дифференциальной игры многих лиц найдены условия того, что заданное многозначное отображение в каждой точке есть множество выигрышей в ситуациях равновесия по Нэшу. Данное условие выписано в инфинитезимальной форме. Также найдены достаточные условия, при которых набор непрерывных функций обеспечивает равновесие по Нэшу. Данное условие обобщает метод, основанный на системе уравнений типа Гамильтона–Якоби.

We study Nash equilibrium for a differential game with many players. The condition on a multivalued map under which any value of this map is a set of Nash equilibrium payoffs is obtained. This condition is written in infinitesimal form. The sufficient condition for the given complex of continuous functions to provide a Nash equilibrium is obtained. This condition is a generalization of the method based on system of Hamilton–Jacobi equations.

Рассматривается игровая задача на максимин функции платы, определенной на произведении множеств притяжения терминальных состояний систем первого и второго игрока. Данные множества притяжения найдены с помощью конструкций расширения в классе конечно-аддитивных мер.

We consider a game problem of maximin of cost function defined on the product of attraction sets of players’ dynamic systems terminal positions. These sets are constructed using the extension in the class of finitely additive measures.

Рассматривается вопрос о существовании рекуррентных и почти рекуррентных сечений многозначных отображений R ∋ t → F(t) ∈ compU с непустыми компактными образами F(t) в полном метрическом пространстве U. На множестве compU вводится метрика Хаусдорфа dist. Рекуррентные и почти рекуррентные многозначные отображения определяются как функции со значениями в метрическом пространстве (compU, dist). Доказано существование рекуррентных (почти рекуррентных) сечений многозначных рекуррентных (соответственно, почти рекуррентных) равномерно абсолютно непрерывных отображений. Рассматриваются также отображения R ∋ t → F(t), образы которых состоят из конечного числа точек (зависящего от t). Доказано, что если такое отображение почти рекуррентно, то у него существует почти рекуррентное сечение. Многозначное рекуррентное отображение, образы F(t) которого для всех t ∈ R состоят не более чем из n точек (где n ∈ N), имеет рекуррентное сечение. Если образы многозначного рекуррентного (почти рекуррентного) отображения t → F(t) при всех t ∈ R состоят из n точек, то все n непрерывных сечений отображения F рекуррентны (почти рекуррентны).

In the paper, we consider the problem of existence of recurrent and almost recurrent selections of multivalued mappings R ∋ t → F(t) ∈ compU with nonempty compact sets F(t) in a complete metric space U. The set compU is equipped with the Hausdorff metric dist. Recurrent and almost recurrent multivalued maps are defined as the functions with values in the metric space (compU, dist). It is proved that there are recurrent (almost recurrent) selections of multivalued recurrent (almost recurrent) uniformly absolutely continuous maps. We also consider mappings R ∋ t → F(t) with the sets F(t) consisting of a finite number of points (the number depends on the t ∈ R). We prove that if such a map is almost recurrent, then it has an almost recurrent selection. A multivalued recurrent mapping t → F(t) with sets F(t) consisting of at most n points (where n ∈ N) has a recurrent selection. If the sets F(t) of a multivalued recurrent (almost recurrent) mapping t → F(t) consist of n points for all t ∈ R, then all n continuous selections of the map F are recurrent (almost recurrent).

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

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

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

Полученная двухсторонняя оценка числа убегающих, достаточного для уклонения от встречи из любой начальной позиции от заданного числа преследователей, иллюстрируется примерами.

A linear non-stationary differential pursuit game with a group of pursuers and a group of evaders is considered. The pursuers' goal is to catch all evaders and the evaders' goal is at least for one of them to avoid contact with pursuers.

All players have equal dynamic capabilities, geometric constraints on the control are strictly convex compact set with smooth boundary. The point in question is the minimum number of evaders that is sufficient to evade a given number of pursuers from any initial position. Sufficient conditions for the solvability of the global problem of evasion are used as an upper estimate of this minimum. We assume that to capture one evader it suffices that the initial position of this evader lie in the interior of convex hull of initial positions of pursuers. Using this assumption we find a lower estimate of this minimum.

The obtained two-sided estimate of the number of evaders sufficient to avoid contact with a given number of pursuers from any initial position is illustrated by examples.

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

Работа посвящена изучению наилучших равномерных рациональных приближений (НРРП) непрерывных функций на компактных, в том числе конечных, подмножествах числовой оси $\mathbb{R}$. Показано, что НРРП на конечном множестве существует не всегда. Более подробно изучен алгоритм Гельмута Вернера поиска НРРП вида $P_m/Q_n = \sum\limits_{i=0}^m a_i x^i \big/ \sum\limits_{j=0}^n b_j x^j$ для функций на множестве из $N=m+n+2$ точек $x_1<\ldots<x_N$. Этот алгоритм может использоваться в алгоритме Ремеза поиска НРРП на отрезке. При работе алгоритма Вернера вычисляется $(n+1)$ вещественное собственное значение $h_1,\ldots,h_{n+1}$ для пучка матриц $A-hB$, где $A$ и $B$ - некоторые симметричные матрицы. Каждому собственному значению сопоставляется своя рациональная дробь вида $P_m/Q_n$, являющаяся кандидатом на наилучшее приближение. Поскольку не более одной из этих дробей свободны от полюсов на отрезке $[x_1, x_N]$, то возникает задача отыскания того собственного значения, которому соответствует рациональная дробь без полюсов. В работе показано, что если $m=0$, все значения $f(x_1),-f(x_2),\ldots,(-1)^{n+2} f(x_{n+2})$ различны и НРРП положительно (отрицательно) во всех точках $x_1,\ldots,x_{n+2}$, то это собственное значение занимает $[(n+2)/2]$-е ($[(n+3)/2]$-е) место по величине. Приведены три численных примера, иллюстрирующих это утверждение.

The paper deals with the best uniform rational approximations (BURA) of continuous functions on compact (and even finite) subsets of real axis $\mathbb{R}$.The authors show that BURA does not always exist. They study the algorithm of Helmut Werner in more detail. This algorithm serves to search for BURA of the type $P_m/Q_n = \sum\limits_{i=0}^m a_i x^i \big/ \sum\limits_{j=0}^n b_j x^j$ for functions on a set of $N=m+n+2$ points $x_1<\ldots<x_N$. It can be used within the Remez algorithm of searching for BURA on a segment. The Verner algorithm calculates $(n+1)$ real eigenvalues $h_1,\ldots,h_{n+1}$ for the matrix pencil $A-hB$, where $A$ and $B$ are some symmetric matrices. Each eigenvalue generates a rational fraction of the type $P_m/Q_n$ which is a candidate for the best approximation. It is known that at most one of these fractions is free from poles on the segment $[x_1, x_N]$, so the following problem arises: how to determine the eigenvalue which generates the rational fraction without poles? It is shown that if $m=0$ and all values $f(x_1),-f(x_2),\ldots,(-1)^{n+2} f(x_{n+2})$ are different and the approximating function is positive (negative) at all points $x_1,\ldots,x_{n+2}$, then this eigenvalue ranks $[(n+2)/2]$-th ($[(n+3)/2]$-th) in value. Three numerical examples illustrate this statement.

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