Все выпуски

Любое бинарное отношение σ⊆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) совокупность опорных множеств ее элементов является специфическим частично упорядоченным множеством относительно естественного отношения включения множеств.

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

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

В настоящей работе проведено исследование модели деформаций системы из $n$ стилтьесовских струн, расположенных вдоль геометрического графа-звезды, с нелинейным условием в узле. Соответствующая граничная задача имеет вид $$ \left\{\begin{array}{lll} -\left(p_iu_i^\prime\right)(x)+\displaystyle{\int_{0}^{x}}u_i\,dQ_i=F_i(x)-F_i(+0)-(p_iu_i')(+0),\quad i=1,2, \ldots, n,\\ \sum\limits_{i=1}^np_i(+0)u_i'(+0)\in N_{[-m,m]}u(0),\\ u_1(0)=u_2(0)=\ldots=u_n(0)=u(0),\\ (p_iu_i')(l_i-0)+u_i(l_i)\Delta Q_i(l_i)=\Delta F_i(l_i),\quad i=1,2,\ldots, n. \end{array} \right. $$ Здесь функции $u_i(x)$ определяют деформации каждой из струн; $F_i(x)$ описывают распределение внешней нагрузки; $p_i(x)$ характеризуют упругость струн; $Q_i(x)$ описывают упругую реакцию внешней среды. Скачок $\Delta F_i(l_i)$ равняется сосредоточенной в точке $l_i$ внешней силе; скачок $\Delta Q_i(l_i)$ совпадает с жесткостью упругой опоры (пружины), прикрепленной к точке $l_i$. Условие $\sum\limits_{i=1}^np_i(+0)u_i'(+0)\in N_{[-m,m]}u(0)$ возникает за счет наличия в узле ограничителя, представленного отрезком $[-m,m]$, на перемещение струн под воздействием внешней нагрузки, то есть предполагается, что $|u(0)|\leq m$. Здесь через $N_{[-m,m]}u(0)$ обозначен нормальный конус к $[-m,m]$ в точке $u(0)$. В работе проведен вариационный вывод модели; доказаны теоремы существования и единственности решения; проанализированы критические нагрузки, при которых происходит соприкосновение струн с ограничителем; приведена явная формула представления решения.

Предложен метод расчета порога протекания x_c бесконечной решетки в d-мерном пространстве на основе среднего значения величины x_cL решеток малых размеров L. Условие применимости метода ограничило круг рассматриваемых 2d и 3d решеток в задаче узлов до квадратной и алмазной. Величины x_cL для этих решеток рассчитывались на основе вектора начального состояния решетки и матрицы смежности графа, соответствующего решетке с долей узлов x=1. Вычислены пороги протекания квадратной решетки x_c=0,592744 и решетки алмаза x_c=0,430308.

Представлена полная аналитическая классификация атомов гиростата Ковалевской–Яхья, возникающих в критических точках ранга 1. Найдены все разделяющие значения гиростатического момента при классификации диаграмм Смейла–Фоменко. Разработан "конструктор" графов Фоменко, применение которого дало полное описание грубой топологии этого интегрируемого случая. Доказано, что имеется девять групп эквивалентных молекул (без меток), содержащих 22 устойчивых графа и 6 неустойчивых по отношению к количеству критических окружностей на критических уровнях.

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

Разметка ребер связного графа $G = (V, E)$ называется локальной антимагической, если она является биекцией $f\colon E \to\{1,\ldots ,|E|\}$ такой, что для любой пары смежных вершин $x$ и $y$ выполнено $f^+(x)\not= f^+(y)$, где $f^+(x)= \sum f(e)$ — индуцированная метка вершины, а $e$ пробегает все ребра, инцидентные $x$. Локальное антимагическое хроматическое число графа $G$, обозначаемое $\chi_{la}(G)$, — это минимальное число различных индуцированных меток вершин среди всех локальных антимагических разметок $G$. В данной статье мы охарактеризуем $s$-мостовые графы с локальным антимагическим хроматическим числом 2.

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

Этот метод c 2004 года используется А.Г. Ченцовым и его соавторами, но степень экономии ресурсов исследовалось мало. Мы предлагаем подход к решению этой проблемы, основанный на комбинаторном анализе числа подзадач, существенных в смысле условий предшествования. Применяя известные комбинаторные правила сложения и произведения, мы получили результат для важных частных случаев условий предшествования: а) «независимые» наборы условий предшествования; б) «цепь» условий предшествования - когда условия задают линейный порядок; в) случай, когда в графе предшествования нет неориентированных циклов, и исходящая степень любой вершины не превышает единицы. Последний случай представляет собой условия предшествования, встречающихся в практической задаче маршрутизации движений инструмента в машинах листовой резки и соответствует требованию вырезать внутренний контур прежде внешнего.

В связи с более сложной структурой случая в) по сравнению с остальными для него вместо аналитической формулы представлен алгоритм; алгоритм реализован на языке C++, зависимость его вычислительной сложности от числа связанных условиями предшествования объектов имеет не более чем квадратичный порядок. В дальнейшем мы предполагаем расширить область применения нашего подхода до более общих вариантов условий предшествования. Отметим также, что наш подход не зависит от критерия оптимальности, соответственно, может применяться для анализа сложности решения методом динамического программирования в произвольных маршрутных задачах с условиями предшествования.