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

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

Настоящее пособие составлено на основе олимпиадных задач по математике преподавателями факультета ВМК МГУ имени М. В. Ломоносова. Пособие содержит: теоретический материал, описание методов решения задач, примеры применения методов, набор заданий для решения. Задачи в разделах и сама последовательность разделов выстроены по принципу «от простого к сложному». По данному пособию можно заниматься два года: в 8 классе пройти по всем разделам, выбирая задачи для 8 класса, в 9 классе снова пройти по всем разделам, выбирая задачи для 9 класса. А можно пройти и за 1 год, если вы уже в 9 классе.

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

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

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

Учебник предназначен для изучения алгебры и начал математического анализа в 11 классе общеобразовательных организаций. В нём предусмотрена уровневая дифференциация, позволяющая формировать у школьников познавательный интерес к алгебре и началам математического анализа. Учебник соответствует Федеральному государственному образовательному стандарту среднего общего образования.

Учебное пособие состоит из четырёх частей. Рассмотрены методы анализа, описаны основные классы СВЧ-устройств и линий передачи УВЧ и СВЧ, приведены примеры практических конструкций. В первой части рассмотрены матричные методы анализа линеаризованных СВЧ-устройств, приведены примеры анализа СВЧ-устройств с использованием различных методов, описаны матрицы рассеяния базовых элементов, а также разработанная под руководством автора программа для анализа линейных СВЧ-устройств «ПАПИРУС» и порядок работы с ней.

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

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

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

Цель данного учебного пособия – изложение не очень большого по объему, но достаточного для понимания материала по дискретной математике и ее специальных разделов для студентов первого и/или (преимущественно) второго курсов университета. Издание подготовлено на основе федеральных государственных образовательных стандартов (ФГОС) в соответствии с рабочими (учебными) программами Московского государственного лингвистического университета для направления подготовки бакалавриата «Информационная безопасность» и Финансового университета для направлений подготовки бакалавриата «Информационная безопасность», «Прикладная информатика», «Бизнес-информатика» (профиль «ИТ-менеджмент в бизнесе»). Труд авторов распределился следующим образом: часть I создана И. А. Кирилловым, часть II, материал которой преподавался в Российском государственном гуманитарном университете (РГГУ) и в Московском гуманитарном университете (МосГУ), – М. В. Шептуновым, предисловие и заключение написаны авторами совместно.

Учебное пособие по курсу «Математические и алгоритмические основы построения интеллектуальных систем» (часть 1) совмещает в себе конспект лекций и практикум в части модуля «Использование графовых и гиперграфовых моделей в интеллектуальных системах» и отражает состояние современных аспектов теории графов и гиперграфов с элементами научной новизны, а также возможности их применения для решения реальных практических задач. Пособие содержит теоретический, практический и методический материал по темам: «Основные понятия теории графов», «Виды графов», «Алгоритмы на графах», «Использование графов в интеллектуальных системах», «Гиперграфы» и «Специальные графы в интеллектуальных системах». Каждая тема завершается заданиями для самостоятельной работы студентов и списком вопросов для самоконтроля.

В девятнадцатом выпуске серии «Математика в техническом университете» изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам. Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.

краткой форме доступно изложены основы дискретной математики. Рассмотрены основы теории множеств, уделено внимание комбинаторному и теоретико-множественному подходам. Рассмотрены элементы математической логики. Изложены основные методы и подходы теории графов. Рассмотрены специальные маршруты в графах и поиск путей. Раскрыты основные вопросы теории кодирования. Наряду с основополагающими понятиями – кодами Грея и Хемминга уделено внимание применению алгоритма RSA в режимах шифрования и электронной цифровой подписи. Пособие подготовлено в соответствии с разработанными автором рабочими программами Финансового университета (ФГОБУ ВО «Финансовый университет при Правительстве РФ»).

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

"Учебник написан по материалам курса ""Дискретная математика"", который читается студентам младших курсов факультета компьютерных наук НИУ ВШЭ. Темы этого курса являются частью базовой математической культуры и необходимы будущим математикам, программистам и специалистам в области анализа данных, но не входят в традиционно сложившиеся курсы начального математического цикла (математический анализ, алгебра, линейная алгебра). В книге излагаются начальные сведения из перечислительной комбинаторики, теории графов, теории чисел, теории множеств, теории вероятностей, теории игр, теории вычислимости. Не претендуя на полноценный охват какой-либо из упомянутых теорий, учебник дает введение в эти области, с одной стороны, достаточное для студентов соответствующих специальностей, а с другой –– позволяющее читать специализированную литературу.

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

Многие школьники изучают алгоритмы, готовясь к олимпиадам по программированию. Возможно, что эта книга поможет математикам-олимпиадникам, не занимавшимся алгоритмами, заинтересоваться олимпиадным программированием, а может быть — и теорией алгоритмов.

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

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

Приведены задания для выполнения на практических занятиях по дисциплинам «Дискретная математика», «Теория графов и математическая логика».

В девятнадцатом выпуске серии «Математика в техническом университете» изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методом. Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.

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

В пособии подобраны задачи по курсу дискретной математики, читаемому на I—II курсах НГТУ. Кроме того, в нем содержится большое количество примеров, способствующих самостоятельной работе и приобретению навыков решения задач.

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

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

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

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

Пособие соответствует дисциплине «Дискретная математика» и предназначено для студентов специальностей «032100.00 - Математика с дополнительной специальностью «Информатика», «030100.00 - Информатика с дополнительной специальностью», «032200.00 — Физика с дополнительной специальностью «Информатика». Пособие включает в себя задачи и упражнения по комбинаторике и теории графов. По каждой теме приводятся минимальные теоретические сведения, контрольные вопросы и типовые задачи с решениями.

В ходе лесозаготовительного процесса технологическую схему возможно выстроить, используя разные варианты. При транспортировке древесины с лесосеки на разных этапах применяется водный или сухопутный транспорт в разное время года. Наличие лесных складов и обработка на них древесины также увеличивают многовариантность технологического процесса. Выполнение операций в различных природно- производственных условиях отличается производительностью и материальными затратами. Эффективность производства зависит от эффективного обоснования техно- логии реализации лесозаготовительных операций с учетом динамических природно- производственных условий функционирования предприятия. Цель исследования – совершенствование технологической схемы транспортных, погрузочно-разгрузочных и обрабатывающих операций лесозаготовительного процесса в динамических природно-производственных условиях. Решение поставленной задачи предложено вы- полнить с использованием графоаналитического моделирования. Переменные и постоянные материальные затраты на выполнение отдельных операций технологического процесса являются определяющими факторами при выборе технологической цепочки в динамических природно-производственных условиях. Разработаны подробные графические модели транспортировки древесины от лесосеки до потребителя, погрузочно-разгрузочных и обрабатывающих операций, проходящих на промежуточном и нижнем лесных складах. Показаны возможные варианты технологической цепочки лесозаготовительного процесса. В качестве одного из видов ограничений, накладываемых на поток, протекающий по дугам графа, используются возможные объемы заготовки древесины на лесосеках и реализации продукции потребителям. Предложены математические зависимости, позволяющие осуществить поиск максимального потока минимальной стоимости в динамической структуре технологического процесса выполнения работ на предприятии. Они определяют условия решения поставленной задачи. Предложенная графоаналитическая модель даст возможность осуществить аналитический подход к обоснованию: последовательности транспортировки древесины с лесосек; использования в лесозаготовительном процессе лесных складов, рейдов; применения погрузочно-разгрузочных работ, обрабатывающих операций, вида транспорта; выбора потребителя и вида конечной товарной продукции в динамических природно-производственных условиях работы предприятия. Отличительной характеристикой модели является ее функционирование на основе учета про- изводительности и трудозатрат, предложенных в качестве пропускных способностей дуг графа. Для цитирования: Рукомойников К.П., Мохирев А.П. Обоснование технологической схемы лесозаготовительных работ путем создания динамической модели функционирования предприятия // Лесн. журн. 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.

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

Описаны приемы формирования навыков и компетенций при использовании методов календарно-сетевого планирования логистическими операциями во внешнеэкономической деятельности предприятий и организаций.

Изложен теоретический материал по разделам дискретной математики: множества, отношения, математическая логика, графы, который проиллюстрирован большим количеством примеров. Каждый раздел завершается вопросами и заданиями для самоконтроля. Приведены задания для самостоятельной работы.

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

Учебное пособие затрагивает такие разделы дискретной математики как: теория множеств, отношения и переключательные функции, булева алгебра, комбинаторика, теория графов. Темы образуют единый методически взаимосвязанный курс. Каждый раздел содержит большое количество разобранных задач и примеров.

Изоморфизм двух коммутативных идемпотентных полугрупп (полурешеток) можно устанавливать с помощью алгоритмов теории графов. Для этого полурешеткам сопоставляется граф, и в том случае, когда полученный граф является деревом, для проверки изоморфизма таких полурешеток применяются известные алгоритмы проверки изоморфизма деревьев. Еще один из видов графов, для которых существует алгоритм проверки изоморфизма (отличающийся от алгоритмов полного перебора), – планарные графы. В статье решен вопрос о том, является ли граф произвольной полурешетки деревом, планарным графом. Реализован алгоритм, с помощью которого можно выяснить, изоморфны ли полурешетки, графы которых являются деревьями. Данный алгоритм может быть применен и для произвольных полурешеток, но в этом случае для изоморфных полурешеток ответ будет верным, а для неизоморфных может быть ошибочным. В статье показано, какое кодовое слово выдается произвольной полурешетке; и то, что это кодовое слово может служить инвариантом для проверки изоморфизма такой полурешетки. Далее рассмотрены другие инварианты теории графов, которые можно успешно применить для полурешеток, а также решен вопрос о полноте представленной системы инвариантов. Созданная в итоге программа для двух произвольных полурешеток, заданных таблицами Кэли, дает информацию о графах (их инварианты), определяет, изоморфны ли они; в случае изоморфизма выдается биективное отображение элементов этих полурешеток. С помощью программы были проанализированы все полугруппы от первого до восьмого порядков, для каждого порядка найдено число полурешеток, графы которых являются деревьями; показано, что для полурешеток не выше восьмого порядка совокупность предложенных инвариантов является полной системой инвариантов.

Содержат 60 вариантов охватывающих основные положения раздела «Моделирование физических объектов с применением теории графов» учебной дисциплины «Моделирование в технике», а также краткие методические указания к выполнению расчётно-графического задания.

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

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

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

Граф-решетка имеет вершины в точках плоскости с неотрицательными целыми координатами. Из каждой вершины выходят две ориентированные дуги: горизонтальная и вертикальная в соседние вершины (правую и верхнюю). Вероятность перехода по каждой из дуг равна 1 2 . Рассмотрена задачи о случайных блужданиях по вершинам графа с ограниче- ниями на достижимость. Допустимыми на графе-решётке считаются только 2- и 3-пути. Под 2(3)-путем на графе решётке будем понимать путь, удовлетворяющий условию: его начальный и все внутренние максимальные по вложению подпути, состоящие только из вертикальных дуг, имеют длину, кратную 2 (3). Получена формула для количества таких путей, соединяющих заданные вершины графа-решётки, найдена вероятность попадания из одной вершины в другую по 2и 3-путям. Следствием последнего является комбинаторное тождество, использующее элементы треугольника Паскаля.

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

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

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

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

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

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

Основан в 1963 г. Публикуются материалы по теории и методам управления, по изучению, проектированию, моделированию, разработке и применению новых систем управления. Особое внимание уделяется публикациям, посвященным компьютерным методам и технологиям (вычислительные алгоритмы, методы компьютерной алгебры), распознаванию образов и обработке изображений, робототехнике и микропроцессорам.Журнал является рецензируемым и включен в Перечень ВАК.

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

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