Комбинаторный анализ. Теория графов

Настоящее пособие составлено преподавателями факультета ВМК МГУ имени М.В. Ломоносова на основе олимпиадных задач по математике. Пособие содержит теоретический материал, подборку задач, а также идеи, указания (подсказки) и решения.

Настоящее пособие адресовано студентам института физической культуры и спорта. Оно написано в соответствии с требованиями государственных образовательных стандартов по дисциплине «Основы математической обработки информации» для направлений подготовки: 44.03.01 «Педагогическое образование», профили «Безопасность жизнедеятельности», «Физическая культура», 44.03.05 «Педагогическое образование» (с двумя профилями подготовки), профили «Безопасность жизнедеятельности и Физическая культура», «Физическая культура и Дополнительное образование (адаптивное физическое воспитание)», 49.03.01 «Физическая культура», профиль «Физическая культура и спорт».

Рассматриваются основы объектно-ориентированного программирования на С++ задач на графах – от создания класса до разработки иерархии классов, основанной на классификации способов задания графов.

В ходе лесозаготовительного процесса технологическую схему возможно выстроить, используя разные варианты. При транспортировке древесины с лесосеки на разных этапах применяется водный или сухопутный транспорт в разное время года. Наличие лесных складов и обработка на них древесины также увеличивают многовариантность технологического процесса. Выполнение операций в различных природно- производственных условиях отличается производительностью и материальными затратами. Эффективность производства зависит от эффективного обоснования техно- логии реализации лесозаготовительных операций с учетом динамических природно- производственных условий функционирования предприятия. Цель исследования – совершенствование технологической схемы транспортных, погрузочно-разгрузочных и обрабатывающих операций лесозаготовительного процесса в динамических природно-производственных условиях. Решение поставленной задачи предложено вы- полнить с использованием графоаналитического моделирования. Переменные и постоянные материальные затраты на выполнение отдельных операций технологического процесса являются определяющими факторами при выборе технологической цепочки в динамических природно-производственных условиях. Разработаны подробные графические модели транспортировки древесины от лесосеки до потребителя, погрузочно-разгрузочных и обрабатывающих операций, проходящих на промежуточном и нижнем лесных складах. Показаны возможные варианты технологической цепочки лесозаготовительного процесса. В качестве одного из видов ограничений, накладываемых на поток, протекающий по дугам графа, используются возможные объемы заготовки древесины на лесосеках и реализации продукции потребителям. Предложены математические зависимости, позволяющие осуществить поиск максимального потока минимальной стоимости в динамической структуре технологического процесса выполнения работ на предприятии. Они определяют условия решения поставленной задачи. Предложенная графоаналитическая модель даст возможность осуществить аналитический подход к обоснованию: последовательности транспортировки древесины с лесосек; использования в лесозаготовительном процессе лесных складов, рейдов; применения погрузочно-разгрузочных работ, обрабатывающих операций, вида транспорта; выбора потребителя и вида конечной товарной продукции в динамических природно-производственных условиях работы предприятия. Отличительной характеристикой модели является ее функционирование на основе учета про- изводительности и трудозатрат, предложенных в качестве пропускных способностей дуг графа. Для цитирования: Рукомойников К.П., Мохирев А.П. Обоснование технологической схемы лесозаготовительных работ путем создания динамической модели функционирования предприятия // Лесн. журн. 2019. № 4. С. 94–107. (Изв. высш. учеб. заведений). DOI: 10.17238/issn0536-036.2019.4.94 Финансирование: Исследование выполнено при финансовой поддержке РФФИ, правительства Красноярского края, Красноярского краевого фонда науки в рамках научного проекта «Исследование и моделирование процессов развития экономики лесной промышленности региона в контексте природно-климатических условий и ресурсного потенциала», № 18-410-240003.
It is possible to build a technological scheme using various options in the process of logging. Water or land transport is used in different seasons during wood transportation from the cutting area at different stages. The presence of wood depots and wood processing at them also increase the multivariance of the technological process. The operation flow in various natural and industrial conditions differs in productivity and material expenses. Production efficiency depends on the effective validation of the technology of logging operations’ implementation with regard to the dynamic natural and industrial conditions of the enterprise functioning. The research purpose is improving of the technological scheme of transport, handling and processing operations of logging in dynamic natural production conditions. The solution of the issue is proposed to perform using semi-graphical modeling. Variable and constant material expenses for the individual operations flow of the technological process define the technological scheme in the dynamic natural and industrial conditions. As a result detailed graphic models of wood transportation from the cutting area to the consumer, handling and processing operations taking place in the intermediate and lower wood depots have been developed. The possible variants of the logging technological scheme are shown. Possible volumes of timber harvesting in cutting areas and consumer sales of products are used as one of the restrictions imposed on the flow running through the graph arcs. Mathematical functions allowing searching for the maximum flow of the minimum cost in the dynamic structure of the technological process of work flow at the enterprise are proposed. They define the conditions for problem solving. The proposed semigraphical model will enable the analytical approach to validation the sequence of wood transportation from the cutting area and usage of wood depots and raids in logging, using of handling and processing operations, choosing the transport type, consumer and type of final commodity products in the dynamic natural production conditions of the enterprise working. A distinctive feature of the proposed model is its functioning based on the performance and labor costs proposed as the throughput of the graph arcs. For citation: Rukomojnikov K.P., Mokhirev A.P. Validation of the Logging Operations Scheme through the Creation of Dynamical Model of the Enterprise Functioning. Lesnoy Zhurnal [Forestry Journal], 2019, no. 4, pp. 94–107. DOI: 10.17238/issn0536-1036.2019.4.94 Funding: The research was carried out with the financial support of the RFBR, Government of Krasnoyarsk Krai and Krasnoyarsk Regional Fund of support scientific and technical activities, KSAU within the framework of the scientific project “Research and Modeling of the Economic Development Processes of the Region’s Timber Industry in the Context of Natural and Climatic Conditions and Resource Potential”, no. 18-410-240003.

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

Получены некоторые конкретные нижние экспоненциальные оценки хроматических чисел дистанционных графов с большим обхватом

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

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

Статья посвящена изложению одного из многочисленных приложений общих понятий дискретной математики. В качестве примера излагаются начала теории сетей Петри. Даны определения основных понятий этой теории. Описана работа сетей Петри на языке теории графов (наглядное описание) и затем на языке линейных операций над векторами с целочисленными координатами. Затронута теория графов (и деревьев) маркировок. Отмечена проблема алгоритмической разрешимости задач, связанных с графами маркировок. Объяснено, каким образом сети Петри применяются для описания сложных систем, а также для описания работы сложных систем взаимодействующих устройств. Подробно рассмотрен пример составления сети Петри такого рода. Изложение не требует предварительных знаний по данной теме. Для восприятия излагаемого материала необходимы только элементарные сведения по теории графов и начала линейной алгебры. Материал статьи может быть использован в качестве тем для внеаудиторной работы студентов.

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

Рассматривается формализм, предназначенный для представления специального расширения класса конечных автоматов - так называемых обобщенных недетерминированных конечных автоматов. Из изложенных в статье алгоритмов эквивалентного преобразования определяемых авторами автоматов и аналога теоремы Клини для них вытекает не столько эквивалентность их и обычных конечных автоматов (эта эквивалентность очевидна априори), сколько возможность определения операции дополнения (и вообще обобщенных регулярных выражений) обычными "автоматными" методами. Также в статье описан метод построения конкретного обобщенного автомата, который определяет заданное обобщенное регулярное выражение. Данный метод вытекает из доказательства аналога теоремы Клини. Представленные расширенные возможности для описания регулярных языков могут быть полезны в некоторых приложениях, например, в контекстном поиске.

Текст лекций предназначен для студентов, обучающихся по специальности 090102.65 Компьютерная безопасность (дисциплина «Алгоритмы на графах», блок ОПД), очной формы обучения.