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

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

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

Настоящее пособие «Методические рекомендации к выполнению контрольной работы по дискретной математике» предназначено для студентов заочного отделения физико-математического факультета педагогического ВУЗа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Статья посвящена проблемам возрождения в современном учебном курсе математического моделирования имитационной игры, в которую играли в отделе Н. Н. Моисеева Вычислительного центра АН СССР в конце 1960-х — начале 1970-х годов такие видные специалисты в области прикладной математики, как И. А. Ватель, Ю. Б. Гермейер, Ю. Г. Евтушенко, Ф. И. Ерешко, А. Ф. Кононенко, П. С. Краснощеков, Ю. Н. Павловский, А.А. Петров.

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

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

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

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

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

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

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

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

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

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