Настоящее учебное пособие предназначено для студентов всех
направлений и специальностей, изучающих дисциплину «Теория графов».
Пособие разработано в помощь к решению практических заданий и
содержит краткое изложение теории по темам«Пути, маршруты»,
«Связность», «Деревья», «Кратчайший остов», «Эйлеровы и гамильтоновы
графы» и «Кратчайшие пути». Рассмотрены примеры с подробными
решениями
Пособие представляет результаты исследования по проблеме изучения дисциплины «Прикладная теория графов» бакалаврами направления подготовки «Прикладная математика и информатика». В пособии рассмотрены следующие вопросы: история возникновения теории графов, основные понятия, виды графов, матрицы смежности и инцидентности, изоморфизм, элементы графа, маршрут, цепь, цикл, путь и контур, связность, полный граф, теорема Куратовского, формула Эйлера, деревья, эйлеровы линия, граф и путь, алгоритм Декстра, проблема коммивояжера, алгоритм «самой близкой вставки». Учебное пособие содержит краткий теоретический материал, примеры решения задач, вопросы и задания для самоконтроля, тестовый материал, а также практические работы (по вариантам).
В работе впервые доказана теорема – обобщенная формула Леонарда Эйлера для произвольного непланарного графа, то есть графа с пересечением ребер. Введено определение степени точки пересечения для ребер графа по аналогии с определением со степенью вершины графа. Полученная формула найдет применение в теории графов и войдет в курс лекций по дискретной математике и теории графов. Для студентов физико-математических специальностей, студентов педагогических, технических университетов, преподавателей, инженеров, программистов использующих в своей практической деятельности теорию графов, комбинаторную геометрию, теорию алгоритмов.
Настоящее учебное пособие предназначено для студентов всех направлений и специальностей, изучающих дисциплину «Теория графов». Пособие разработано в помощь к решению практических заданий и содержит краткое изложение теории по темам «Пути, маршруты», «Связность», «Деревья», «Кратчайший остов», «Эйлеровы и гамильтоновы графы» и «Кратчайшие пути». Рассмотрены примеры с подробными решениями.
Настоящее учебное пособие предназначено для студентов всех направлений и специальностей, изучающих дисциплину «Дискретная математика и математическая логика». Пособие разработано в помощь к решению практических заданий и содержит краткое изложение теории по темам «Теория множеств», «Теория графов» и «Математическая логика». Рассмотрены примеры с подробными решениями, приведены задания для самостоятельной работы.
Организация непрерывного мониторинга значительных пространств с динамически меняющимися условиями и обстановкой является одной ключевых задач в различных направлениях жизнедеятельности человека. Особо остро эта задача стоит в России с учетом ее территорий (земель), предназначенных для сельскохозяйственной деятельности. Особую важность организации непрерывного мониторинга подчеркивает и развитие концепции и технологий точного земледелия. В качестве средств для решения этой системной задачи могут использоваться различные робототехнические и беспилотные системы, оснащенные необходимым оборудованием в соответствии с локальными задачами непрерывного мониторинга. Непрерывный мониторинг при этом может быть обеспечен только применением эффективных алгоритмов построения траектории движения используемых подвижных робототехнических и беспилотных (в первую очередь авиационных) систем. Повышение эффективности таких алгоритмов с математической точки зрения всегда усложняется цикличностью траекторий движения, т.е. построением гамильтонова цикла. В рамках данной работы предлагается метод конструирования оптимальной траектории движения при выполнении задач непрерывного циклического мониторинга сельскохозяйственных полей. Метод основан на поиске гамильтонова цикла на графе карты местности и позволяет автоматически строить оптимальный замкнутый путь для произвольной карты местности. Отличительной особенностью метода является использование модифицированного алгоритма поиска гамильтонова цикла. Алгоритм может быть масштабирован для карт, соответствующих графам с большим (более 100) количеством вершин, для которых стандартный алгоритм поиска гамильтонова цикла методом перебора требует значительно большего времени выполнения, чем предложенный алгоритм. Показано, что используемый алгоритм обладает в 17 раз меньшей константой роста временной сложности, чем стандартный алгоритм поиска гамильтонова цикла. Это позволяет увеличить количество вершин графа, используемого для поиска гамильтонова цикла в режиме реального времени (от 0.1 до 100 секунд), на порядок (от 30 до 500). Разработанный алгоритм может быть внедрён в современные беспилотные системы мониторинга состояния сельскохозяйственных полей для оптимизации траектории движения беспилотных аппаратов в режиме реального времени (0.1-100 секунд), внося тем самым вклад в динамично развивающуюся область точного земледелия.
Предметом данного исследования является модель системы оптимального распределения инвестиций в экономике, испытывающей потребность в импортозамещении в условиях внешних шоков и санкций. Необходимо построить математическую модель, связывающую отраслевую структуру инвестиций и выпуска, с учетом технологических ограничений. В настоящей статье исследуются возможности применения моделей структуры и динамики экономики для целей импортозамещения, использования в этих целях производственной функции, динамических стохастических моделей общего равновесия и байесовских векторных авторегрессий. Авторский метод, представленный в статье, основан на построении дерева решений для перебора циклов обхода - вариантов маршрута с отсечением. Метод может быть модифицирован для сокращения времени его работы. Рекомендуемая технология построения модели структуры импортозамещения сводится первоначально к построению ее целевой функции и представлению в виде графа. Впоследствии на основе структуры данных, позволяющих строить маршруты, авторами был представлен алгоритм, который является основой для реализации оптимального распределения инвестиций в отраслевой структуре и контроля их соответствия обозначенным требованиям импортозамещения. На базе данного алгоритма разработаны архитектура и структура программного средства с соответствующими классами, которое обеспечивает выходные данные в виде соответствия «инвестиции-отрасль». Полученные результаты необходимы для разработки программного средства, позволяющего решить важную отраслевую задачу моделирования структуры импортозамещения на основе распределения инвестиций по отраслям и продуктам, а также прогнозировать воздействие на этот процесс новых внешних шоков и технологических ограничений, изменения производительности труда и уровня загрузки производственных мощностей.
Сегодня беспилотная авиация используется для решения самых разных задач. Одна из проблем, возникающих при использовании беспилотных летательных аппаратов (БПЛА), – это проблема навигации, в частности установление их точного местоположения в пространстве. Сегодня существуют различные методы решения этой проблемы. Перспективным способом ее решения в условиях невозможности использования спутниковой системы навигации являются системы видеонавигации, использующие для установления местоположения визуальные ориентиры. В настоящей работе проведен обзор существующих типов систем видеонавигации БПЛА, выделены особенности работы систем видеонавигации, использующих сопоставление визуальных ориентиров со спутниковыми картами, поставлена задача поиска маршрута в условиях недостатка визуальных ориентиров, при которых возможно возникновение проблемы потери опорных точек. Описан используемый графовый формат данных, хранящий значения метрики разнообразия подстилающей поверхности, которая характеризует величину вероятности возникновения проблемы потери опорных точек. Рассмотрены существующие алгоритмы поиска пути в графе и обоснована необходимость разработки нового алгоритма.
Предложено теоретическое описание алгоритма, в котором процесс поиска пути делится на два этапа: вначале производится поиск варианта решения с максимальным значением метрики разнообразия подстилающей поверхности, а затем выбор маршрута с минимальной длиной. Приведено несколько вариантов реализации предложенного алгоритма и выполнена оценка их асимптотической сложности. На основании теоретического описания разработана программная реализация предложенного алгоритма и выполнена экспериментальная проверка корректности его работы на тестовой карте с различными полетными заданиями. По результатам тестирования предложенный алгоритм показал свою работоспособность, корректно построив маршруты во всех тестовых примерах. В дальнейшем этот алгоритм может быть использован как часть системы видеонавигации БПЛА. Также в статье описаны основные преимущества и недостатки ал