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

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

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

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

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