?
Структурные и алгоритмические свойства максимальных диссоциирующих множеств в графах
Труды института математики и механики УрО РАН. 2022. Т. 28. № 2. С. 114–142.
Подмножество вершин графа называется диссоциирующим, если степени вершин подграфа, порожденного этим подмножеством, не превосходят 1. Диссоциирующее множество максимально, если оно не содержится ни в каком другом диссоциирующем множестве с бо́льшим числом вершин. В данной работе предлагаются оценки наибольшего (наименьшего) числа вершин в максимальном диссоциирующем множестве графа. Доказано, что задача нахождения максимального диссоциирующего множества наибольшей мощности NP-трудна для квазихордальных двудольных графов. Кроме этого доказано, что задача нахождения максимального диссоциирующего множества наименьшей мощности NP-трудна для хордальных двудольных графов, двудольных графов с максимальной степенью вершин, равной 3, планарных графов с большим обхватом, а также для классов графов, характеризуемых конечными списками запрещенных порожденных двусвязных подграфов. Предлагается линейный алгоритм решения последней задачи в классе деревьев.
Починка О. В., Баринова М. К., Journal of Geometry and Physics 2026 Vol. 228 P. 1–8
Добавлено: 30 июня 2026 г.
Герман О. Н., Илларионов А. А., Известия РАН. Серия математическая 2026 Т. 90 № 3 С. 3–18
Пусть симплекс с целочисленными вершинами - содержащий ровно одну целочисленную точку, отличную от своих вершин. В работе доказывается, что если точка находится во внутренности симплекса или в относительной внутренности некоторой гиперграни симплекса, то объем симплекса ограничен величиной, зависящей только от размерности, в противном случае объем симплекса может быть сколь угодно большим. Этот результат применяется для вывода асимптотической формулы для среднего числа вершин полиэдров ...
Добавлено: 29 июня 2026 г.
В данной работе мы сосредоточимся на обобщении эмпирического закона Херста и предложим набор редуцированных параметров для количественного описания длительных временных рядов. Эти ряды обычно рассматриваются как специфический отклик сложной системы (экономической, геофизической, электромагнитной и других), где последовательная фиксация внешних факторов становится невозможной. Мы рассматриваем применение обобщенных законов Херста для получения нового набора редуцированных параметров в ...
Добавлено: 27 июня 2026 г.
Ивченко А. В., Shestoperov A. I., Fomina E. V., Microgravity Science and Technology 2025 Vol. 37 No. 19 P. 1–19
Данная работа посвящена анализу медико-биологических данных, полученных в ходе локомоторных тестов космонавтов. Точная интерпретация данных играет решающую роль в мониторинге системы передвижения, профилактике негативных последствий длительного космического полета и, следовательно, в разработке автономной системы медицинского обеспечения для экспедиций в дальний космос. Во время локомоторных тестов космонавт меняет режимы движения в соответствии с предписанным протоколом тренировки, ...
Добавлено: 26 июня 2026 г.
Гаджимирзаев Ш. М., Хельвас А. В., 2023 3rd International Conference on Innovative Research in Applied Science, Engineering and Technology (IRASET) Mohammedia, Morocco 2023 P. 1–6
В статье предлагается архитектура событийно-управляемого Центра экстренного реагирования с компонентом компьютерного зрения. Анализируются источники информации и обсуждаются подходы к использованию событий компьютерного зрения для обнаружения и оценки тактических ситуаций. Сообщения от компонентов компьютерного зрения преобразуются в Протокол общих оповещений (Common Alerting Protocol) и обрабатываются средой Центра управления для распознавания тактических ситуаций. ...
Добавлено: 26 июня 2026 г.
Гаджимирзаев Ш. М., Хельвас А. В., Лукьянченко П. П., Computer Research and Modeling 2023 Vol. 15 No. 1 P. 129–140
В данной статье нами предложен новый подход к анализу эконометрических параметров отрасли для уровня консолидированности отрасли. Исследование базируется на простой модели управления отраслью в соответствии с моделью из теории автоматического управления. Состояние отрасли оценивается на основе ежеквартальных эконометрических параметров получаемых в обезличенном виде от каждой компании отрасли через налогового регулятора. Предложен подход к анализу отрасли, ...
Добавлено: 26 июня 2026 г.
Гаджимирзаев Ш. М., Хельвас А. В., International Frequency Sensor Association (IFSA) Publishing, 19-21 February 2025 Granada, Spain 2025 P. 172–176
В статье представлены модели инновационного полностью роботизированного склада для хранения коробочных товаров. Была реализована дискретная многоагентная симуляция движения челноков на складе для заданной последовательности паллетных отгрузок. Оцениваются различные стратегии размещения коробок в разных зонах склада, а также оптимальные схемы маршрутизации челноков для заданной топологии склада. Также оценивается оптимальное количество челноков, максимизирующее производительность склада. ...
Добавлено: 26 июня 2026 г.
Воронеж: Издательский дом ВГУ, 2026.
В сборнике представлены материалы докладов и лекций, включенных в программу весенней математической школы. ...
Добавлено: 25 июня 2026 г.
Оноприенко А. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае ...
Добавлено: 23 ноября 2025 г.
Вялый М. Н., Карпов В. Е., Дискретный анализ и исследование операций 2023 Т. 30 № 3(157) С. 81–95
Изучается задача реализации гиперграфа на графе с условием, что каждое ребро гиперграфа реализуется подграфом, в котором ровно две вершины имеют нечётную степень. Установлена связь такой задачи реализации гиперграфов и гипотезы о двойном покрытии циклами. Доказана алгоритмическая трудность проверки существования реализации в различных постановках: реализации на всех графах, на простых графах и на графах из нескольких ...
Добавлено: 31 октября 2023 г.
Обухов А. С., В кн.: Практические задания в области STEM-образования: Сборник в трех томахТ. 1: Задания для работы с учащимися начальной школы.: М.: Библиотека журнала «Исследователь/Researcher», 2022. С. 93–94.
Задача для младших школьников, знакомящее с вариативностью строения листа деревьев и определение вида дерева по листу. ...
Добавлено: 1 февраля 2022 г.
Клемашев Н. И., Шананин А. А., Труды Московского физико-технического института 2015 Т. 7 № 4 С. 17–27
Доказана NP-полнота непараметрического теста для модели временного диктатора с несколькими диктаторами с положительно-однородными функциями полезности. ...
Добавлено: 5 марта 2019 г.
Бусяцкая И. К., Кочетков Ю. Ю., / Series arXiv "math". 2018. No. 1811.10357.
В работе сначала рассматриваются плоские корневые деревья с отмеченным ребром, выходящим из корневой вершины. Используя скобочный код таких деревьев, мы вводим новую характеристику -- четность. Оказывается, что четность не зависит от выбора отмеченного ребра, а в случае четного числа вершин, не зависит и от выбора корневой вершины. Далее рассматриваются группы вращений двудольных деревьев. Доказывается, что ...
Добавлено: 27 ноября 2018 г.
Авдошин С. М., Набебин А. А., М.: ДМК Пресс, 2019.
Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто ...
Добавлено: 24 августа 2018 г.
Сироткин Д. В., Журнал Средневолжского математического общества 2017 Т. 19 № 2 С. 98–104
В данной работе вводится некоторый класс замен подграфов в графах, причем замены из этого класса сохраняют $k$-раскрашиваемость. Каждое такое локальное преобразование графов определяется некоторым шаблоном – набором разбиений множества на его подмножества. Показывается, что заменяющий подграф существует для любого шаблона, а также приводится оценка на количество его вершин от размера шаблона. Данный результат является основным ...
Добавлено: 23 августа 2017 г.
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2014 Т. 26 № 2 С. 245–268
Задача унификации пары подстановок θ_1 и θ_2 состоит в вычислении такой пары подстановок η' и η'', чтобы композиции θ_1 η' и θ_2 η'' были равны. По существу, задача унификации подстановок равносильна задаче решения линейных уравнений вида θ_1 X=θ_2 Y в полугруппе подстановок. Но некоторые линейные уравнения над подстановками также можно рассматривать как новые варианты задачи ...
Добавлено: 30 сентября 2015 г.
Замараев В. А., Дискретная математика 2011 Т. 23 № 3 С. 57–62
Рассматриваются классы из нулевого слоя множества бесконечных наследственных классов графов, определяемые двумя запрещенными подграфами. Один из этих подграфов K1,s + Op, а второй Kq. Дается верхняя оценка числа графов в таких классах. ...
Добавлено: 28 июня 2012 г.