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

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

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

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

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