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

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

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

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

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

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

Рассмотрены комбинаторные вычисления, их основные операционные объекты: сочетания, перестановки, размещения и разбиения элементов конечных множеств и натуральных чисел.

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

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

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

В сборнике «Труды РФЯЦ-ВНИИЭФ» опубликованы результаты научных исследований, а также методических и проектно-конструкторских разработок в области прикладных задач теоретической физики, математического моделирования физических процессов, ядерной физики, физики ядерных реакторов, исследований по термоядерному синтезу, электрофизики, физики ускорителей, приборов и техники эксперимента, физики лазеров, гидродинамики, реологии, физики горения и взрыва, физической химии, экологии, материаловедения, безопасности, средств защиты от несанкционированных действий, электроники, радиотехники, оптоэлектроники.

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

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

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

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

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

Эта книга - уникальная монография о векторных расслоениях на кривых, написанная одним из самых ярких геометров нашего времени. Её цель - показать, как с необыкновенной красотой переплетаются в геометрии векторных расслоений самые разные ветви современной математики: классические алгебраическая и дифференциальная геометрия, лагранжева геометрия и геометрическое квантование, дифференциальные уравнения на многообразиях и анализ Фурье, теория представлений и комбинаторика графов, калибровочные теории и квантовая теория поля... Автор щедро делится с читателем замечательными геометрическими конструкциями, остроумными идеями и нерешёнными вопросами, вскрывающими глубокие связи между на первый взгляд далёкими друг от друга разделами математики и математической физики.

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

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

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

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

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

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

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

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

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

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

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

Рассматриваются четыре комбинаторные задачи, параметризованные кратностью r элемента базового мультимножества: распределение индексов vp-монотонных перестановок, обобщенные перестановки Гесселя-Стенли и обобщенные частично упорядоченные множества Баклавского-Эдельмана, обобщенные числа Стирлинга и обобщенные частично упорядоченные множества разбиений, обобщенные статистики и обобщенные многочлены Эйлера. Для исследования этих задач привлекаются различные методы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Журнал физико-химического профиля. Адресован специалистам, работающим в области квантовой химии, физических методов исследования, кристаллохимии, супрамолекулярной химии, структуры и свойств наноматериалов, строения жидкостей, а также широкому кругу химиков. Своеобразие журнала заключается в том, что для исследования электронного и пространственного строения химических соединений в публикуемых работах широко применяются современные физические методы, оригинальные теоретические и экспериментальные подходы. Форма публикаций - статьи, краткие сообщения, тематические обзоры по различным проблемам структурной химии. С 2004 г. Издаётся ежегодное Приложение к Журналу, в котором публикуются статьи по актуальным направлениям структурной химии. Журнал переводится на английский язык, издается и распространяется за рубежом Издательством Springer. Название англоязычного издания Journal of Structural Chemistry.

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

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

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

Журнал физико-химического профиля. Адресован специалистам, работающим в области квантовой химии, физических методов исследования, кристаллохимии, супрамолекулярной химии, структуры и свойств наноматериалов, строения жидкостей, а также широкому кругу химиков. Своеобразие журнала заключается в том, что для исследования электронного и пространственного строения химических соединений в публикуемых работах широко применяются современные физические методы, оригинальные теоретические и экспериментальные подходы. Форма публикаций - статьи, краткие сообщения, тематические обзоры по различным проблемам структурной химии. С 2004 г. Издаётся ежегодное Приложение к Журналу, в котором публикуются статьи по актуальным направлениям структурной химии. Журнал переводится на английский язык, издается и распространяется за рубежом Издательством Springer. Название англоязычного издания Journal of Structural Chemistry.

Учебное пособие соответствует государственному образовательному стандарту дисциплин «Дискретная математика», «Математическая логика и теория алгоритмов». Пособие содержит краткий курс дискретной математики и математической логики. В каждом разделе приведены подробно разобранные примеры.

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